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

· · 题解

题目传送门

思路

容易证明，每次操作总会选择 m\gets x-m ，而不会选择花费 k 的代价保持 m 不变，因为最后要进行异或运算时，只关注每个 a 在每一位上出现 1 的次数的奇偶性，而不是次数(即不是次数越多越好)，所以对于 m 的每一位 1，只需要使用一次即可。

所以，本题的 k 是没有用的！！！

可以看作先将预处理出 a 的异或和 sum，再将 sum 与 m 进行或运算。

但这么做并没有得到满分，why？

注意到，当每一个 a 在某一位上均为 1 时，此时该位出现 1 的次数无法改变(因为进行与运算只会使 1 的个数越来越多，而无法减少)，所以当这一位的异或和为 0 时，无法通过和 m 的与运算将其变为 1。

所以，我们要判断是否存在某些位，所有 a 在这些位上均为 1。

此时，只需要增加一个变量 p ，将其初始化为 2^{31}-1，每次输入时与 a 进行与运算，即可判断在哪些位上所有 a 均为 1。

最后，如何通过 sum，m 和 p 得出最后的答案 ans？

注意到，当某一位上 sum 为 1 时，ans 在这一位上一定为 1；若 sum 为0，则只有 m 在这一位上为 1，p 在这一位上为 0 时，ans 才为1，由此可得：

有了这个，本题就迎刃而解。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int T,n,m,k,ans,p;
inline int read(){
    int p=1,k=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') p=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        k=k*10+c-'0';
        c=getchar();
    }
    return p*k;
}
int main(){
    T=read();
    while(T--){
        n=read(),m=read(),k=read(),ans=0,p=2147483647;
        for(int i=0;i<n;++i){
            int a;
            a=read();
            ans^=a;
            p&=a;
        }
        ans=ans|((m^p)&m);
        printf("%d\n",ans);
    }
    return 0;
}

加入快读以后可以跑到 100~200ms 哦！awa