首页 > 代码库 > CodeForces 665E Beautiful Subarrays
CodeForces 665E Beautiful Subarrays
题目：Beautiful Subarrays
链接：Here
题意：给一个数组，给一个 ‘完美区间‘ 的定义：l 到r 区间内的所有数异或和大于等于k，问给定数组有多少完美区间。
思路：
异或运算可以前缀和处理，用w[i]表示i 前面的数异或和，那么w[5]^w[3]就是4、5两数异或的值。
现在我们要开始建字典树了（感觉异或和字典树老扯上关系），我们从前往后一个个地把前缀加入字典树（补齐，高位补0），在w[i]加入字典树前，判断w[i]和前面的哪个前缀可以异或并且值大于等于k。这里要用树形DP，根据性质，假设高位异或后，在那一位>k在那一位的值，那就不用往下继续了，因为高位有差别，大小就已经判断出来了，直接加上所有以这个为前缀的w[i]的数量就可以了，细节小心处理，大概就是这样。
AC代码：（没整理，乱七八糟的）
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<math.h> 5 #include<set> 6 #include<map> 7 #include<list> 8 #include<stack> 9 #include<queue> 10 #include<vector> 11 #include<string> 12 #include<iostream> 13 #include<algorithm> 14 using namespace std; 15 #define lson rt<<1 16 #define rson rt<<1|1 17 #define N 1000010 18 #define M 100010 19 #define Mod 1000000007 20 #define LL long long 21 #define INF 0x7fffffff 22 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++) 23 #define For(i,f_start,f_end) for(int i=f_start;i<f_end;i++) 24 #define REP(i,f_end,f_start) for(int i=f_end;i>=f_start;i--) 25 #define Rep(i,f_end,f_start) for(int i=f_end;i>f_start;i--) 26 #define MT(x,i) memset(x,i,sizeof(x)) 27 #define gcd(x,y) __gcd(x,y) 28 const double PI = acos(-1); 29 30 struct Node 31 { 32 int num; 33 int next[2]; 34 }v[N*33]; 35 int vNum; 36 37 int c[33],co; 38 LL ans; 39 40 void add(int x) 41 { 42 int bt[33],bo=0; 43 while(x) 44 { 45 bt[bo++] = x&1; 46 x>>=1; 47 } 48 for(int i=bo;i<33;i++) 49 { 50 bt[i]=0; 51 } 52 int p=0,i; 53 for(i=32;i>=0;i--) 54 { 55 int pos = !bt[i]; 56 57 if(v[p].next[pos]!=-1) 58 { 59 if(c[i]==0) ans+=v[v[p].next[pos]].num; 60 else 61 { 62 p = v[p].next[pos]; 63 if(p==-1) break; 64 continue; 65 } 66 } 67 else if(v[p].next[!pos]==-1) break; 68 if(c[i]==1) break; 69 p = v[p].next[!pos]; 70 if(p==-1) break; 71 } 72 if(i==-1) ans+=v[p].num; 73 p=0; 74 for(int i=32;i>=0;i--) 75 { 76 int pos = bt[i]; 77 if(v[p].next[pos]==-1) 78 { 79 v[vNum].next[0]=v[vNum].next[1]=-1; 80 v[vNum].num=0; 81 v[p].next[pos]=vNum++; 82 } 83 p = v[p].next[pos]; 84 v[p].num++; 85 } 86 } 87 88 int w[N]; 89 int main() 90 { 91 int n,k,x; 92 while(~scanf("%d%d",&n,&k)) 93 { 94 int ttt=k; 95 w[0]=0; 96 for(int i=1;i<=n;i++) 97 { 98 scanf("%d",&x); 99 w[i]=w[i-1]^x;100 }101 co=0;102 while(k)103 {104 c[co++]=k&1;105 k>>=1;106 }107 for(int i=co;i<33;i++) c[i]=0;108 v[0].next[0]=v[0].next[1]=-1;109 v[0].num=0;110 vNum=1;111 ans=0;112 k=ttt;113 for(int i=1;i<=n;i++)114 {115 add(w[i]);116 if(w[i]>=k) ans++;117 }118 printf("%I64d\n",ans);119 }120 return 0;121 }
CodeForces 665E Beautiful Subarrays
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。