C. Sakurada Reset
「Gym 102361C」Sakurada Reset(动态规划)
题目描述
给定数列 $A, B$,将数列中的每个子序列都看作一个 $1000$ 进制数,问有多少对 $(x, y)$ 满足 $x$ 是 $A$ 的某个子序列,$y$ 是 $B$ 的某个子序列,并且 $x > y$。本质相同的子序列只算一次,答案对大素数取模。
数据范围:$n, m \le 5000, 1 \le A_i, B_i \le 100$。
思路分析
令 $p_i$ 表示 $A$ 中满足 $j < i$ 且 $A_j = A_i$ 的最大的 $j$,如果不存在则为 $0$;$q_i$ 在 $B$ 中有类似的定义。首先计算长度不等的对数,发现这时一定是 $x$ 的长度比 $y$ 的大。预处理出每个数列中特定长度的本质不同子序列个数,就可以直接计算答案了。转移方程:$f(i, j) = f(i - 1)(j) + f(i - 1)(j - 1) - f(p_i - 1)(j - 1)$。
之后再考虑 $x, y$ 长度相同时的贡献。$x, y$ 必定有一个 lcp,之后的第一个数一定是 $x$ 中的比 $y$ 中的大,然后就可以随便排了。将这三个阶段写成三个状态:$f, g, h$,$f(i, j)$ 表示选到 $A_i, B_j$ 为止都相同的方案数,$g, h$ 类似。那么 $f$ 要求 $A_i = B_j$,$g$ 要求 $A_i > B_j$,$h$ 没有要求; $f, g$ 可以从 $f$ 转移过来,$h$ 可以从 $g, h$ 转移过来。下面列出 $f$ 的转移方程,$g, h$ 类似:
前缀和优化 dp 即可。时间复杂度 $O(\max(n, m)^2)$,注意常数优化。
代码实现
1 |
|
E. Escape
题目描述
给定 $n$ 行 $m$ 列的棋盘,北面某些位置有机器人头朝下,南边有某些位置有出口。棋盘中有一些障碍物,机器人不能通过。你可以在一些没有障碍物的地方放置转弯装置,共有四种(“北 $\leftrightarrow$ 东” 以及其他类似的三种)。问机器人是否能够到达某个出口。
数据范围:$T \le 10, n, m \le 100$。
思路分析
一个重要的观察就是每个转弯装置只能给一个人用。那么考虑网络流,给每个格子拆成两个点:横点和竖点,每排的横点连边,每列的竖点连边,机器人和出口与竖点连边。转弯装置相当于联通横点与竖点,也就是在横点和竖点之间连一条边。这样网络中的所有边都是单位容量边,网络流跑得很快。时间复杂度 $O(T \cdot \text{flow}(n \times m, n \times m))$。
代码实现
1 |
|
H. Houraisan Kaguya
绝对不鸽。
K. MUV LUV UNLIMITED
「Gym 102361K」MUV LUV UNLIMITED(博弈论)
题目描述
有一棵树,先手和后手轮流操作,每次可以拿掉若干叶子结点(不能不拿),拿到根结点的人获胜。问先手是否必胜。
复杂度要求线性。
思路分析
对于某棵树,考虑在它的某个非叶结点下面加上一个叶子结点,那么:
- 如果原树是必败态,先手第一次只取新叶子后就留下了必败态,那么新树就是必胜态。
- 如果原树是必胜态,先手第一次取下新叶子和原树必胜态中第一步应该取下的叶子,那么新树还是必胜态。
也就是说,如果一个树满足一个叶子结点的父亲度数大于等于 $2$,它就是必胜态。
如果不是怎么办呢?我们对于每个叶子结点找到第一个祖先 $x$ 满足它的父亲度数大于等于 $2$,我们的目标就是让敌人删到 $x$ 成为叶子结点,然后自己就赢了。这样问题转化成了有 $k$ 个 $a_i$ 表示叶子结点和对应的 $x$ 结点的距离,每次可以选择若干个 $a_i$ 减去 $1$,把其中一个减到 $0$ 的人就输了。
发现只要有一个 $a_i$ 是偶数,你就可以在第一步把所有偶数都取掉一个,之后对手干什么你就复读,最后肯定会在对手的回合留下 $k$ 个 $1$,然后他就输了。否则这时 $a_i$ 全是奇数,对手只要复读你他就能赢。也就是说如果 $a_i$ 全是奇数,你会输;否则你会赢。这样问题就解决了,时间复杂度 $O(n)$。
代码实现
1 |
|
L. MUV LUV ALTERNATIVE
在路上了。