Dashboard – 2022 Shanghai Collegiate Programming Contest – Codeforces
A. Another A+B Problem
题意：给出一个表达式 xx+xx=xx的格式，然后每个位置有三种字母表示三种状态，G表示这个位置的字母在答案中存在并且位置相同，P表示这个位置的字母在答案中存在但并不在这个位置，B表示这种字符在答案中不存在，或者存在与答案中数目相同的颜色不为B的位置，问有多少不同的答案。
题解: 模拟，如果为G就不管直接加上，如果为P，用一个sum计数器存储一下，表示最少有sum个数要使用掉，并且记录当前位置，保证这个数不能在这个位置出现，如果B，表示这个数不会出现，或者最多出现sum次+G出现的次数，所以按照前面的方式模拟，保证使用次数不超过sum即可，最后判断所有的sum是不是都<=0。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const ll N=2e5+5; const ll inf=1e18; ll n,m; ll dp[N][102]; string s,p; ll vis[20]; unordered_map<char,ll> sum,mp; set<string> ans; vector<ll> q[N]; void dfs(ll th,string l){ if(th==2){ dfs(th+1,l+'+'); return ; } if(th==5){ dfs(th+1,l+'='); return ; } if(th==8){ string x=""; x+=l[0];x+=l[1]; string y=""; y+=l[3];y+=l[4]; string z=""; z+=l[6];z+=l[7]; for(ll i=0;i<=9;i++){//判断所有sum是否都<=0，即是不是把所有的p都使用掉了 if(sum[i+'0']>0) return; } if((atoi(x.c_str())+atoi(y.c_str()))==atoi(z.c_str())){//判断这个表达式是否成立 ans.insert(l); } return ; } if(vis[th]==1){//G直接加上即可 dfs(th+1,l+s[th]); return ; } for(ll i=0;i<=9;i++){ char c='0'+i; if(mp[c]==-1){//如果i存在某个位置为B并且sum<=0，那么就不能再使用了 if(sum[c]<=0) continue; } bool flag=0; for(ll j=0;j<q[i].size();j++){//找到合法的位置 if(q[i][j]==th){ flag=1; } } if(!flag){ sum[c]--; dfs(th+1,l+c); sum[c]++; } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>s>>p; for(ll i=0;i<p.size();i++){ if(p[i]=='G') vis[i]=1; else if(p[i]=='P'){ sum[s[i]]++; q[s[i]-'0'].push_back(i); } else{ mp[s[i]]=-1; q[s[i]-'0'].push_back(i);//注意这里，B的位置也不能走 } } dfs(0,""); cout<<ans.size()<<endl; set<string>::iterator it; for(it=ans.begin();it!=ans.end();it++){ cout<<*it<<endl; } }
E. Expenditure Reduction
题意: 给出两个字符串a , b，在前面的字符串中找一个字串S，保证S的一个子序列是b，找出最短的S。
题解: dp，dp[i][j]表示在a中（1-i）范围内含有（1-j）的b的子序列的最短字串。
dp[i][j]=dp[i-1][j]+1 //每一项都是前一项+1 if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1)//相同情况下
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=2e5+5; const ll inf=1e18; ll n,m; ll dp[N][102]; char p[N],q[N]; signed main(){ ios::sync_with_stdio(false); cin.tie(0); ll t;cin>>t; while (t--){ cin>>p+1>>q+1; ll len1=strlen(p+1); ll len2=strlen(q+1); for(ll i=0;i<=len1;i++) for(ll j=1;j<=len2;j++){//给每个位置附上一个最大值len1+1; dp[i][j]=len1+1; } dp[0][0]=0;//初始化第一个位置 for(ll i=1;i<=len1;i++) for(ll j=1;j<=len2;j++){ dp[i][j]=dp[i-1][j]+1; if(p[i]==q[j]){//相同的时候 dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1); } } ll pos=1,ans=len1+1; for(ll i=1;i<=len1;i++){//找出最小字串 if(dp[i][len2]<ans){ ans=dp[i][len2];pos=i; } } for(ll i=pos-ans+1;i<=pos;i++) cout<<p[i]; cout<<endl; } } /* 1 paiiipeaded paed */
H. Heirloom Painting
题意: 给一个长度为n的环，每次只能连续选择k个位置，将其涂成相同的颜色，问最少几次能涂成给出字符串的形式，如果不能输出 ‘-1’
题解: 如果一段连续的颜色相同的方块，他的长度<k,那么它一定会影响到别的方块，如何抵消掉这种影响，就必须保障，有一段连续的，他的长度>=k,这样它可以晚涂，覆盖掉别的方块对它的影响，而又不影响别的位置，所以每段连续的向上除，然后判断有没有>=k的位置。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const ll N=2e5+5; const ll inf=1e18; signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll t;cin>>t; while(t--){ ll n,m,k;cin>>n>>m>>k; vector<ll> a(n+1,0); bool flag=0; for(ll i=1;i<=n;i++){ cin>>a[i]; } ll sum=0; ll ans=0; ll la=0; ll end=n; ll le=1; while(a[end]==a[1]&&end!=1){//这个是找出第一个字符的连续长度，因为是环，最后一个字符与第一个可能相同，也要加上去 le++; end--; } for(ll i=1;i<=end;i++){ ll j=i+1; while(a[j]==a[i]&&j<=end){ le++;j++; } ll p=(le+k-1)/k;//求出需要几次 if(le>=k) flag=1;//判断有没有>=k的片段 ans+=p; la=i; le=1; i=j-1; } if(!flag) cout<<"-1"<<endl; else cout<<ans<<endl; } }
原文地址：http://www.cnblogs.com/hhzp/p/16783937.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
