A - Two Choices
题意
有$n$个学生做$m$道题，每道题的答案都是$0$或$1$。给你每个学生的解答，问有多少对学生，满足无论标准答案是什么都不能使他们有相同数量的正确答案。
$2 \leq n \leq 10^5$, $1 \leq m \leq 20$
题解
考虑两个人怎样满足要求：首先，两个人答案相同的题目是没有影响的，要么都错，要么都对，所以我们可以先异或起来，只关心$1$的位置。显然，只有异或之后$1$的数量为偶数的时候，才能让他们有相同数量的正确答案，即每一位异或起来=0。所以题目要求的限制等价于
所以只需要维护异或和为$0$的数量和异或和为$1$的数量即可。
代码
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt[2];
long long ans = 0;
char s[30];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
scanf("%s", s);
int now = 0;
for (int j = 0; j < m; j++)
now ^= s[j] - '0';
ans += cnt[now];
cnt[now ^ 1]++;
}
printf("%lld\n", ans);
}
B - Plus Matrix
题意
给定$n\times n$的矩阵$C$，求两个长度为$n$的非负序列$a, b$，满足$C_{i, j} = a_i + b_j$。
$1 \leq n \leq 500, 0 \leq C_{i, j} \leq 10^9$
题解
考虑分别按行和列差分，因为$a, b$的差分和行、列的差分是相等的。如果两行或两列的差分不相等的话，那么直接就可以判断出是无解的。然后因为$a, b$要求非负，我们已经知道了他们差分后的数组，也就可以求出他们的最小值相对于$a_1$和$b_1$的大小，而$a_1 + b_1 = C_{1,1}$，所以只要把$C_{1,1}$拆成$a_1$和$b_1$，满足两个序列的最小值都非负就行了。
代码
#include <bits/stdc++.h>
using namespace std;
int n, c[510][510], a[510], b[510];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &c[i][j]);
for (int i = 2; i <= n; i++)
a[i] = c[1][i] - c[1][i - 1];
for (int i = 2; i <= n; i++)
for (int j = 2; j <= n; j++)
if (a[j] != c[i][j] - c[i][j - 1])
{
puts("No");
return 0;
}
for (int i = 2; i <= n; i++)
b[i] = c[i][1] - c[i - 1][1];
for (int i = 2; i <= n; i++)
for (int j = 2; j <= n; j++)
if (b[j] != c[j][i] - c[j - 1][i])
{
puts("No");
return 0;
}
int mna = 0, mnb = 0;
for (int i = 2; i <= n; i++)
{
a[i] += a[i - 1];
b[i] += b[i - 1];
mna = min(mna, a[i]);
mnb = min(mnb, b[i]);
}
if (-(mna + mnb) > c[1][1])
{
puts("No");
return 0;
}
for (int i = 1; i <= n; i++)
{
a[i] -= mna;
b[i] += c[1][1] + mna;
}
puts("Yes");
for (int i = 1; i <= n; i++)
printf("%d ", b[i]);
puts("");
for (int i = 1; i <= n; i++)
printf("%d ", a[i]);
puts("");
}
C - ℕ Coloring
题意
给定$n$，求一个长度为$n$的序列$A$，满足$i|j, A_i \neq A_j$。最小化最大值。
$1 \leq n \leq 10^5$
题解
看了别人的代码感觉我想复杂了qaq
从前往后填数，每次填最小的合法的数进去，这样显然是最优的。注意到因数个数和不大，对每个数，我们先因式分解，然后用权值线段树维护哪些数已经用了，把最小的没用过的数填到当前这一位上。
官方题解：
$A_i= (\text{the number of prime factors of } i) + 1$
$i|j$时，$i$和$j$的质因数个数肯定不等，所以这个构造方法合法；令$k=\lfloor \log_2 n \rfloor + 1$，则$A_{2^k} \geq k + 1$，而上述构造方法最大值即为$k + 1$，所以时最优的。
代码
#include <bits/stdc++.h>
#define pa pair<int, int>
using namespace std;
int n, ans[100010];
struct tree
{
int l, r, sz;
tree *lc, *rc;
tree(int l, int r) : l(l), r(r), sz(0), lc(nullptr), rc(nullptr) {}
} *root;
bool not_prime[100010];
vector<int> prime, v;
vector<pa> d;
int mn[100010];
void pre(int n = 100000)
{
for (int i = 2; i <= n; i++)
{
if (!not_prime[i])
{
prime.push_back(i);
mn[i] = i;
}
for (int x : prime)
{
if (1LL * x * i > n) break;
not_prime[x * i] = 1;
mn[x * i] = x;
if (i % x == 0) break;
}
}
}
tree *bt(int l, int r)
{
tree *i = new tree(l, r);
if (l < r)
{
int md = l + r >> 1;
i->lc = bt(l, md);
i->rc = bt(md + 1, r);
}
return i;
}
void chg(tree *i, int p, int x)
{
if (i->l == i->r)
{
if (x == 1) i->sz = 1;
else i->sz = 0;
return;
}
int md = i->l + i->r >> 1;
if (p <= md) chg(i->lc, p, x);
else chg(i->rc, p, x);
i->sz = i->lc->sz + i->rc->sz;
}
int get(tree *i)
{
if (!i->sz) return i->l;
int md = i->l + i->r >> 1;
if (i->lc->sz < md - i->l + 1) return get(i->lc);
else return get(i->rc);
}
void dfs(int now, int x)
{
if (x == d.size())
{
v.push_back(now);
return;
}
dfs(now, x + 1);
for (int i = 1; i <= d[x].second; i++)
{
now *= d[x].first;
dfs(now, x + 1);
}
}
int main()
{
pre();
scanf("%d", &n);
root = bt(1, n);
for (int i = 1; i <= n; i++)
{
d.clear();
v.clear();
int now = i;
while (now > 1)
{
int hh = mn[now];
d.emplace_back(hh, 0);
while (now % hh == 0)
{
now /= hh;
d.back().second++;
}
}
dfs(1, 0);
// for (int x : v)
// printf("%d ", x);
// puts("");
v.pop_back();
for (int x : v)
chg(root, ans[x], 1);
ans[i] = get(root);
for (int x : v)
chg(root, ans[x], -1);
printf("%d ", ans[i]);
}
puts("");
}
D - Odd Degree
题意
给定一个$n$个点$m$条边的简单无向图，对于每个$0 \leq k \leq n$，求恰好有$k$个奇度顶点生成子图的个数。答案%998244353。
$1 \leq n \leq 5000, 0 \leq m \leq 5000$
题解
有个很棒的结论：如果原图是一棵树，在我们确定了某$k$个奇度顶点，那么只会有0个方案（$k$为奇数时）或1个（$k$为偶数时）。证明：对于一个合法方案，它一定可以拆成$k/2$条边不相交的路径；标记一条路径，相当与把从根到两个端点的路径上的边都异或一下，也就是说我们只要把根到每个奇度顶点的路径都异或一遍就可以构造出方案，这显然是唯一的。
考虑加上非树边：如果我们要选某条非树边，我们只需要把两个端点的树上路径取反就行了，即选一条非树边也只对应一种方案。
那么我们就可以得到一个连通块的答案：
多个连通块卷积起来就好了。$n$很小，暴力即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n, m, f[5010], sz[5010], nm[5010];
long long pow2[5010], C[5010][5010], ans[2][5010];
int fd(int x) { return f[x] == x ? x : f[x] = fd(f[x]); }
void pre(int n = 5000)
{
pow2[0] = 1;
for (int i = 1; i <= n; i++)
pow2[i] = (pow2[i - 1] << 1) % mod;
C[0][0] = 1;
for (int i = 1; i <= n; i++)
{
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
}
int main()
{
pre();
scanf("%d%d", &n, &m);
iota(f + 1, f + 1 + n, 1);
fill(nm + 1, nm + 1 + n, 1);
for (int i = 0; i < m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
int fa = fd(a), fb = fd(b);
if (fa == fb)
sz[fa]++;
else
{
f[fa] = fb;
sz[fb] += sz[fa];
nm[fb] += nm[fa];
}
}
int p = 0, now = 0;
ans[p][0] = 1;
for (int i = 1; i <= n; i++)
if (f[i] == i)
{
// printf("%d %d\n", nm[i], sz[i]);
p ^= 1;
memset(ans[p], 0, sizeof(ans[p]));
for (int j = 0; j <= nm[i]; j += 2)
{
for (int k = 0; k <= now; k += 2)
(ans[p][j + k] += pow2[sz[i]] * C[nm[i]][j] % mod * ans[p ^ 1][k] % mod) %= mod;
}
now += nm[i];
}
for (int i = 0; i <= n; i++)
printf("%d\n", ans[p][i]);
}
E - LEQ and NEQ
题意
给你一个长度为$n$的序列$A$，求满足$1 \leq X_i \leq A_i, X_i \neq X_{i+1}$的$X$的个数%998244353。
题解
怎么感觉这个e比d还好想
考虑dp：$f_i$表示前$i$个数的答案。转移要容斥一下：
$\min_{k=j}^i A_k$是单调的，所以我们可以一边做一边维护$f_{j-1} \min_{k=j}^i A_k$，最小值一样的一段合并到一起，更新的时候一起更新。最后加起来是$O(n)$的。
代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, inf = 0x3f3f3f3f;
int n, a[500010];
long long f[500010];
struct hh { long long sum, mn; };
vector<hh> s;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
f[0] = 1;
s.push_back({1, inf});
long long now = inf % mod;
for (int i = 1, p = 1; i <= n; i++, p *= -1)
{
long long sum = 0;
while (!s.empty() && s.back().mn >= a[i])
{
(sum += s.back().sum) %= mod;
(now -= s.back().mn % mod * s.back().sum % mod) %= mod;
s.pop_back();
}
(now += sum * a[i] % mod) %= mod;
s.push_back({sum, a[i]});
f[i] = (now * p + mod) % mod;
s.push_back({(f[i] * (-p) + mod) % mod, inf});
(now += s.back().mn % mod * s.back().sum % mod) %= mod;
// printf("%lld\n", f[i]);
}
printf("%lld\n", (f[n] + mod) % mod);
}
F - Migration
题意
一棵$n$个结点的树，点有点权$h_i$，现在上面有$k$个物体，初始放在$s_i$上，最终要移到$t_i$上。每一步可以把其中一个物体移动到相邻的结点上。定义一个状态的“潜力”为每个物体所在点的点权之和（多个物体在同一个点算多次），最小化把所有物体从$s_i$移动到$t_i$的过程中（包括始末状态）的“潜力”的最大值。
题解
首先，考虑初始状态和结束状态同时开始走，最后走到两个状态重合。在这种情况下，如果我们要移动一个物体，肯定要一路移动到权值更小的点上，这样有利于后面的操作。所以对于每个点，我们在权值更小的点中，找路径上最大值最小的点，移动这个地方的物体时肯定要移动到那里。用两个堆维护一下两个状态中移动代价最小的点，移动的同时更新一下答案，就可以了。
代码
#include <bits/stdc++.h>
#define pa pair<long long, int>
using namespace std;
long long w[2010];
int n, k, a[2010], num = 0, fst[2010], s[2010], t[2010], f[2010], mx[2010];
struct edge
{
int x, y, n;
} e[4010];
priority_queue<pa, vector<pa>, greater<pa>> q1, q2;
void ins(int x, int y)
{
e[++num] = {x, y, fst[x]};
fst[x] = num;
}
void dfs(int x, int fa)
{
mx[x] = max(mx[fa], a[x]);
for (int i = fst[x]; i; i = e[i].n)
{
int y = e[i].y;
if (y == fa) continue;
dfs(y, x);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i < n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
ins(x, y);
ins(y, x);
}
memset(w, 63, sizeof(w));
for (int i = 1; i <= n; i++)
{
mx[i] = 0;
dfs(i, 0);
for (int j = 1; j <= n; j++)
if (a[j] < a[i] || a[j] == a[i] && j < i)
{
if (mx[j] < w[i])
{
w[i] = mx[j];
f[i] = j;
}
}
w[i] -= a[i];
}/*
puts("");
for (int i = 1; i <= n; i++)
printf("%lld %d\n", w[i], f[i]);*/
scanf("%d", &k);
int dif = 0;
long long ans = 0, now1 = 0, now2 = 0;
for (int i = 1; i <= k; i++)
{
scanf("%d%d", &s[i], &t[i]);
dif += (s[i] != t[i]);
now1 += a[s[i]];
now2 += a[t[i]];
q1.emplace(w[s[i]], i);
q2.emplace(w[t[i]], i);
}
ans = max(now1, now2);
// printf("%d\n", ans);
while (dif)
{
pa x = q1.top(), y = q2.top();
// printf("%lld %d %lld %d %lld %lld\n", x.first, x.second, y.first, y.second, now1, now2);
if (x.first + now1 < y.first + now2)
{
q1.pop();
int pos = s[x.second];
ans = max(ans, now1 + w[pos]);
now1 = now1 - a[pos] + a[f[pos]];
dif = dif - (s[x.second] != t[x.second]) + (f[pos] != t[x.second]);
s[x.second] = f[pos];
q1.emplace(w[s[x.second]], x.second);
}
else
{
q2.pop();
int pos = t[y.second];
ans = max(ans, now2 + w[pos]);
now2 = now2 - a[pos] + a[f[pos]];
dif = dif - (s[y.second] != t[y.second]) + (s[y.second] != f[pos]);
t[y.second] = f[pos];
q2.emplace(w[t[y.second]], y.second);
}/*
printf("%lld\n", ans);
for (int i = 1; i <= k; i++)
printf("%d %d\n", s[i], t[i]);
system("pause");*/
}
printf("%lld\n", ans);
}