Smiling & Weeping
----我对姑娘的喜欢,何止钟意二字自我分析:我感觉这是一道很有意义的题目,可以帮我们更好的理解二进制的本质
思路:首先先了解一下题目,我们是求由第i个数到末尾的异或和(异或:相同为0,不同为1),那么我们可以换种思路,可以求从1到i的异或和m,再^上从1到j的异或和(1 <= j <= i) ,毕竟异或相同的数两次等于0,那么有了这个算法思路,我们可以设计程序了:
使用vis记录曾经出现的异或和(a < pow(2 , 8) ), 再从1遍历到n , 算法的复杂度为O(pow(2,8)*n) , 可以通过
现在是代码时间(づ ̄3 ̄)づ╭❤~you
1 #include<bits/stdc++.h> 2 using namespace std; 3 int t , n; 4 const int maxn = 1 << 8; 5 int main() 6 { 7 scanf("%d",&t); 8 while(t--) 9 { 10 scanf("%d",&n); 11 int cur = 0 , ans = 0; 12 vector<int> num(n+10); 13 vector<bool> vis(maxn+10); 14 for(int i = 1; i <= n; i++) 15 scanf("%d",&num[i]); 16 vis[0] = true; 17 for(int i = 1; i <= n; i++) 18 { 19 cur ^= num[i]; 20 for(int j = 0; j < maxn; j++) 21 { 22 if(vis[j]) 23 { 24 int an = j^cur; 25 ans = max(ans , an); 26 // vis[an] = true; 27 } 28 } 29 vis[cur] = true; 30 } 31 printf("%d\n",ans); 32 } 33 return 0; 34 }
其实对第26行,我还是深有感触的,我们大可不必去记录每个的前j个的异或和与新值(记录了一定出错,不符合题意,思考一下(ˇˍˇ) 想~),再填入vis中,就像二进制运算一样,它的所有可能出现的值都能用前i个异或和 以及 前j个异或和 来异或表示
这路遥马急的人间,你我平安喜乐就好 --o(╥﹏╥)o-- 此后烟雨皆尽散,一人撑伞一人行
标签:题目,int,Codeforces,vis,异或,div.2,Round From: https://www.cnblogs.com/smiling-weeping-zhr/p/17569792.html