比赛链接:https://codeforces.ml/contest/1744
第一次排名挺高,到了2500+,也是如愿的在定级赛内要上绿了。这次比赛E题的构造题听恶心的,其他发挥的还可以,C题稍微有些失误但不多,还是有些需要注意的点。构造题单独总结一下。
A题:水题,主要是哈希的应用
B题:奇偶数问题,大意是给出一堆数,给出两种操作,令偶数+x或令奇数+x,每次操作后输出所有数的和。
直接分别计算。
C题:WA了两发,需要考虑的情况还是挺多的。给出一个字符串,包含ryb,红绿黄灯。给出现在的灯,求最少需要等多长时间,可以等到下一个绿灯且保证等到。 规律循环。
我们可以每次记录目前的灯到下一个灯的时间,这个只需要遍历一下。
另一边,我们总能通过,最后末尾没有绿的时候的目前灯,到达下一次循环的绿灯。这里比较细节。(第一次考虑的时候是考虑的最后的目前的,没有想到l绿灯问题)(第二次考虑的时候,忘记了遇不到灯的情况,即绿之后再无此灯)
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; char c; scanf("%d %c",&n,&c); string s; cin>>s; int maxt = -1; int cur = -1; int mopos = -1; for(int i=0;i<s.size();i++){ if(s[i]==c&&cur==-1){ cur = i; } if(cur!=-1&&s[i]=='g'){ maxt = max(maxt,i-cur); cur = -1; } } for(int i=s.size()-1;i>=0;i--){ if(s[i]==c) mopos = i; if(s[i]=='g') break; } if(mopos!=-1){ s+=s; for(int i=mopos;i<s.size();i++){ if(s[i]=='g'){ maxt = max(maxt,i-mopos); break; } } } cout<<maxt<<endl; } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n') //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
D题:给出一堆数,可以使这些数乘以i,求至少多少次这样的操作可以使得乘积 可以 整除2^n。每个位置只能操作一次。不能到达-1.
这个题做的也挺顺利。记录当前数的因子中含有多少个2,然后从大到小考虑i含有多少个2。然后比较,然后从大到小应用操作。
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; } // 2 4 8 16 32 64 12 11 10 bool cmp(int a,int b){ return a>b; } const int nn = 2*1e5+10; void solve() { vector<int> ve; int n; cin>>n; int x; int sum = 0; int tsum = 0; for(int i=1;i<=n;i++){ cin>>x; while(x%2==0){ sum++; x/=2; } int tx = i; int ff = 0; while(tx%2==0){ ff++; tsum++; tx/=2; } ve.push_back(ff); } if(sum+tsum<n) cout<<-1<<endl; else{ sort(ve.begin(),ve.end(),cmp); int ans = 0; int tn = n-sum; for(int i=0;i<ve.size();i++){ if(tn<=0) break; tn-=ve[i]; ans++; } cout<<ans<<endl; } } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n') ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }