比赛链接:https://codeforc.es/contest/1722
在学校里,一直没时间参赛。
在D题上出现了比较大的问题。把题拆开来考虑结果导致有些麻烦。
前三题中规中矩吧,基本一次过,题并不是很难
A题:大意是有个人叫Timur,对于他名字的任意排列都是对的。求输出的字符串是否正确。直接map存
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } map<char,int>mp; void solve() { mp.clear(); int n; cin>>n; string a; cin>>a; if(n!=5) cout<<"NO"<<endl; else { for(int i=0;i<n;i++) mp[a[i]]=1; if(mp['T']==1&&mp['i']==1&&mp['m']==1&&mp['r']==1&&mp['u']==1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
B题:大意是给出2行n列的字符串,也就是两个串。每个字符有三种颜色,R, G, or B,,其中G和B不能被识别。因为眼盲,所以求出这个人看这两个字符串是否是一样的。
直接两两比较每一个字符,如果存在一个r,那么另一个必定要是r,否则直接no
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void solve() { int n; cin>>n; string a,b; cin>>a>>b; int i=0; for(;i<a.size();i++) { if(a[i]=='R'&&b[i]!='R'||b[i]=='R'&&a[i]!='R') break; } if(i<a.size()) cout<<"NO"<<endl; else cout<<"YES"<<endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
C题:大意是有三个人,每个人给出n个字符串。如果有一个字符串出现了一次,那个人+3分,出现了两次,两人分别+1分,出现了3次不加分。
思路:直接map存储每个字符串出现的次数,这里最开始想用set结果set.count()并不能很好的识别字符串出现的数量,所以用map来存的。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } vector<string> ve[4]; map<string,int> mp; void solve() { for(int i=0;i<4;i++) ve[i].clear(); mp.clear(); int n; cin>>n; for(int i=1;i<=3;i++) { for(int j=0;j<n;j++) { string c; cin>>c; ve[i].push_back(c); mp[c]++; } } int num[4]={}; for(int i=1;i<=3;i++) { for(int j=0;j<ve[i].size();j++) { if(mp[ve[i][j]]==1) num[i]+=3; else if(mp[ve[i][j]]==2) num[i]+=1; } } for(int i=1;i<=3;i++) printf("%d%c",num[i],i==3?'\n':' '); } int main() { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
D题:大意是给出一个字符串,每个元素都是L或者R,如果是L它的值就是它左边元素的数量,如果是R,它的值就是它右边元素的数量。你可以通过操作N次改变使得和s最大,每次k对应1-n,输出每一次的最大和s。
思路:很明显的一个贪心题,如果它在左边,那么它为R才能值最大,右边亦然。贪心的看待每一个逆向L或R,离边界越近的优先改变。ve存储它离边界的距离,然后直接计算出另一侧。这个题最开始的操作并不是很好,把题的左右拆开然后用的双指针做的。其实可以把右边靠右的边界转换为左边靠左的边界,然后直接排序来做。网上的答案比我写的更精简一些,计算上更加简洁。
my code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void solve() { int n; cin>>n; string a; cin>>a; ll sum = 0; vector<int> ve; for(int i=0;i<a.size();i++) if(a[i]=='L') sum+=i; else if(a[i]=='R') sum+=n-i-1; if(n%2) { for(int i=0;i<n/2;i++) if(a[i]=='L') ve.push_back(i); for(int i=n/2+1;i<n;i++) if(a[i]=='R') ve.push_back(n-i-1); }else { for(int i=0;i<n/2;i++) if(a[i]=='L') ve.push_back(i); for(int i=n/2;i<n;i++) if(a[i]=='R') ve.push_back(n-i-1); } sort(ve.begin(),ve.end()); int p=0; for(int i=1;i<=n;i++) { if(p<ve.size()) sum-=ve[p],sum+=(n-ve[p]-1); p++; cout<<sum<<' '; } cout<<endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
Internet code:
#include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; string s; cin>>s; int d[n]; long long c=0; for(int i=0;i<n;i++){ if(s[i]=='L')d[i]=i; else d[i]=n-1-i; c+=d[i]; } sort(d,d+n); for(int i=0;i<n;++i){ if(n-1-2*d[i]>0)c+=n-1-2*d[i]; cout<<c<<" "; } cout<<endl; }}