)
A. You Delete, I Delete
地址跳转
赛时代码：
#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){string s;cin>>s;boolf1=1,f2=1;for(inti=0;i<s.size();i++){if(s[i]=='1'&&f1){f1=0;s[i]='A';}if(s[i]=='0'&&f2){f2=0;s[i]='A';}}string ans="";for(inti=0;i<s.size();i++)if(s[i]=='A')continue;elseans+=s[i];cout<<ans<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}Alice删0使字典序最大
Bob删1使字典序最小
最后剩下的位数是相同的，
删去最前面的0，后面的1会前进一位
删去最前面的1，前排会少一位1
所以Alice和Bob的最优策略都是删掉最前面的0和1
一边找一边输出
关闭输入输出流后，不要用putchar函数
boolc0=0,c1=0;for(inti=0;i<s.size();i++){if(!c0&&s[i]=='0'){c0=1;continue;}if(!c1&&s[i]=='1'){c1=1;continue;}cout<<s[i];}cout<<endl;题解代码：
#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){string s;cin>>s;intn=s.size();s=" "+s;boolc0=0,c1=0;for(inti=1;i<=n;i++){if(!c0&&s[i]=='0'){c0=true;continue;}if(!c1&&s[i]=='1'){c1=true;continue;}cout<<s[i];}cout<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}B. Merge to Match
地址跳转
如果a数组的数字都变成b数组的数字后还剩余很多数
这些数可以找任意一个数结合，删掉
对于b数组中的每个数
需要在a数组中有一个比它大的数和一个比它小的数才可以变出来
找比b数组小的数字是否够用
sort(a.begin()+1,a.end());sort(b.begin()+1,b.end());intl=1;for(inti=1;i<=m;i++){if(a[l]<b[i]&&l<=n)l++;else{cout<<"NO"<<endl;return;}}找比b数组大的数字是否够用
l--;intr=n;for(inti=m;i;i--){if(a[r]>b[i]&&r>l)r--;else{cout<<"NO"<<endl;return;}}cout<<"YES"<<endl;赛时代码：
#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;intn,m;voidsolve(){cin>>n>>m;vector<int>a(n+1),b(m+1);for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<=m;i++)cin>>b[i];sort(a.begin()+1,a.end());sort(b.begin()+1,b.end());intl=1;for(inti=1;i<=m;i++){if(a[l]<b[i]&&l<=n)l++;else{cout<<"NO"<<endl;return;}}l--;intr=n;for(inti=m;i;i--){if(a[r]>b[i]&&r>l)r--;else{cout<<"NO"<<endl;return;}}cout<<"YES"<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}C. Maximize the Score
地址跳转
设dp[i]表示前i位能产生分数的最大值
状态转移：
dp[i]=dp[i-1]+1;
dp[i]=dp[pos-1]+(i-pos+1)*(i-pos+1)
pos是第i位的数字上一次出现的位置
标记每一位数字第一次出现的位置
vector<int>vis(n+1);for(inti=1;i<=2*n;i++){intx=a[i];if(!vis[x])vis[x]=i;}根据状态转移写dp
for(inti=1;i<=2*n;i++){intx=a[i];intj=vis[x];dp[i]=max(dp[i-1]+1,dp[j-1]+(i-j+1)*(i-j+1));}cout<<dp[2*n]<<endl;赛时代码：
#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;intn;voidsolve(){cin>>n;vector<int>a(2*n+1);for(inti=1;i<=2*n;i++)cin>>a[i];vector<int>dp(2*n+1),vis(n+1);for(inti=1;i<=2*n;i++){intx=a[i];if(!vis[x])vis[x]=i;}for(inti=1;i<=2*n;i++){intx=a[i];intj=vis[x];dp[i]=max(dp[i-1]+1,dp[j-1]+(i-j+1)*(i-j+1));}cout<<dp[2*n]<<endl;return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}D. Good Pair Queries
地址跳转
01表示a[i]=0,b[i]=1;
10表示a[i]=1,b[i]=0;
00和11很容易删掉
主要问题是处理01和10
min(cnt01,cnt10)容易删掉，让他们结合就行
如果cnt01<cnt10
多出来的cnt10必须和00或11结合才能删掉
此时剩余的cnt10的数量必须小于等于00 11和的数量
cnt10<=m/2
同理cnt01<=m/2
统计一下前缀01和10的数量
string a,b;cin>>a>>b;a=" "+a;b=" "+b;vector<int>p1(n+1),p2(n+1);for(inti=1;i<=n;i++){p1[i]=p1[i-1]+(a[i]=='0'&&b[i]=='1');p2[i]=p2[i-1]+(a[i]=='1'&&b[i]=='0');}对于每次询问，利用前缀和求出
区间内01和10的数量，进行判断
while(q--){intx,y;cin>>x>>y;intm=y-x+1;intc1=p1[y]-p1[x-1];intc2=p2[y]-p2[x-1];if(c1*2<=m&&c2*2<=m)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}赛时代码：
#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;intn,q;voidsolve(){cin>>n>>q;string a,b;cin>>a>>b;a=" "+a;b=" "+b;vector<int>p1(n+1),p2(n+1);for(inti=1;i<=n;i++){p1[i]=p1[i-1]+(a[i]=='0'&&b[i]=='1');p2[i]=p2[i-1]+(a[i]=='1'&&b[i]=='0');}while(q--){intx,y;cin>>x>>y;intm=y-x+1;intc1=p1[y]-p1[x-1];intc2=p2[y]-p2[x-1];if(c1*2<=m&&c2*2<=m)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intt;cin>>t;while(t--)solve();return0;}
