题解：P12420 【MX-X12-T3】「ALFR Round 5」变换

· · 题解

前言

很有趣的一道题，但是样例有点水（TAT）。

正篇

首先题面是要求 x~\&~m = x，那么也就是在二进制下 x 为 1 的位置，在 m 的对应位置也必须是 1。那么考虑枚举 m 的二进制的 1 的位置，对于每一位计算可以产生的贡献并计算答案。首先，知周所众，异或这个运算相同为 0 不同为 1。那么肯定要么在某一位进行一次操作，要么不进行操作（因为偶数次操作就等于不做操作，奇数次操作等于做一次操作）。那么如果现在这一位异或起来为 0 那么就需要做一次操作，来使其变为 1 来增加答案，如果已经是 1 了就不需要做操作了，根据这个结论就可以写出满分代码了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll t;
ll n, m, k;
ll a[1000006];
void work()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    ll x = 0;
    for(int i = 0; i < 31; i++)
    {
        if((m & (1 << i)) == 0)
            continue;
        ll cnt = 0;
        for(int j = 1; j <= n; j++)
            cnt += ((a[j] & (1 << i)) > 0);
        if(cnt % 2 == 0)
            for(int j = 1; j <= n; j++)
                if((a[j] & (1 << i)) == 0)
                {
                    a[j] |= (1 << i);
                    break;
                }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++)
        ans ^= a[i];
    cout << ans << "\n";
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    ll t;
    cin >> t;
    while(t--)
        work();
    return 0;
}