7/11 Done
训练不下去
被自己困起来了
其实没什么大事儿的
题目链接
A
题意
题解
B
签到
C
一开始理解错题意wa+1(实际上是没仔细看题)。
简单dp一下即可。
D
题意
玩家 $A$ 有 $n$ 个卡片， $B$ 有 $m$ 个卡片，每张卡片都有一个生命值，现有 $d$ 次攻击，每次攻击任意减少一张卡牌 $1$ 点生命值(卡牌生命值为 $0$ 后就小消失)，问使玩家 $B$ 的所有卡片生命值都减少为 $0$ 的概率。
题解
- 考虑爆搜的复杂度为 共计 $6^{10}$ 个状态。
- 考虑优化，将卡片的生命值排序，因为顺序并不影响答案，每个状态即为上升序列的数量，计算可得状态数 $10^5$ 左右。
- 定义当前状态为：当前状态到玩家 $B$ 的所有卡片生命值都减少为 $0$ 的概率，记忆化爆搜即可。
E
题意
题解
F
题意
题解
G
题意
题解
H
模拟即可
I
模拟即可
J
题意
构造一个 $01$ 串，满足子序列 $00$ 的数量为 $a$，$01$ 数量为 $b$，$10$ 数量为 $c$， $11$ 数量为 $c$，存在不存在的情况。
题解
- 通过 $00,11$ 的数量可以分别求出 $0,1$ 数量，最终的 $01$ 串一定是一个特定 $01$ 串。
- 考虑 $0$ 往 所有 $1$ 里面从左向右插入的过程，没向右移动一次，子序列 $01$ 的数量 $-1$，$10$ 的数量 $+1$，暴力移动即可。
- 没考虑 $a,b,c,d$ 都为 $0$ 的情况， 自闭 $+1$。
K
题意
$n$ 个节点的树， 用 $k$ 个颜色染色(全部用完)，问方案数。$(n\le 2500)$
题解
考虑每个叶子节点。
- 叶子节点是一个不同于所有其他节点的颜色，即 $k·f(i-1,k-1)$。
- 叶子节点是同于其他颜色并且已经涂了 $k$ 了颜色，即 $(k-1)·f(i-1,k)$。
每个节点都可以看做父亲节点的儿子，所以答案和树的结构无关，即 $f(i,k)=k·f(i-1,k-1)+(k-1)·f(i-1,k)$，做一个简单做一个 $n·k$ 的 $dp$ 即可。