https://codeforces.com/contest/1323
A. Even Subset Sum Problem.
数据范围只有100，两个for暴力枚举一遍，记录满足题意的区间左右端点即可。最后输出。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 105; 5 ll a[maxn]; 6 int main(){ 7 int t;cin>>t; 8 while(t--){ 9 int n;cin>>n; 10 for(int i = 1;i<=n;i++) cin>>a[i]; 11 int sum = 0, l = -1, r = -1;//满足条件区间的左右端点 12 for(int i = 1;i<=n;i++){ 13 int tmp = a[i]; 14 if(tmp%2 == 0) l = r = i; 15 for(int j = i + 1;j<=n;j++){ 16 tmp+=a[j]; 17 if(tmp%2 == 0) l = i,r = j;//如果满足和是偶数就记录 18 } 19 20 } 21 if(l!=-1 && r!=-1) sum = r - l + 1; 22 else{ 23 cout<<-1<<endl;continue; 24 } 25 cout<<sum<<endl; 26 for(int i = l;i<=r;i++) cout<<i<<" "; 27 cout<<endl; 28 } 29 return 0; 30 }
B. Count Subrectangles
由于需要考虑满足面积 = k的长方形，那么长方形的长和宽必定是k的因子了。考虑行，比如行数组是 1 1 1 1 0 0 1 1 1，那么遍历的时候统计连续 x 个1的个数（1<=x <= n），连续2个1的个数..连续3个1的个数....连续n个1的个数，统计进map里面。同样地再把列连续的1统计进去，最后发现行连续的1可以作为长方形的一边，列连续的1可以作为长方形的另一边，两者相乘判断一下是否等于k，把两者个数相乘加入答案中即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 4e4+5; 5 ll r[maxn],c[maxn]; 6 ll dpR[maxn],dpC[maxn],Rer[maxn],Rec[maxn]; 7 int n,m,k; 8 int main(){ 9 cin>>n>>m>>k; 10 for(int i = 1;i<=n;i++) cin>>r[i]; 11 for(int j = 1;j<=m;j++) cin>>c[j]; 12 for(int i = 1;i<=n;i++) if(r[i] == 1) dpR[i] = dpR[i-1]+1;//行连续1 13 for(int i = 1;i<=m;i++) if(c[i] == 1) dpC[i] = dpC[i-1]+1;//列连续1 14 for(int i = n;i>=1;i--) if(r[i] == 1) Rer[i] = Rer[i+1]+1;//倒着遍历统计出连续长度为x的个数 15 for(int i = m;i>=1;i--) if(c[i] == 1) Rec[i] = Rec[i+1]+1;//同理统计列 16 map<int,int> mR,mC; 17 for(int i = 1;i<=n;i++) mR[dpR[i]]+=Rer[i];//把答案加入map中去 18 for(int j = 1;j<=m;j++) mC[dpC[j]]+=Rec[j];// 19 // 20 ll ans = 0; 21 for(int i = 1;i<=n;i++){ 22 if(mR[i]!=0 && k%i == 0 ) {//遍历行，假设一条边长度为i，如果k%i==0,可以作为一条边 23 int sear = k/i;//算出另一条边的长度 24 ans+=(mC[sear]*mR[i]);//满足两条边的连续1的个数相乘就是一部分贡献，累加全部的贡献即可 25 } 26 } 27 cout<<ans; 28 return 0; 29 }
C. Unusual Competitions
这一题比较套路了，括号题可以考虑前缀和做。遍历字符串，如果第i个字符为' (' 那么让前缀和-1，如果为 ')' ，前缀和+1。最终前缀和为0才可以修正为正常序列，否则输出-1.
考虑前缀和中间段出现0的情况。" ))(( " ，例如这个字符串，在第4个位置时前缀和是0，那么判断该位置前一项的前缀和是否为负数，如果是负数则表明出现了不合法情况，那么把这段子串修正即可，如果为正数只能是 “ (()) ”这种情况，这种情况是合法的，不用管。注意每次去更新不合法子串的左端点。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e6+5; 5 ll f[maxn]; 6 int n; 7 int main(){ 8 int n;cin>>n; 9 string s;cin>>s; 10 for(int i = 1;i<=n;i++){ 11 if(s[i-1] == '(') f[i] = f[i-1] + 1;//处理前缀和 12 else f[i] = f[i-1] - 1; 13 } 14 int ans = 0; 15 if(f[n] != 0) { 16 cout<<-1;return 0; 17 } 18 int indx = 1;//假设不合法子串的左端点位indx 19 for(int i = 1;i<=n;i++){ 20 if(f[i] == 0 && i!=1 && f[i-1] < 0){ 21 ans +=(i-indx+1);//i-indx+1就是不合法子串长度 22 } 23 if(f[i] == 0) indx = i+1;//更新左端点 24 } 25 cout<<ans; 26 return 0; 27 }
D. Present
这次D题比较难想，状态压缩再用二分优化一下能做。题解很不好写，挂个英文题解方便回顾。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 4e5+5; 5 int a[maxn],b[maxn]; 6 int n; 7 int main(){ 8 scanf("%d",&n); 9 int ans = 0; 10 for(int i = 1;i<=n;i++) scanf("%d",&a[i]); 11 for(int i = 0;i<25;i++){ //最多25位 12 for(int j = 1;j<=n;j++) b[j] = a[j]%(1<<(i+1)); 13 sort(b+1,b+1+n); 14 for(int j = 1;j<=n;j++){ 15 int l = max(0,(1<<i)-b[j]);//第一段区间的左端点 16 int r = ( (1<<(i+1) ) - 1) - b[j] ;//第一段区间的右端点 17 int range = upper_bound(b+1,b+j,r)-lower_bound(b+1,b+j,l); 18 if(range&1) ans^=(1<<i); 19 l = max(0,( (1<<(i+1)) +(1<<i)-b[j] ) ); 20 r = ( (1<<(i+2)) -1)-b[j]; 21 range = upper_bound(b+1,b+j,r)-lower_bound(b+1,b+j,l); 22 if(range&1) ans^=(1<<i); 23 } 24 } 25 printf("%d",ans); 26 return 0; 27 }