Codeforces Global Round 1题解报告

A. Parity

题意

模2意义下的秦九韶。

题解

模2意义下的秦九韶。

代码

#include int ri() { char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1; for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f; } int main() { int b = ri(), k = ri(), n = 0; for(int i = 1;i <= k; ++i) n = (n * b + ri()) & 1; puts(n ? "odd" : "even"); return 0; }

B. Tape

题意

给你一条长度为$m$的绳子，上面有$n$处断点，利用要最多$k$条胶带覆盖这些断点，最小化长度。

题解

取前$k$大的断点间隔即可。记得掐头去尾。

代码

#include const int N = 1e5 + 10; int ri() { char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1; for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f; } int n, m, k, b[N]; int main() { n = ri(); m = ri(); k = ri(); for(int i = 0;i < n; ++i) b[i] = ri(); int All = b[n - 1] - b[0] + 1, Sum = 0; for(int i = n - 1; i; --i) b[i] -= b[i - 1] + 1; std::sort(b + 1, b + n); for(int i = 1; i < k && i < n; ++i) Sum += b[n - i]; printf("%d ", All - Sum); return 0; }

C. Meaningless Operations

题意

$f(a)= max_{0<b<a}gcd(a⊕b,a & b)$，多组询问$a$，求$f(a)$

题解

如果$a eq 2^n-1$，将$a$拆位考虑，$1⊕0=1,1 & 0 = 0;0⊕1=1,0& 1 = 0$，这样的话构造出来的就是$a⊕b=111cdots 11_{(2)},a& b = 0$，$f(a)$在此时最大。
可是当$a= 2 ^n-1$是，构造出来的$b=0$，不符合题意。考场上当然直接打表啦。
题解给的方法是，此时相当于是$gcd(2^x-1-b,b)=gcd(2^x-1,b)$，就是找$2^x-1$的最大因子。

代码

#include int ri() { char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1; for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f; } int bin[30]; const int biao[] = {1,1,5,1,21,1,85,73,341,89,1365,1,5461,4681,21845,1,87381,1,349525,299593,1398101,178481,5592405,1082401}; int main() { bin[0] = 1; for(int i = 1;i <= 25; ++i) bin[i] = bin[i - 1] << 1; int q = ri(); for(;q--;) { int a = ri(), mx; for(int i = 24;~i; --i) if(a >= bin[i]) { mx = i + 1; break; } if(bin[mx] - 1 == a) printf("%d ", biao[mx - 2]); else printf("%d ", bin[mx] - 1); } return 0; }

D. Jongmah

题意

从一个序列里面挑出尽量多的三元组，满足要么三个数相同要么三个数连续。

题解

考虑如果某个连续型三元组超过了三个，可以直接转化成相同型的三元组，所以存在最优解使得完全相同的连续型三元组不超过两个，于是同一种数至多有六个用于组成连续型三元组。排序之后状压前面两个数值的用于组成连续三元组的情况即可。

代码

#include const int N = 1e6 + 10; int ri() { char c = getchar(); int x = 0, f = 1; for(;c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1; for(;c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c; return x * f; } int n, m, Ans, c[N], dp[2][49]; void Up(int &a, int b) {a = std::max(a, b);} int main() { n = ri(); m = ri(); for(int i = 1;i <= n; ++i) ++c[ri()]; memset(dp, -0x3f, sizeof(dp)); dp[0][0] = 0; int *g = dp[0], *f = dp[1]; for(int i = 1;i <= m; ++i, std::swap(f, g)) { memset(f, -0x3f, sizeof(dp[0])); for(int c1 = 0;c1 < 7; ++c1) for(int c2 = 0; c2 < 7; ++c2) { int mx = std::min(std::min(c1, std::min(c2, c[i])), 2); for(int t = 0;t <= mx; ++t) { int re = c[i] - t; if(re < 3) { Up(f[(c2 - t) * 7 + re], g[c1 * 7 + c2] + t); } else if(re < 6) { Up(f[(c2 - t) * 7 + re], g[c1 * 7 + c2] + t); Up(f[(c2 - t) * 7 + re - 3], g[c1 * 7 + c2] + t + 1); } else { int rre = re % 3 + 3, tm = re / 3 - 1; Up(f[(c2 - t) * 7 + rre], g[c1 * 7 + c2] + t + tm); Up(f[(c2 - t) * 7 + rre - 3], g[c1 * 7 + c2] + t + tm + 1); } } } } int mx = 0; for(int i = 0;i < 49; ++i) mx = std::max(mx, g[i]); printf("%d ", mx); return 0; }

E. Magic Stones

题意

给一个序列，可以进行任意进行以下操作，$c_i'=c_{i-1}+c_{i+1}-c_i$