自动搬运

查看原文

来自洛谷，原作者为

	GavinCayne 绝岭衔延不可攀，我自信步留蹊去。

搬运于2025-08-24 22:42:53，当前版本为作者最后更新于2023-08-04 01:15:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8826 游戏 题解

传送门

这是当年传智杯初赛最难的题，说是黄题中的佼佼者也不为过。甚至过了三年提交 $1400$ 通过人数竟不满 $100$！而且无一篇题解（被我捡漏）！一开始本蒟蒻也没有思路，后来看了讨论区别的大佬的思路才豁然开朗（此题数据有问题）。

题目大意

给定 $n$ 个数，两种操作：每次选 $i$ 和 $j$，若 $a[i]\operatorname{xor}a[j]$ 的值二进制只有 $1$ 位为 $1$，则代价 $ans$ 需要加上 $C_1$，如果大于 $1$ 位则代价 $ans$ 加上 $C_2$。做完操作删去其中一个数，问剩最后一个数时 $ans$ 最小是多少。

整理一波思路

1. 若 $C_1=C_2$ 无论异或情况如何代价都不变。直接用操作次数 $n-1$ 乘上一次代价 $C_1$ 出结果。
2. 一位一位判断异或结果实在麻烦，需要转成二进制再倒着（短除法性质）判断每一位上的值是不是 $1$，要循环两次。有什么方法一下就能知道异或的值是不是 $1$ 位是 $1$ 呢？用 $\operatorname{lowbit}$ 函数！$\operatorname{lowbit}(n)$ 表示 $n$ 最低位为 $1$ 的数和它后面的数构成的数值。例：$\operatorname{lowbit}(6)$ 表示 $6(110)$ 最低位为 $1$ 的数及它后面的 $0$ 构成的数 $2(10)$。那么当 $\operatorname{lowbit}(n)=n$ 时，$n$ 一定是 $2$ 的整数次幂（除最高位全是 $0$），它的二进制为 $1$ 的位只可能是最高位！
3. 如何写 $\operatorname{lowbit}$？假设 $n$ 最低位的 $1$ 在第 $k$ 位上，那么 $n$ 取反后 $k$ 以后所有的位数全是 $1$，$k$ 位为 $0$。$n$ 是正数，取反后变成负数，补码要加 $1$，刚好 $k$ 位又回到 $1$。那么 $n$ 与取反后的 $-n$ 做与运算（常识：与运算是将两个数的补码运算）由于 $k$ 位前面的数全由于取反导致与的值为 $0$，所以结果就是 $k$ 位为 $1$ 其它全是 $0$。即 $\operatorname{lowbit}(n)$ 可写作 $n\operatorname{and}(-n)$。
4. 处理好判断异或值了，接下来就要考虑正式操作。统计两种操作中代价较小的次数为 $ans$，则代价大的操作次数为 $n-1-ans$。用两者分别乘上每次的代价 $\min(C_1,C_2)$ 和 $\max(C_1,C_2)$ 就能得出正确结果！
5. 考虑并查集（是的，你没听错，这题还与并查集挂钩）。不难理解，操作不会改变数本身的大小，只需要删掉即可。那么把操作过的数并在一个集合里，每操作一次判断操作的两个数在不在同一集合，不在则并在一起，同时操作次数加一。

喜闻乐见的代码时间

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e4+5;
int n,c1,c2,a[M],ans=0,f[M];
int findfather(int x)//并查集标准模板：找爹 
{
	if(f[x]!=x)f[x]=findfather(f[x]);
	return f[x];
}
int lowbit(int x)//找最低的值为1的位 
{
	return x&(-x);
}
signed main()
{
	cin>>n>>c1>>c2;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];f[i]=i;
	}
	sort(a+1,a+n+1);//可不排 
	if(c1==c2)//判断，如果相等则怎么操作代价都一样 
	{
		cout<<(n-1)*c1;
		return 0;
	}	
	for(int i=1;i<n;i++) 
	{
		for(int j=i+1;j<=n;j++)
		{
			int pd=0,xornum=a[i]^a[j];
			if((xornum||n<=10)&&lowbit(xornum)==xornum)pd=1;//xornum表示异或值不为0，也就是不等 
			if((c1<c2&&pd)||(c1>c2&&!pd))//C1划算就要异或值只有一位为1，也就是pd成立 
			{
				int f1=findfather(i),f2=findfather(j);//并查集 
				if(f1!=f2)
				{
					ans++;f[f1]=f2;
				}
			}
		}
	}
	cout<<(max(c1,c2)*(n-1-ans)+min(c1,c2)*ans);//简单乘法 
	return 0;
}
//最难的黄题搞定了！！！ 

参考资料：$\operatorname{lowbit}$ 详解。 参考 ShanireZ 大佬的做法。 大佬的讨论 同时也是判断异或中 $n\le10$ 的由来（数据的锅，不能保证数据正确）。完结撒花~