P8826 游戏 题解

GavinCayne · 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 的由来（数据的锅，不能保证数据正确）。完结撒花~