老张觉得比较简单,但我一道都不会做.
求和
把每个点到根的 $k$ 种权值和全部预处理出来,每次求出 $lca$ 回答询问.
时间复杂度 $O(nk+m\log n)$ .
二进制
考虑给定一个二进制串,如何判断能否重排成 $3$ 的倍数.
这显然只和 $0,1$ 的个数有关,注意到,当 $k$ 为偶数时, $2^k\bmod 3=1$ ,当 $k$ 为奇数时, $2^k\bmod 3=2$ .
于是当 $1$ 的个数为偶数时,一定有解,将 $1$ 都放在后面, $0$ 全部弄成前导 $0$ .
当 $1$ 的个数为奇数时,需要放一个 $10101$ ,剩下的 $1$ 依次放在前面, $0$ 弄成前导 $0$ .
这要求 $1$ 的个数 $\ge 3$ , $0$ 的个数 $\ge 2$ .
整理一下,即,不合法的情况只有两种: $1$ 的个数为奇数,且 $0$ 的数目不超过 $1$ ,或者 $1$ 的个数为 $1$ .
这些区间要么只有一个 $1$ ,要么只有 $1$ 个 $0$ ,或者没有 $0$ ,用 $set$ 维护所有 $0,1$ 的位置,用树状数组维护答案.
时间复杂度 $O(n\log n)$ .
染色
若不是二分图,显然可以被卡掉.若有度数 $\le 1$ 的节点,显然可以直接去掉.
于是只用考虑每个点的度数 $\ge 2$ 的二分图,不同的连通块可以分开做.
对于完全二分图 $K_{3,3}$ ,样例已经给出了卡掉的方法.
对于完全二分图 $K_{2,4}$ ,一边是 $(AB),(CD)$ ,另一边是 $(AC),(AD),(BC),(BD)$ ,就可以卡掉了.
如果有两个偶环,它们有公共点,且各自独有的点数目 $\ge 2$ ,也可以卡掉.
在一个偶环上构造出 $(AC),(AB),(BC)$ ,之后的点就不能染 $C$ 了.
再换一种颜色在另一个偶环上进行类似的构造,另一种颜色也没法染了.
当一个点的度数 $>3$ 时,一定可以找出两个这样的偶环,于是只考虑最大度数为 $2,3$ 的情况.
当所有点的度数为 $2$ 时,一定是个偶环,显然顺着环染色,是卡不掉的.
于是只剩下了有 $2$ 个点度数为 $3$ ,其余点度数为 $2$ 的情况.
这两个度数为 $3$ 的点之间有 $3$ 条边不相交的路径,只有它们的长度为 $2,2,k$ ,其中 $k$ 为偶数时,是卡不掉的.
而对于 $2,4,4$ 或者 $1,3,3$ 都有卡掉的办法.
整理一下,先把所有度数为 $\le 1$ 的点剥掉.
再对于每个连通块判断其是否为偶环,或恰有两个度数为 $3$ 的点,且两者间的路径长度为 $2,2,k$ ,其中 $k$ 为偶数.
时间复杂度 $O(m)$ .
双人猜数游戏
手玩了两个小时,喜提 $4$ 分.
按照题目中给的优先级枚举 $a,b$ 作为答案,尝试检验.
设 $f(i,a,b)$ 表示询问了 $i$ 次,若 $m=a,n=b$ ,则它们是否会被猜出来.
$i=1$ 时是边界情况,分情况讨论一下.
- 如果第一次问的是 Alice ,那么能猜出来,当且仅当把 $ab$ 拆成两个 $\ge s$ 的数字之积时方案唯一.
- 如果第一次问的是 Bob,那么能猜出来,当且仅当把 $a+b$ 拆成两个 $\ge s$ 的数字之和时方案唯一.
对于 $i>1$ 的情况,根据奇偶性判断这次是问的谁.
从可能的数对 $(x,y)$ 中找出 $f(i-1,x,y)$ 为 $0$ 的个数,若只有 $1$ 个,就可以把它猜出来了.
同时,若另一个人在第 $i+1$ 回合也能猜出这个数对,那么它就是答案了.
链上二次游戏
询问长度在 $[L,R]$ 内的链的权值和时,用长度 $\le R$ 的答案减去长度 $\le L-1$ 的答案.
于是只需要考虑如何计算长度 $\le k$ 的链的权值和.
考虑每个点的贡献,分情况讨论一下每个点会被算多少次,显然用线段树维护 $\sum a_i,\sum a_i\cdot i,\sum a_i \cdot i^2$ 即可.
时间复杂度 $O(n+m\log n)$ .
治疗之雨
这个是暗影打击装甲被削之前出的题.
先特判答案为 $-1$ 的情况.
- 当 $k=0$ 时,答案为 $-1$ .
- 当 $m=0$ 时,若血量上限 $n>1$ ,且每次扣血 $k=1$ ,答案也为 $-1$ .
对于剩下的情况,设 $E(i)$ 表示当前有 $i$ 点血,被暗影打击装甲打死期望需要的回合数.
由于 $E(0)=0$ ,所以可以不用考虑转移到 $E(0)$ ,也不用处理血量被打成负数的问题.
设 $f(i)$ 表示 $k$ 个暗影打击装甲攻击后,恰好对英雄造成 $i$ 点伤害的概率,容易预处理出来.
$$
f(i)=\frac{ {k\choose i}\cdot m^{k-i} } { (m+1)^k }
$$
设 $g(i,j)$ 表示当前血量为 $i$ ,一轮后血量变成 $j$ 的概率,讨论一下 $i$ 是否为 $n$ ,就可以根据 $f(i-j)$ 算出它.
于是对于血量 $i<n$ 的 $E(i)$ ,有转移
$$
E(i)=\sum_{j=1}^i E(j)\cdot g(i,j)+E(i+1)\cdot g(i,i+1)+1
$$
对于 $i=n$ 的情况,有转移
$$
E(i)=\sum_{j=1}^{i} E(j)\cdot g(i,j)+1
$$
直接做高斯消元,复杂度是 $O(n^3)$ 的.
它虽然不是稀疏矩阵,但注意到每次最多回 $1$ 点血,即, $E(i)$ 要转移到 $j>i$ 的 $E(j)$ ,只可能是 $E(i+1)$ .
于是就可以像树上高斯消元那样搞一搞,将每个 $E(i)$ 都表示成 $k\cdot E(1)+b$ 的形式.
根据转移方程
$$
E(i)=\sum_{j=1}^i E(j)\cdot g(i,j)+E(i+1)\cdot g(i,i+1)+1
$$
可以从前往后依次求出每个 $E(i)$ 的 $k,b$ .
而 $E(n)$ 的转移方程还没有用,把所有 $E(i)$ 代入到 $E(n)$ 的转移方程中,就可以解出 $E(1)$ ,代入求得 $E(p)$ .
时间复杂度 $O(T\cdot n^2)$ .