随笔题解 Ct. 4

Educational Codeforces Round 170 (Rated for Div. 2)

呵呵呵，许久不曾 CF 了……

A. B. C.

略。

D. Attribute Checks

Description

考虑一款游戏，游戏角色有两个属性：力量和智力。

接下来会发生 $n$ 个事件。第 $i$ 个事件可能是：

1. 属性分配：你可以选择力量 $+1$ 或智力 $+1$
2. 力量检查：给出一个阈值 $r$，如果你的力量 $\geqslant r$，你获得一分
3. 智力检查：给出一个阈值 $r$，如果你的智力 $\geqslant r$，你获得一分

并且恰好会有 $m$ 个事件是属性分配。

问 $n$ 个事件结束之后你最多能拿多少得分。

$1 \leqslant m \leqslant 5000$，$m \lt n \leqslant 2 \cdot 10^6$。$r \leqslant m$。

$\texttt{2.5s/512MiB}$。

Solution

令 $\text{dp}[i][j]$ 表示第 $i$ 次属性分配之后力量为 $j$，这样的最高得分。然后 DP。

E. Card Game

Description

现在这里有 $n \cdot m$ 张卡牌。$m$ 是偶数。每张卡牌都有花色和点数两个属性。花色是 $1 \sim n$ 的整数，点数是 $1 \sim m$ 的整数。花色和点数的 $n \cdot m$ 种组合每种恰好只有一张。

对于两张卡牌：

1. 如果花色不同，花色为 $1$ 的卡牌总能打赢花色非 $1$ 的卡牌
2. 如果花色相同，点数更高的卡牌能打赢点数更低的卡牌

现将这 $n \cdot m$ 张卡牌两两配对，使得每对卡牌的其中一张能够打赢另外一张。问方案数。对 $998244353$ 取模。

$1 \leqslant n, m \leqslant 500$。

$\texttt{2s/512MiB}$。

Solution

考虑给每张卡牌分配一个括号。

对于 $2 \sim n$ 的每种花色，将这种花色的 $m$ 张卡牌按点数从大到小排开，可以得到一个括号序列。

比如说 ()(()) 就是说 $1-2, 3-6, 4-5$ 两两配对。

如果出现不匹配的情况，比如说 ()()))，这个例子里多出来 $2$ 个右括号，那么花色 $1$ 的括号序列里就需要多出来 $2$ 个左括号。

如果这些括号序列里存在没有使用的左括号，因为整体的括号数量要是一样的，花色 $1$ 的括号序列里就会多出来等量的右括号。它们就配对不上了。

那么，对于 $2 \sim n$ 的每种花色，实际合法的括号序列就是：

1. 总和 $\leqslant 0$
2. 最后一个括号是右括号

花色 $1$ 的合法括号序列就是：

1. 前缀和总是 $\geqslant 0$
2. 总和 $= - \sum$ 其他花色括号序列的总和

然后就是 DP 水平（