To xor or not to xor
给你 n 个非负整数序列 A1, A2, ..., AN。你需要寻找这个序列的一个子序列:Ai1, Ai2, ..., Aik (1<=i1 <i2 <...<ik <=N)满足Ai1 XORAi2 XOR...XORAik最大。
Xor 即为不进位的二进制加法。满足: 0+0=0
1+0=1 1+1=0
在 PASCAL 中，你可以使用 a:=b xor c 语句。其中 a,b,c 均为整型。 输入格式:(xor.in)
第一行包含一个正整数 n，第二行包含整数序列 A1, A2, ..., AN。 输出格式:(xor.out)
包含一个整数，表示 Ai1 XOR Ai2 XOR ... XOR Aik 的最大可能值。
样例输入:
3
11 9 5
样例输出:
14
数据规模:
对于 30%的数据，n<=10
对于 60%的数据，n<=20，ai<=1023
对于 100%的数据，0 <= Ai <= 10^18，0<n<=100。
思路:我们要求的是子序列异或起来的最大值,而0 <= Ai <= 10^18刚好可以用long long存下,
所以可以把每一个Ai看作二进制数,尽量使ans的高位是1,这样就可以保证求出来的是最大值.
开始在判断最高位(1<<63)时非常简单,
只要O(n)扫一遍,每次判断Ai在这一位(1<<63)是不是1就可以,只要有一个Ai这一位是1就可以满足.
但是马上就会发现选不同的数异或都可以使这一位(1<<63)是1,但是之后不一定最优.
这个时候就要给ans一个反悔的机会.
怎么样反悔呢?
怎么样能在异或了Ai之后枚举下一个二进制位时消除Ai的影响又不影响高位呢(相当于异或了别的数)?
(这里很不好想,我卡这儿半天,各位可以思考一下再看)
(结合一下异或的性质)
我们知道A^B^B仍然等于A,而且异或满足结合律
所以在Ans^Ai之后反悔的话,只要把其他这一二进制位是1的Aj都^Ai就可以啦!
这样Ans^Ai^Aj^Ai-->Ans^Aj,这就相当于异或了别的数啦~
选多个Ai也是一样的,在异或Ak之后再选的话,肯定要选偶数个才能保证最优,
偶数个异或起来也是可以消掉的并不影响答案.
一些细节:枚举的到Aj时要判断一下当前ans这一位是不是1,如果是的话才将ans^Aj
但是不管ans这一位是什么,只要Aj这一位是1,就要将其他Ak^Aj,这样才能有足够的反悔机会,不会挤掉答案
感觉有点像dp的二进制优化......?
还有Ak^Aj的时候不能一个for异或下去,要不然j==k的时候Aj就成0了,之后的Ak不会改变,就会WA
最后Aj赋成0就行
(这么傻的错误应该只有我会犯了吧qwq)
来跑个小样例~
(对齐有点问题所以直接截图了)
下面是代码
#include<cstdio> #define ll long long using namespace std; int n; ll num[101]; int main(){ // freopen("xor.in","r",stdin); // freopen("xor.out","w",stdout); ll ans=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&num[i]); for(int i=63;i>=0;i--)//从高位开始枚举 for(int j=1;j<=n;j++) if(num[j]&(1LL<<i)){//a[j]这一位是1 if((ans&(1LL<<i))==0)//ans这一位是0 ans^=num[j]; for(int k=1;k<=n;k++)//为保证之后最优 if((num[k]&(1LL<<i))&&k!=j) num[k]^=num[j]; num[j]=0; } printf("%lld ",ans); return 0; }