E. Card Game 题目大意 有两个人正在玩一个卡牌游戏，该游戏使用的卡牌组有 $n \times m$ 张卡牌，每张卡牌都有两个参数：花色和等级。花色编号从 $1 \sim n$，等级编号从 $1 \sim m$。每种花色和等级的组合恰有一张牌。
一张花色为 $a$，等级为 $b$ 的牌可以击败一张花色为 $c$，等级为 $d$ 的牌的条件有：
$a = 1, \; c \not = 1$ （花色为 $1$ 的卡牌可以打败任何其他花色的卡牌）；
$a = c, \; b > d$ （同一花色的卡牌可以打败等级较低的卡牌）。
两名玩家进行游戏。在游戏开始之前，他们各自获得正好一半的牌组。第一名玩家获胜的条件是，对于第二名玩家的每一张卡牌，他都能选择一张可以打败它的卡牌，并且没有卡牌被重复选择。否则第二名玩家获胜。
你的任务是计算使第一名玩家获胜的卡牌分配方式数量。两种方式被认为是不同的，如果存在一张卡牌在一种方式中属于第一名玩家，而在另一种方式中属于第二名玩家。结果对 $998244353$ 取模。
$1 \leq n, m \leq 500$
题目分析 首先考虑 $n=1$ 时要如何解决这个问题。容易发现，将牌按等级从大到小排序后，此时任意合法的拿牌序列都形如一个合法的括号匹配。
然而对于 $n>1$ 时，由于除花色 $1$ 之外的花色之间无法相互抵消，从而第一个人得到的一定不多于第二个人得到的。因为一旦比第二个人多，那么他一定会剩下一些这种花色的牌无法消耗。那么对于第二个人比第一个人得到的该花色的牌多的情况，此时只能由第一个人得到的多的花色为 $1$ 的牌抵消掉。
于是考虑设计状态 $f_{i, j}$ 表示分配前 $i$ 副花色的卡牌使得第一个人手里还剩下 $j$ 张可用的 $1$ 花色卡牌的方案数。通过枚举在 $(i + 1)$ 花色第一个人需要使用的 $1$ 花色牌数 $k$，可以进行转移 $f_{i, j} * g_k \rightarrow f_{i + 1, j - k}$，其中 $g_k$ 是长为 $m$ 的括号序列多出 $k$ 个左括号（或右括号）的方案数。
时间复杂度 $O\left(nm^2\right)$
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <bits/stdc++.h> #define R register #define ll long long #define sum(a, b, mod) (((a) + (b)) % mod) #define mul(a, b, mod) (((a) * 1ll * (b)) % mod) #define meow(cat...) fprintf(stderr, cat) const int mod = 998244353 ;const int MaxN = 5e2 + 10 ;int n, m, g[MaxN][MaxN], f[MaxN][MaxN];signed main () scanf ("%d%d" , &n, &m), g[0 ][0 ] = 1 ; for (int i = 0 ; i < m; i++) for (int j = 0 ; j <= i; j++) { g[i + 1 ][j + 1 ] = sum(g[i + 1 ][j + 1 ], g[i][j], mod); if (j) g[i + 1 ][j - 1 ] = sum(g[i + 1 ][j - 1 ], g[i][j], mod); } f[0 ][0 ] = 1 ; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j <= m; j++) { for (int k = 0 ; k <= m; k++) { int t = i ? j - k : j + k; if (t < 0 || t > m) continue ; f[i + 1 ][t] = sum(f[i + 1 ][t], mul(f[i][j], g[m][k], mod), mod); } } } printf ("%d\n" , f[n][0 ]); return 0 ; }
F. Choose Your Queries 题目大意 有 $1$ 个长度为 $n$，初始全部为 $0$ 的数组。有 $q$ 组操作，每次操作有两个参数 $x, y$。在每次操作中，你需要选择 $\{x, y\}$ 中的一个，并加上 $1$ 或 $-1$。需要保证操作过程中每个数都保持非负。给出一种使得最后所有数的和最小的操作方案。
$1 \leq n, q \leq 3 \times 10 ^ 5$
题目分析 注意到题目所给的结构很像一个无向图，于是考虑在无向图上处理。容易发现对于一个点 $u$，最优的决策一定是一加一减，从而只和选择 $u$ 的次数的奇偶性有关，即我们要让尽量少的点具有奇数入度。
考虑答案的下界，容易发现对于某一个联通块，答案的下界是这个联通块中边的条数模 $2$ 的余数。可以发现一定存在一种构造达到这个下界：对于每一个联通块，从某个点出发构造一棵 $\text{DFS}$ 树，然后自底向上分配边。具体过程是：对于一个节点 $v$，首先遍历它的所有子节点；然后对于 $v$ 连接的边，可以分为 $3$ 类：连接 $v$ 儿子的树边，返祖边，横叉边。我们用树边和横叉边构造边对，并把它们移除。如果最后剩下的边的数量为奇数，那么把 $v$ 和它父亲之间的边（如果还没被使用）进行配对，否则留下一条边留待 $v$ 的祖先处理。最后如果联通块的边为奇数，那么会在 $\text{DFS}$ 树的根节点留下一条未被配对的边。
有一个细节需要注意：这题需要保证任意时刻序列中所有数的值非负。所以应该把所有定向到 $u$ 的边排序后，按照题目给定的顺序轮流加一减一，才能符合题意。
时间复杂度 $O(n+q)$
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 #include <bits/stdc++.h> #define R register #define ll long long #define sum(a, b, mod) (((a) + (b)) % mod) #define meow(cat...) fprintf(stderr, cat) const int MaxN = 3e5 + 10 ;const std ::string choice = "xy" ;const std ::string sign = "+-" ;std ::string ans[MaxN];int n, q, color[MaxN], edge[MaxN][2 ];std ::vector <int > g[MaxN];void pair (int q1, int q2) if (q1 > q2) std ::swap(q1, q2); for (int i = 0 ; i < 2 ; i++) for (int j = 0 ; j < 2 ; j++) if (edge[q1][i] == edge[q2][j]) { ans[q1] = {choice[i], sign[0 ]}; ans[q2] = {choice[j], sign[1 ]}; return ; } } int dfs (int u, int pe = -1 ) color[u] = 1 ; std ::vector <int > ed; for (auto e : g[u]) { int v = edge[e][0 ] ^ edge[e][1 ] ^ u; if (color[v] == 1 ) continue ; if (color[v] == 0 ) { if (dfs(v, e)) ed.push_back(e); } else ed.push_back(e); } int res = true ; if (ed.size() % 2 != 0 ) { if (pe != -1 ) ed.push_back(pe); else ed.pop_back(); res = false ; } for (int i = 0 ; i < ed.size(); i += 2 ) pair(ed[i], ed[i + 1 ]); color[u] = 2 ; return res; } signed main () scanf ("%d%d" , &n, &q); for (int i = 1 ; i <= q; i++) { scanf ("%d%d" , &edge[i][0 ], &edge[i][1 ]); g[edge[i][0 ]].push_back(i); g[edge[i][1 ]].push_back(i); ans[i] = "x+" ; } for (int i = 1 ; i <= n; i++) if (!color[i]) dfs(i); for (int i = 1 ; i <= q; i++) printf ("%s\n" , ans[i].c_str()); return 0 ; }
G. Variable Damage 题目翻译 Monocarp 正在组建一支军队，在一款电子游戏中与龙作战。
军队由两个部分组成：英雄和防御神器。每个英雄都有一个参数——他的生命值。每个防御神器也有一个参数——它的耐久度。
在战斗开始前，Monocarp 将神器分配给英雄，使得每个英雄最多持有一个神器。
战斗由若干回合组成，每个回合的流程如下：
首先，龙对每个英雄造成伤害，伤害值等于 $\frac{1}{a+b}$（为不进行取整的实数），其中 $a$ 是存活英雄的数量，$b$ 是活跃神器的数量；
之后，所有生命值小于或等于 0 的英雄死亡；
最后，一些神器会被取消激活。当满足以下任意一个条件时，耐久度为 $x$ 的神器被取消激活：持有该神器的英雄死亡，或者该英雄累计承受的伤害达到 $x$。如果神器未被任何英雄持有，则在战斗开始时即为非活跃状态。
当没有英雄存活时，战斗结束。
最初，军队为空。共有 $q$ 个查询：添加一个生命值为 $x$ 的英雄或耐久度为 $y$ 的神器到军队。对于每个查询，确定如果 Monocarp 最优地分配神器，他能存活的最大回合数。
$1 \leq q \leq 3 \times 10 ^ 5$
题目解析 首先考虑给定 $a, b$ 数组时如何解决该问题。我们先把神器分配给英雄，组成对 $a_i, b_i$。如果 $m > n$，那么丢弃 $b$ 最小的一些神器。否则如果 $m < n$，用 $b_i = 0$ 补充缺少的神器。
注意到一个有着神器 $b_i$ 的英雄 $a_i$ 可以被替换为一个有着 $a_i$ 点血量的英雄和一个有着 $\min \left(a_i, b_i\right)$ 点血量的英雄，而不会改变答案。
于是我们可以考虑把问题转化为神器不存在，只有 $2n$ 个血量分别为 $a_1, \min (a_1, b_1), \dots, a_n, \min (a_n, b_n)$ 的英雄，每回合龙可以对英雄造成总计一点的伤害，因此最终答案就是：
第一个和容易维护，我们考虑如何维护第二个和的最小值。容易发现，将神器和英雄均降序排序后两两配对是最优的。现在考虑动态插入时要怎么维护。
考虑类似扫描线的思路。我们将英雄和神器组合成一个数组并按降序排列。为了简化起见，假设所有耐久度和生命值都是不同的整数，这可以通过离散化实现。把英雄当成 1，让 $s_{a_i}$ 加上 1，武器当成 $-1$，让 $s_{b_i}$ 减去 1，那么一个血量为 $a_i$ 的英雄会造成贡献（即比与其匹配的武器的 $b$ 小）当且仅当 $\sum_{k=a_i}^{\infty} s_k \leq 0$，同样的，一个强度为 $b_i$ 的装备会造成贡献当且仅当 $\sum_{k=b_i}^{\infty} s_k \geq 0$。
现在考虑维护 $s$ 的后缀和数组 $f$，并查询 $f$ 上所有 $\leq/ \ge 0$ 的位置对应的权值，修改则是区间 $+1/-1$。考虑通过分块维护，显然查询的时间复杂度为 $O(\dfrac{q}{B})$。对于修改，我们考虑块内维护差分数组，由于块内任意两个 $f$ 值的差小于块长 $B$，于是空间复杂度是线性的。在块内修改的时间复杂度是 $O(B)$，重新计算答案的时间复杂度为 $O(\dfrac{q}{B})$。于是取 $B = \sqrt q$，那么总时间复杂度为 $O(q \sqrt q)$
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 #include <bits/stdc++.h> #define forn(i, n) for (int i = 0; i < int(n); i++) using namespace std ;struct query { int t, v; }; int main () cin .tie(0 ); ios::sync_with_stdio(false ); int m; cin >> m; vector <query> q(m); forn(i, m) cin >> q[i].t >> q[i].v; vector <pair<int , int >> xs; forn(i, m) xs.push_back({q[i].v, i}); sort(xs.rbegin(), xs.rend()); forn(i, m) q[i].v = xs.rend() - lower_bound(xs.rbegin(), xs.rend(), make_pair(q[i].v, i)) - 1 ; const int p = sqrt (m + 10 ); const int siz = (m + p - 1 ) / p; vector <int > tp(m); vector <int > val(m); vector <vector <long long >> dp(p, vector <long long >(2 * siz + 1 )); vector <int > blbal(p); auto upd = [&](const query &q) { tp[q.v] = q.t; val[q.v] = xs[q.v].first; blbal[q.v / siz] += q.t == 1 ? 1 : -1 ; }; auto recalc = [&](int b) { dp[b].assign(2 * siz + 1 , 0 ); int bal = 0 ; for (int i = b * siz; i < m && i < (b + 1 ) * siz; ++i) { if (tp[i] == 1 ) { dp[b][0 ] += val[i]; dp[b][0 ] += val[i]; dp[b][-bal + siz] -= val[i]; ++bal; } else if (tp[i] == 2 ) { dp[b][-bal + 1 + siz] += val[i]; --bal; } } forn(i, 2 * siz) { dp[b][i + 1 ] += dp[b][i]; } }; auto get = [&](int b, int bal) { bal += siz; if (bal < 0 ) return dp[b][0 ]; if (bal >= 2 * siz + 1 ) return dp[b].back(); return dp[b][bal]; }; for (auto it : q) { upd(it); recalc(it.v / siz); int bal = 0 ; long long ans = 0 ; for (int i = 0 ; i * siz < m; ++i) { ans += get(i, bal); bal += blbal[i]; } cout << ans << '\n' ; } return 0 ; }