目录

A - String Similarity

B - RPG Protagonist

C - Binary String Reconstruction

D - Zigzags

---

A - String Similarity

思维，只需要对每个字串依次提取一个字符组成目标字符即可；

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int t;cin >>t; while(t--) { int n; cin >>n; n=n*2-1; string s; cin >>s; for(int i=0;i<n;i++) if(i%2==0) cout <<s[i]; cout <<endl; } }

B - RPG Protagonist

 B放了个1700的题.......

第一眼以为是个背包，一看数据gg；正确思想是贪心+枚举：

首先肯定是先买s和w中最小的 (假设是s) ；枚举p能买s的个数，对应每一个个数状态计算先买s后剩下的钱买w；之后，f也同样先买s，剩下的钱买w

#include <bits/stdc++.h> using namespace std; typedef long long ll; int ans,p,f,cnts,cntw,s,w; void get() { int x=min(p/s,cnts); //cout <<"x"<<" "<<x<<endl; // int y=min((p-x*s)/w,cntw); // int z=min(p/(s+w)*2+(p-(p/(s+w)*(s+w)))/s,min(cnts,cntw)*2+) // //cout <<x<<" "<<y<<endl; // if(x+y>=min(p/(s+w)*2,min(cnts,cntw)*2)+) ans+=x+y,cnts-=x,cntw-=y; // else if(cnts>=p/(s+w)) cnts-=p/(s+w),cntw-=p/(s+w),ans+=p/(s+w)*2; // //cout <<ans<<" ans"<<endl; for(int i=0;i<=x;i++) { int cntss=cnts,cntww=cntw; int sum=0; sum+=i+min((p-i*s)/w,cntww); cntss-=i,cntww-=min((p-i*s)/w,cntw); //cout <<cntss<<" "<<cntww<<endl; sum+=min(cntss,f/s)+min((f-min(cntss,f/s)*s)/w,cntww); ans=max(sum,ans); } } int main() { int t;cin >>t; while(t--) { ans=-0x3f3f3f3f; cin >>p>>f>>cnts>>cntw>>s>>w; if(s>w) swap(s,w),swap(cnts,cntw); get(); cout <<ans<<endl; } }

C - Binary String Reconstruction

目前还在WA；但是思路感觉没问题...

思路：先初始化w数组都为1，然后根据s中0的位置，更新w中0的位置；

之后，根据w数组求出s数组，看是否和原始s数组相同即可；

wa代码：原因是没处理  && 的情况，此时=0

#include <bits/stdc++.h> using namespace std; typedef long long ll; char s[100005],w[100005],temp[100005]; int main() { int t; cin >>t; while(t--) { int f=1; cin >>s+1; int x;cin >>x; int n=strlen(s+1); for(int i=1;i<=n;i++) w[i]='1',temp[i]='1'; for(int i=1;i<=n;i++) { if(i<=x&&s[i]=='0') w[i+x]='0'; else if(i+x>n&&s[i]=='0') w[i-x]='0'; else if(s[i]=='0') w[i+x]='0',w[i-x]='0'; } // for(int i=1;i<=n;i++) cout <<w[i]; // cout<<endl; for(int i=1;i<=n;i++) { if(i<=x) temp[i]=w[i+x]; else if(i+x>n) temp[i]=w[i-x]; else temp[i]=(w[i+x]-'0')|(w[i-x]-'0')+'0'; } // for(int i=1;i<=n;i++) cout <<temp[i]; // cout<<endl; for(int i=1;i<=n;i++) { if(s[i]!= temp[i]) {f=0;break;} } if(f) {for(int i=1;i<=n;i++) cout <<w[i];cout <<endl;} else puts("-1"); } }

AC代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; char s[100005],w[100005],temp[100005]; int main() { int t; cin >>t; while(t--) { int f=1; cin >>s+1; int x;cin >>x; int n=strlen(s+1); for(int i=1;i<=n;i++) w[i]='1',temp[i]='0'; for(int i=1;i<=n;i++) { if(i+x>n&&i-x<=0) continue; if(i<=x&&s[i]=='0') w[i+x]='0'; else if(i+x>n&&s[i]=='0') w[i-x]='0'; else if(s[i]=='0') w[i+x]='0',w[i-x]='0'; } // for(int i=1;i<=n;i++) cout <<w[i]; // cout<<endl; for(int i=1;i<=n;i++) { if(i+x>n&&i-x<=0) continue; if(i<=x) temp[i]=w[i+x]; else if(i+x>n) temp[i]=w[i-x]; else temp[i]=((w[i+x]-'0')|(w[i-x]-'0'))+'0'; } // for(int i=1;i<=n;i++) cout <<temp[i]; // cout<<endl; for(int i=1;i<=n;i++) { if(s[i]!= temp[i]) {f=0;break;} } if(f) {for(int i=1;i<=n;i++) cout <<w[i];cout <<endl;} else puts("-1"); } }

 

D - Zigzags

思路：枚举  j  和  k  的位置，那么i只能在（1,j）中选择， l只能在 (k,n） 中选择；然后统计每个区间中每个数字出现次数的前缀和；利用乘法原理求解即可；

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[3005],sum[3005][3005]; int main() { int t; cin >>t; while(t--) { int n; cin >>n; for(int i=1;i<=n;i++) { cin >>a[i]; for(int j=1;j<=n;j++) sum[i][j]=sum[i-1][j]; sum[i][a[i]]++; } ll ans=0; for(int j=2;j<=n-2;j++) { for(int k=j+1;k<=n-1;k++) { ans+=(sum[j-1][a[k]])*(sum[n][a[j]]-sum[k][a[j]]); } } cout <<ans<<endl; } }