$Luogu$ $P5514$ $[MtOI2019]$ 永夜的报应

链接

背景

\(disangan233\) ，迷途之家 \(2019\) 联赛 \((MtOI2019)\) \(T1\) ， \(Luogu\) \(P5514\)

题意

给定 \(n\) 个 \(int\) 范围内的整数，将其中每个数分至某一组后，使得各组内数异或和之和最小的异或和之和。

解法

假设所有数的异或和在 \(2^t\) 位为 \(0\) ，那么分到一组对答案没有贡献。 假设所有数的异或和在 \(2^t\) 位为 \(1\) ，那么显然无论如何分组， \(2^t\) 位对答案的总贡献都不会为 \(0\) （因为当前位有奇数个 \(1\) ），即 \(1\) 是答案下界。 因此，将所有数分为一组即为最优答案，输出所有数的异或和即可，时间复杂度 \(O(n)\) 。\(8.24\) \(17：43\) \(update\) ：根据 \(@Air\_Castle\) 的思路，异或的本质是不进位的加法，而直接相加是要进位的，故异或次数越多越好。而所有数的异或和就是异或次数最多的结果。

\(trick\)

\(1.\) 位运算题目大力按位讨论即可。

代码

$View$ $Code$ //省略头文件 using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,ans; int main() { n=read(); while(n--) ans^=read(); printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/Peter0701/p/11405423.html

相关资源：JAVA上百实例源码以及开源项目