题目链接:https://codeforc.es/contest/1702
这次比赛赛题比较简单,很多题感觉可以用stl巧做。另外感觉有必要学习一下stl容器的一些设置的规则 ,stl是有必要深入学习一下的。这次比赛A了四个题,有两个题用map巧做的,一个题是用了set。map嘛很多时候是可以当哈希来用的,而且还可以设置key值对应结构体val。
A题:就是给出个数,然后让求出不超过这个数的10的幂次方。刚开始想用log来O(1)做,但是其实可以直接循环。
code:
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { long long x; cin>>x; long long f=1; while(f<=x) f*=10; f/=10; cout<<x-f<<endl; } }
B题:给出一个字符串,每天可以学习连续的字母,字母类别不超过三个。多少天能学完
#include<bits/stdc++.h> using namespace std; map<char,int>mapt; int main() { int t; cin>>t; while(t--) { string a,b; cin>>a; b=a; sort(b.begin(),b.end());// nlogn int p,sum=0; scanf("%d",&p); int i=0; while(sum<=p&&i!=a.size())//nlogn { sum+=b[i]-96; mapt[b[i]]++; i++; } if(sum>p) { i--; mapt[b[i]]--;//消除一个 } for(int j=0;j<a.size();j++) { if(mapt[a[j]]>0) { printf("%c",a[j]); mapt[a[j]]--; } } printf("\n"); } }
解决方法:可以用指针指向来控制学习的元素,循环内巧用set来对每天的进行判重。贪心思想学到第四个之前为止。
code:
#include<bits/stdc++.h> using namespace std; set<char>se; int main() { int t; cin>>t; while(t--) { se.clear(); string a; cin>>a; int i=0; int day =0; while(i!=a.size()) { se.clear(); while(1) { se.insert(a[i++]); if(i==a.size()||se.size()==3&&se.count(a[i])==0) break; } day++; } cout<<day<<endl; } }
C题:给出一堆数(可能有重复),询问两个数a b,问a能否到达b,只能顺序到达。
解决方案:用map做伪哈希,存储一个数的最低位次和最高位次,当这个数为a时,用最低位次来判断到b的最高位次。这个有个贪心的思想在里面。
code:
#include<bits/stdc++.h> using namespace std; const int nn = 2*1e5+20; struct posison{ int mint=nn; int maxt=0; }; map<int,posison>mp; int main() { int t; cin>>t; while(t--) { mp.clear(); int n,k,x; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&x); if(mp[x].mint>i) mp[x].mint=i; if(mp[x].maxt<i) mp[x].maxt=i; } int a,b; while(k--) { scanf("%d%d",&a,&b); if(mp[a].mint>mp[b].maxt) printf("NO\n"); else printf("YES\n"); } } }
D题:大意就是给出个字符串,令a=1,b=2,直到z,给出一个数p,我们可以删除某些字符,使得字符串的sum<=p,求最少操作数。
解决方法:排序,然后map记录保留字符的数量。
code:
#include<bits/stdc++.h> using namespace std; map<char,int>mapt; int main() { int t; cin>>t; while(t--) { string a,b; cin>>a; b=a; sort(b.begin(),b.end());// nlogn int p,sum=0; scanf("%d",&p); int i=0; while(sum<=p&&i!=a.size())//nlogn { sum+=b[i]-96; mapt[b[i]]++; i++; } if(sum>p) { i--; mapt[b[i]]--;//消除一个 } for(int j=0;j<a.size();j++) { if(mapt[a[j]]>0) { printf("%c",a[j]); mapt[a[j]]--; } } printf("\n"); } }