2小时6道题，所以请记住，对于cf比赛，犹豫就会败北，果断就会白给
CF1155A Reverse a Substring
如果字符大小非严格单增，显然无解，如果出现前面字符大于后面的字符的情况，输出它们的位置即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include<bits/stdc++.h> using namespace std; int n;string str; int main(){ cin>>n>>str;char last=str[0];int pos=0; for(int i=1;i<str.length();i++){ if(last==str[i]){pos=i;continue;} if(last<str[i]){last=str[i];pos=i;} else { printf("YES\n%d %d",pos+1,i+1); return 0; } } printf("NO"); return 0; } |
CF1155B Game with Telephone Numbers
一开始还以为是博弈论（我傻了）……结果一个简单的贪心就OK了
一轮游戏会将数字取到只剩11个，如果序列中前 n-10 个元素中，8的数量大于其他的数量，那么显然先手会把其中不是8的取完，先手必胜。如果不大于，后手会把所有的8取完，先手必败。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include<bits/stdc++.h> using namespace std; int n;int a[100005]; int main(){ cin>>n;int cnt=0; for(int i=1;i<=n;i++)scanf("%1d",&a[i]); for(int i=1;i<=n-10;i++){ if(a[i]==8)cnt++; else cnt--; } if(cnt>0)printf("YES\n"); else printf("NO\n"); return 0; } |
CF1155C Alarm Clocks Everywhere
我们要找到一个 x和d 使得 x+kd = a_i k为正整数
如果我们的时间累积到 a_i 了，那么我们其实就是要满足 a_i+kd=a_{i+1} 即 a_{i+1}-a_i=kd
所以我们就是要用一个间隔来遍历到所有时间点，这个间隔显然是所有相邻时间间隔的gcd，记为d
然后看看第二行里面有没有d的约数，有的话就输出
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=300003; int n,m; ll x,d,z; ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; } int main(){ scanf("%d%d",&n,&m); scanf("%lld",&x); for (int i=1;i<n;i++) { scanf("%lld", &z); d=gcd(d,abs(z-x)); } for(int i=1;i<=m;i++){ ll p;cin>>p; if(d%p==0){ printf("YES\n%lld %d",x,i); return 0; } } printf("NO"); return 0; } |
CF1155D Beautiful Array
其实就是最长连续子串的变形。
| 变量名 | 变量作用 |
|---|---|
| $s$ | $s_i$ 表示整个序列乘上 $x$ 后的前缀和 |
| $L$ | $L_i$ 表示 $i$ 位置往前的最大连续子串和 |
| $R$ | $R_i$ 表示 $i$ 位置往后的最大连续子串和 |
假如我们选择了 i 到 j (j\le i) 这一段乘上 x 那么答案就为 s[i]-s[j-1]+R[i+1]+L[j-1]
我们可以枚举 s[i]+R[i+1] ，用 max(L[j-1]-s[j-1]) 来更新答案
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[300005]; ll s[300005],L[300005],R[300005]; int main() { int n;ll x; cin>>n>>x; ll ans=0; for (int i=1; i<=n; i++) {cin>>a[i];ans+=a[i];s[i]=x*a[i];s[i]+=s[i-1];} ans=max(ans,0LL); for (int i=1; i<=n; i++) L[i]=max(L[i-1]+a[i],0LL); for (int i=n; i>=1; i--) R[i]=max(R[i+1]+a[i],0LL); ll mx=-1LL<<62; for (int i=1; i<=n; i++) { mx=max(mx,L[i-1]-s[i-1]); ans=max(ans,R[i+1]+s[i]+mx); } cout<<ans<<endl; return 0; } |