Codeforces Edu Round 63 A-E

缺乏、安全感 2021-10-19 04:12 286阅读 0赞

#### A. Reverse a Substring ####

容易看出，只要符合递增顺序就符合\\(NO\\)，否则则可以找到一组，每次记录最大值比较即可。

#include <cstdio> #include <iostream> using namespace std; const int N = 300010; int n; char s[N]; int main(){ scanf("%d%s", &n, s + 1); int maxn = s[1], k = 1; for(int i = 2; i <= n; i++){ if(s[i] < maxn){ printf("YES\n%d %d\n", k, i); return 0; } if(s[i] > maxn){ maxn = s[i]; k = i; } } printf("NO\n"); return 0; }

#### B. Game with Telephone Numbers ####

\\(Vasya\\)用尽所有轮次可以把几个\\(8\\)扔到最前面，只要这个数大于轮次，就说明\\(Petya\\)无法逆天改命。

#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int N = 100010; int n; char s[N]; int main(){ scanf("%d%s", &n, s + 1); int round = (n - 11) >> 1; int cnt = 0; for(int i = 1; i <= round && round <= n; i++){ if(s[i] == '8')cnt++, round ++; } int i = round + 1; while(s[i] == '8' && i <= n) i++, cnt++; if(cnt > (n - 11) >> 1) puts("YES"); else puts("NO"); return 0; }

#### C. Alarm Clocks Everywhere ####

显然，y设置为\\(x\[1\]\\)即可，因为即使设置在之前，还是要经过\\(x\[1\]\\)，还是以\\(p\\)往上跳，是没有区别的。

我们只要找到一个\\(p\_j\\)，使其满足\\(p\_j | a\[i + 1\] - a\[i\] (1 <= i < n)\\)。（整除的意思）

#include <cstdio> #include <iostream> using namespace std; typedef long long LL; const int N = 300010; int n, m; LL x[N], p[N]; LL gcd(LL a, LL b){ return b ? gcd(b, a % b) : a; } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%lld", x + i); for(int i = 1; i <= m; i++) scanf("%lld", p + i); LL ans = x[2] - x[1]; for(int i = 2; i < n; i++) ans = gcd(ans, x[i + 1] - x[i]); for(int i = 1; i <= m; i++){ if(ans % p[i] == 0){ printf("YES\n%lld %d\n", x[1], i); return 0; } } printf("NO"); return 0; }

#### D. Beautiful Array ####

想到了对数列总和最大贡献，但是其实最大贡献不一定能最大化答案，于是惨遭\\(WA10\\)。

\\(WA\\)炸代码：

#include <cstdio> #include <iostream> #include <cmath> using namespace std; const int N = 300010, INF = 2147483647; typedef long long LL; int n, x, L[N]; LL a[N], f[N]; int main(){ scanf("%d%d", &n, &x); for(int i = 1; i <= n; i++) scanf("%lld", a + i); if(x < 0){ f[1] = a[1]; L[1] = 1; LL minn = f[1]; int k = 1; for(int i = 2; i <= n; i++) { if(f[i - 1] + a[i] < a[i]){ L[i] = L[i - 1]; f[i] = f[i - 1] + a[i]; }else{ L[i] = i; f[i] = a[i]; } if(f[i] < minn){ minn = f[i], k = i; } } if(minn < 0){ for(int i = L[k]; i <= k; i++) a[i] *= x; } }else{ f[1] = a[1]; L[1] = 1; LL maxn = f[1]; int k = 1; for(int i = 2; i <= n; i++) { if(f[i - 1] + a[i] > a[i]){ L[i] = L[i - 1]; f[i] = f[i - 1] + a[i]; }else{ L[i] = i; f[i] = a[i]; } if(f[i] > maxn){ maxn = f[i], k = i; } } if(maxn > 0){ for(int i = L[k]; i <= k; i++) a[i] *= x; } } f[1] = a[1]; LL maxn = f[1]; for(int i = 2; i <= n; i++){ f[i] = max(f[i - 1] + a[i], a[i]); maxn = max(maxn, f[i]); } printf("%lld\n", max(maxn, 0ll)); return 0; }

看了题解直接自闭掉，实际上，可以设

\\(f\[0\]\\)为当前以\\(i\\)为右端点，未加入\\(x\\)的极大值，那么它必须大于\\(0\\)

\\(f\[1\]\\)代表开始连续计算\\(\* x\\)了，如果这时候还没有\\(f\[0\]\\)大，那么它也没用了

\\(f\[2\]\\)代表乘完了的，探究是否还能再加入\\(a\[i\]\\)

如果\\(x > 0\\)，那么\\(f\[2\] + a\[i\]\\)一定不会最优

如果\\(x < 0\\)，有可能有这种情况，前面负数后面正数

#include <cstdio> #include <iostream> #include <cmath> using namespace std; const int N = 300010, INF = 2147483647; typedef long long LL; int n, x, L[N]; LL a[N], f[3], ans = 0; int main(){ scanf("%d%d", &n, &x); for(int i = 1; i <= n; i++) scanf("%lld", a + i); for(int i = 1; i <= n; i++){ f[0] = max(f[0] + a[i], 0ll); f[1] = max(f[0], f[1] + a[i] * x); f[2] = max(f[1], f[2] + a[i]); ans = max(ans, f[2]); } printf("%lld\n", ans); return 0; }

#### E. Guess the Root ####

高斯消元\\(/\\)拉格朗日插值法都不会，咕咕咕。

转载于:https://www.cnblogs.com/dmoransky/p/11304787.html