1004-Black Magic

来源: 杭电杯超级联赛7 算法: 贪心题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1050&pid=1004 补完: Yes 完成时间: August 9, 2022

题意简述

有若干个方块，一种是纯白，一种左侧面是黑色，一种右侧面是黑色，一种是纯黑。黑魔法可以把两个黑色面相贴的方块合并成一个。

给出四种方块的数量 $E 、 L 、 R 、 B$ 。问把方块自由线性排列后合并，最后的方块总数量最小和最大的结果。

题目分析

读题，可知四种方块的特性是：白方块 $E$ 不会和其他的方块合并，单侧黑的方块 $L$ 和 $R$ 放置成 $R L$ 会合并，黑块 $B$ 可以和黑块合并，串多长都行，或者在左右侧呈 $R B / B L / R B L$ 形状和单侧方块合并。

方块排列是自由的，直接给出一个最优结果即可，没有放置的先后顺序的要求，没有分步过程，也就没有后效性，直接贪心找到最合适的方案是可以尝试的。

————

先考虑数量最少。

要让方块数量尽量少，就是要让方块尽量多地合并。

首先，白色方块无法合并，把白色方块数量作为答案的最初值。

对于黑色方块，它可以随意和左方块或者右方块连接，并且连接完左右方块还是保持原来的左或者右可以连接的情况。

所以黑色方块直接并入左或者右方块，暂时不用考虑。

对于左右方块。可以成对地合并，让方块尽量变少。

多余出来的方块落单。

也就是左或者右方块比较少的那个全数并入比较多的那个，答案贡献就是 $m a x （ L ， R ）$ 。

再考虑比较特殊的情况：没有左右方块的时候。

这时候黑色方块不能直接并入，那么把所有的黑色方块接在一起变成一块就行。对答案的贡献是 $1$ 。

————

再考虑数量最多。

与之前相反，这次我们要让左右方块尽量不要合并。显然，左右方块同种连续堆放的时候，不会发生合并。只有左右方块两种放在一起才会合并。而且左右方块一定要黑色那面贴合才会合并。那么我们只考虑左右方块的时候，只要把左方块全放在左边，右方块全放在右边，这样左右方块相接的地方也不会合并，没有方块减少的情况发生。

使用1表示黑面，举个例子：

…（1，0）（1，0）（0，1）（0，1）（0，1）（0，1）…

两边可以无限叠放左右方块，都不会发生合并。

那么他们就给答案来了 $L + R$ 的贡献。

保全了单边的方块之后，我们再看看很容易合并的纯黑方块。

如果没有黑块，那很简单，把白块的数量也加入答案即可。

如果有，我们试着把黑色方块插入，会发现只有左右方块界线的位置才不会发生合并。

也就是变成：

…（1，0）（1，1）（0，1）…

再之后，黑块插入到任意位置都会被合并，那么我们方便起见，把黑块全部堆放在中间先。

这样以后，我们插入白块来拯救这个情况。

白块不止不会和其他方块合并，它还能阻隔会合并的方块。在这需要阻隔的是中间堆放着的黑方块群。

很显然，如果白块数量 $E$ 有黑块数量 $B - 1$ 以上，就可以在每两个黑块中间都插入一个白块。那么所有的黑白块都不会合并， $E + B$ 计入答案贡献。

如果数量不够，那么每次插入一个白块，都可以让一组相邻的黑块被阻隔，相当于一个大黑块被切成两个，再插入一个，再切一刀。插入E个白块，黑块就被切成 $E + 1$ 段，这就是黑块的答案贡献。再加上白块E本身不会合并，总共的答案贡献就是 $E + 1 + E = 2 * E + 1$ 。

最后按这个逻辑编写代码即可。

完整代码

#include<iostream>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int E,L,R,B;
		cin>>E>>L>>R>>B;
		int ans=E;
		ans+=max(L,R);
		if(L==0&&R==0&&B!=0){
			ans++;
		}
		cout<<ans<<' ';
		
		if(B==0){
			ans=R+L+E;
			cout<<ans<<'\n';
		}
		else{
			ans=R+L;
			if(E>=B-1)ans+=E+B;
			else ans+=E*2+1;
			cout<<ans<<'\n';
		}
	}
	return 0;
}

1008-Triangle Gam

来源: 杭电杯超级联赛7 算法: Nim, 博弈论题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1050&pid=1008 补完: Yes 完成时间: August 9, 2022

题意：

Kate和Emilico玩游戏，给定非退化三角形三条边长度分别为 $a 、 b 、 c$ ，玩家轮流在 $3$ 个整数中的一个上减少某个正整数。如果在游戏者的操作后不存在边长为 $a 、 b 、 c$ 的非退化三角形，则游戏者失败。

Kate先手，问Kate会赢吗？若赢输出“Win”，否则输出“Lose”。

解法：

容易推出：

要满足三角形两边之和大于第三边，如果有一条边是1，那么另外两条边一定是等长的，且当至少有一条边为1时，下一轮无论玩家减少哪一条边的边长，都无法形成三角形。

因此题目转换为

kate是否可以先将三角形的任一边变成1，可以就Win，否则Lose。

现在引入一个经典博弈问题：Nim游戏

$n$ 堆物品，每堆有 $a_{i}$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。

取走最后一个物品的人获胜。

当且仅当： $a_{1} \oplus a_{2} \oplus . . . \oplus a_{n} = 0$ ，为先手必赢

知识迁移

Nim游戏中是要将所有 $a_{i}$ 变为0，该题目则是将 $a 、 b 、 c$ 其中一个变为1，以此要先将 $a 、 b 、 c$ 都减1，再进行异或运算。

代码：

#include<iostream>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int a,b,c; 
		cin>>a>>b>>c;
		a--;
		b--;
		c--;
		if(a^b^c)cout<<"Win\n";
		else cout<<"Lose\n"; 
	}
	return 0;
	
}

Shelter

2022杭电杯超级联赛07