Codeforces Global Round 1
A
模拟即可
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int b, k, n, a[232333];
int main() {
int i, base = 1, v;
scanf("%d%d", &b, &k);
for (i = 1; i <= k; ++i) scanf("%d", &a[i]);
for (i = k; i; --i) {
v = a[i];
n = (n + v * base) & 1;
base = (base * b) & 1;
}
puts(n ? "odd" : "even");
return 0;
}B
总长度减去前 \(k-1\) 大的间距
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(1e5 + 5);
int m, n, k, b[maxn];
int main() {
int i;
ll ans;
scanf("%d%d%d", &n, &m, &k);
for (i = 1; i <= n; ++i) scanf("%d", &b[i]);
for (i = n; i; --i) b[i] = b[i] - b[i - 1] - 1;
sort(b + 2, b + n + 1);
for (i = 2; i <= n; ++i) ans += b[i];
for (i = 1; i < k; ++i) ans -= b[n - i + 1];
printf("%I64d\n", ans + n);
return 0;
}C
当 \(a\ne 2^k-1\)，那么一定能找到一个数字 \(b\) 使得 \(a~or~b=2^k-1\)，\(gcd(a~xor~b,a~and~b)=gcd(2^k-1,0)=2^k-1\)
否则，\(gcd(a~xor~b,a~and~b)=gcd(a-b,b)\)，输出 \(a\) 的最大因子
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int q;
int main() {
int v, i, j, mx = 0;
scanf("%d", &q);
for (i = 1; i <= q; ++i) {
scanf("%d", &v), ++v;
if ((v & -v) == v) {
--v, mx = 1;
for (j = 2; j * j <= v; ++j)
if (v % j == 0) mx = max(mx, max(j, v / j));
printf("%d\n", mx);
}
else {
--v;
for (j = 0; j <= 25; ++j)
if ((1 << j) > v) break;
printf("%d\n", (1 << j) - 1);
}
}
return 0;
}D
记录这每个数字的个数，\(DP\)
\(f[i][j][k]\) 表示从小到大的第 \(i\) 个数字，这个数字还有 \(j\) 个，上一个有 \(k\)
理论上 \(j,k\le 6\)，一个位置能出的不同顺子最多三种，如果 \(j,k> 6\)，那么一定有一种出了三次，直接拆开每个出三连即可考场上写到了9
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(1e6 + 5);
int n, m, c[maxn], t[maxn];
ll ans, f[2][10][10], mx, inf;
inline void Cmax(ll &x, ll y) {
x = x < y ? y : x;
}
int main() {
int i, j, k, l, lst, nxt;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; ++i) scanf("%d", &c[i]), ++t[c[i]];
for (i = 1; i <= m; ++i) c[i] = t[i];
for (i = 1; i <= m; ++i) {
if (c[i] > 6) {
c[i] -= 6;
ans += c[i] / 3, c[i] %= 3;
c[i] += 6;
}
}
memset(f, -63, sizeof(f)), lst = 0, nxt = 1;
inf = f[0][0][0], f[0][c[1]][c[2]] = ans;
for (i = 3; i <= m; ++i) {
for (j = 0; j <= 8; ++j)
for (k = 0; k <= 8; ++k)
if (f[lst][j][k] != inf) {
for (l = min(j, min(k, c[i])); ~l; --l)
Cmax(f[nxt][k - l][c[i] - l], f[lst][j][k] + l + (j - l) / 3);
for (l = 3; l <= c[i]; l += 3)
Cmax(f[nxt][k][c[i] - l], f[lst][j][k] + l / 3);
f[lst][j][k] = inf;
}
swap(lst, nxt);
}
for (i = 0; i <= 8; ++i)
for (j = 0; j <= 8; ++j) mx = max(mx, f[lst][i][j] + i / 3 + j / 3);
printf("%lld\n", mx);
return 0;
}E
这个变换在差分数组上表现为相邻两个数的交换，直接判断即可
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(1e5 + 5);
int n, c[maxn], t[maxn];
int main() {
int i;
scanf("%d", &n);
for (i = 1; i <= n; ++i) scanf("%d", &c[i]);
for (i = 1; i <= n; ++i) scanf("%d", &t[i]);
if (c[1] != t[1] || c[n] != t[n]) return puts("No"), 0;
for (i = n; i; --i) c[i] -= c[i - 1], t[i] -= t[i - 1];
sort(t + 2, t + n + 1), sort(c + 2, c + n + 1);
for (i = 2; i <= n; ++i) if (c[i] ^ t[i]) return puts("No"), 0;
return puts("Yes"), 0;
}F
在线就是维护每个点到所有点的距离，主席树存储，两遍 \(dfs\) 预处理，空间有点卡
直接离线存储询问一起 \(dfs\) 就行了
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(5e5 + 5);
const ll inf(1e18);
struct Qry {
int l, r, id;
};
int n, q, dfn[maxn], idx, ed[maxn];
ll mn[maxn << 2], tag[maxn << 2], ans[maxn];
vector < pair <int, int> > edge[maxn];
vector <Qry> qry[maxn];
void Update(int x, int l, int r, int p, ll v) {
if (l == r) mn[x] = v + tag[x];
else {
int mid = (l + r) >> 1;
p <= mid ? Update(x << 1, l, mid, p, v) : Update(x << 1 | 1, mid + 1, r, p, v);
mn[x] = min(mn[x << 1], mn[x << 1 | 1]) + tag[x];
}
}
void Modify(int x, int l, int r, int ql, int qr, ll v) {
if (ql <= l && qr >= r) tag[x] += v, mn[x] += v;
else {
int mid = (l + r) >> 1;
if (ql <= mid) Modify(x << 1, l, mid, ql, qr, v);
if (qr > mid) Modify(x << 1 | 1, mid + 1, r, ql, qr, v);
mn[x] = min(mn[x << 1], mn[x << 1 | 1]) + tag[x];
}
}
ll Query(int x, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return mn[x];
int mid = (l + r) >> 1;
ll ret = inf;
if (ql <= mid) ret = Query(x << 1, l, mid, ql, qr);
if (qr > mid) ret = min(ret, Query(x << 1 | 1, mid + 1, r, ql, qr));
return ret + tag[x];
}
void Dfs1(int u, ll d) {
dfn[u] = ++idx;
if (!edge[u].size()) Update(1, 1, n, idx, d);
for (auto v : edge[u]) Dfs1(v.first, d + v.second);
ed[u] = idx;
}
void Dfs2(int u) {
for (auto ques : qry[u]) ans[ques.id] = Query(1, 1, n, ques.l, ques.r);
for (auto v : edge[u]) {
Modify(1, 1, n, 1, n, v.second);
Modify(1, 1, n, dfn[v.first], ed[v.first], -(v.second << 1));
Dfs2(v.first);
Modify(1, 1, n, dfn[v.first], ed[v.first], v.second << 1);
Modify(1, 1, n, 1, n, -v.second);
}
}
int main() {
memset(mn, 63, sizeof(mn));
int p, w, i, l, r;
scanf("%d%d", &n, &q);
for (i = 2; i <= n; ++i) {
scanf("%d%d", &p, &w);
edge[p].push_back(make_pair(i, w));
}
for (i = 1; i <= q; ++i) {
scanf("%d%d%d", &p, &l, &r);
qry[p].push_back((Qry){l, r, i});
}
Dfs1(1, 0), Dfs2(1);
for (i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
return 0;
}G
官方题解
首先黑点不会获胜，如果黑点获胜，那么白点一定可以在按照黑点获胜的策略在之前获胜
考虑如果没有选过的点的做法，分情况讨论
- 存在一个度数大于 \(3\) 的点，显然白点 \(win\)
- 存在一个度数大于 \(2\) 的，且有大于 \(1\) 个非叶子的相邻点的点，还是 \(win\)
- 剩下的情况就是一些度数为 \(2/1\) 的点，以及不超过两个的度数为 \(3\) 的点有大于一个叶子的相邻点的点，不难发现这种情况只有当点数为奇数的时候才会 \(win\)
- 其它情况均为 \(draw\)
考虑有选过的点怎么办，题解里面把这样的点变成了四个没有被选过的点懒得放图片就描述一下中间一个点，然后周围挂三个点，选挂的三个点中任意一个为原来的点连回原图
这样为什么是对的呢，因为在双方绝顶聪明的时候，白的选了原来的点，黑的就一定会选中间的那一个，如果黑的再次选一个点，那么白的可以拿走剩下的点，状态不变
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(2e6 + 5);
struct Edge {
int to, next;
} edge[maxn << 1];
int n, tot, first[maxn], cnt, d[maxn];
char c;
inline void Add(int u, int v) {
edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++, ++d[v];
edge[cnt] = (Edge){u, first[v]}, first[v] = cnt++, ++d[u];
}
inline int Solve() {
int i, e, u, v;
scanf("%d", &n), cnt = 0, tot = n + n + n + n;
for (i = 1; i <= tot; ++i) first[i] = -1, d[i] = 0;
for (i = 1; i < n; ++i) scanf("%d%d", &u, &v), Add(u, v);
for (tot = n, i = 1; i <= n; ++i) {
scanf(" %c", &c);
if (c == 'W') Add(i, tot + 1), Add(tot + 1, tot + 2), Add(tot + 1, tot + 3), tot += 3;
}
for (i = 1; i <= tot; ++i) if (d[i] > 3) return puts("White"), 233;
for (i = 1; i <= tot; ++i)
if (d[i] > 2) {
for (cnt = 0, e = first[i]; ~e; e = edge[e].next)
if (d[edge[e].to] > 1) ++cnt;
if (cnt > 1) return puts("White"), 233;
}
cnt = 0;
for (i = 1; i <= tot; ++i) cnt += d[i] == 3;
if (cnt == 2 && (tot & 1)) return puts("White"), 233;
return puts("Draw"), 666;
}
int main() {
int test;
scanf("%d", &test);
while (test--) Solve();
return 0;
}H
首先如果合法的串不多就是一个简单的 \(AC\) 自动机 + \(DP\)
考虑到自动机上有很多状态是存在所有转移的，也就是数位 \(DP\) ，第一个满足 \(>l\) 或 \(<r\) 的地方
把所有这样的前缀加入 \(AC\) 自动机，最多 \(10(|l|+|r|)\) 个
设 \(g[u][i]\) 表示从 \(u\) 点开始，任意再选 \(i\) 个能得到的合法串的个数
这样就把那些没有新建的状态的贡献加上了
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(2005);
const int maxm(16005);
int n, lenl, lenr, trs[maxm][10], tot, fail[maxm], g[maxm][maxn], f[maxm][maxn], ans;
bitset <maxn> vis[maxm];
char liml[maxn], limr[maxn];
queue <int> Q;
inline void Upd(int &x, int y) {
x = x > y ? x : y;
}
inline void Init() {
int i, c, cur1, cur2;
scanf(" %s %s%d", liml + 1, limr + 1, &n);
lenl = strlen(liml + 1), lenr = strlen(limr + 1);
if (lenl == lenr) {
cur1 = cur2 = 0;
for (i = 1; i <= lenl; ++i) {
if (cur1 == cur2) {
for (c = liml[i] - '0' + 1; c < limr[i] - '0'; ++c) {
if (!trs[cur1][c]) trs[cur1][c] = ++tot;
++g[trs[cur1][c]][lenl - i];
}
}
else {
for (c = liml[i] - '0' + 1; c < 10; ++c) {
if (!trs[cur1][c]) trs[cur1][c] = ++tot;
++g[trs[cur1][c]][lenl - i];
}
for (c = 0; c < limr[i] - '0'; ++c) {
if (!trs[cur2][c]) trs[cur2][c] = ++tot;
++g[trs[cur2][c]][lenl - i];
}
}
if (!trs[cur1][liml[i] - '0']) trs[cur1][liml[i] - '0'] = ++tot;
if (!trs[cur2][limr[i] - '0']) trs[cur2][limr[i] - '0'] = ++tot;
cur1 = trs[cur1][liml[i] - '0'], cur2 = trs[cur2][limr[i] - '0'];
}
++g[cur1][0];
if (cur1 ^ cur2) ++g[cur2][0];
}
else {
cur1 = cur2 = 0;
for (i = 1; i <= lenl; ++i) {
for (c = liml[i] - '0' + 1; c < 10; ++c) {
if (!trs[cur1][c]) trs[cur1][c] = ++tot;
++g[trs[cur1][c]][lenl - i];
}
if (!trs[cur1][liml[i] - '0']) trs[cur1][liml[i] - '0'] = ++tot;
cur1 = trs[cur1][liml[i] - '0'];
}
for (i = 1; i <= lenr; ++i) {
for (c = i == 1; c < limr[i] - '0'; ++c) {
if (!trs[cur2][c]) trs[cur2][c] = ++tot;
++g[trs[cur2][c]][lenr - i];
}
if (!trs[cur2][limr[i] - '0']) trs[cur2][limr[i] - '0'] = ++tot;
cur2 = trs[cur2][limr[i] - '0'];
}
++g[cur1][0], ++g[cur2][0];
for (i = lenl + 1; i < lenr; ++i)
for (c = 1; c < 10; ++c) {
if (!trs[0][c]) trs[0][c] = ++tot;
++g[trs[0][c]][i - 1];
}
}
}
inline void GetFail() {
int u, i, c;
for (c = 0; c < 10; ++c) if (trs[0][c]) Q.push(trs[0][c]);
while (!Q.empty()) {
u = Q.front(), Q.pop();
for (c = 0; c < 10; ++c)
if (trs[u][c]) fail[trs[u][c]] = trs[fail[u]][c], Q.push(trs[u][c]);
else trs[u][c] = trs[fail[u]][c];
for (i = 0; i <= n; ++i) g[u][i] += g[fail[u]][i];
}
for (i = 0; i <= tot; ++i)
for (c = 1; c <= n; ++c) g[i][c] += g[i][c - 1];
}
inline void Solve(int x, int y) {
if (y == n) return;
int c;
for (c = 0; c < 10; ++c)
if (f[x][y] + g[trs[x][c]][n - y - 1] == f[trs[x][c]][y + 1] && vis[trs[x][c]][y + 1]) {
putchar(c + '0'), Solve(trs[x][c], y + 1);
return;
}
}
int main() {
int i, j, c;
memset(f, -63, sizeof(f));
Init(), GetFail(), f[0][0] = 0;
for (i = 1; i <= n; ++i)
for (j = 0; j <= tot; ++j)
if (f[j][i - 1] >= 0)
for (c = 0; c < 10; ++c)
Upd(f[trs[j][c]][i], f[j][i - 1] + g[trs[j][c]][n - i]);
for (j = 0; j <= tot; ++j) Upd(ans, f[j][n]);
for (j = 0; j <= tot; ++j) if (f[j][n] == ans) vis[j][n] = 1;
for (i = n; i; --i)
for (j = 0; j <= tot; ++j)
for (c = 0; c < 10; ++c)
if (vis[trs[j][c]][i] && f[trs[j][c]][i] == f[j][i - 1] + g[trs[j][c]][n - i]) vis[j][i - 1] = 1;
printf("%d\n", ans), Solve(0, 0), puts("");
return 0;
}