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;
}