转载

$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

正文到此结束
本文目录