模拟赛 14 题解

贪心+结论+数论

认识到了自己的弱小（

A.淘淘蓝蓝之地主的硬币

发现 $k$ 个钞票一定是给用时最大的 $k$ 个人更优。

所以排序之后，前 $n-k$ 个人是吃面包的，时间是累加的。

注意：$\max a_i$ 可能大于前面所有人的和。

$k$ 不保证小于等于 $n$!!!!!!!

B.淘淘蓝蓝喜欢01串

原题：CF1430D

可以先用一个栈把所有连续的相同长度子串提取出来。

我们贪心的去想，每次操作都要删一个长度最长的前缀，而我们还要删一个字符。

是的，我们可以让这个字符处在某个前缀的位置，这样删的时候就可以多保留一些字符了。

具体删在怎样的前缀呢？不难想到，是长度大于1的。

这样我们就可以从前往后找每一个长度不为 $1$ 的前缀，把它一直删到 $1$ 再向后找就可以了。

注意可能都是 $1$，这时候随便删就好了。

注意 $i$ 和 $j$ 的大小关系。

C.淘淘蓝蓝之幻影树

考试没猜出来，哭了QAQ。

首先我们发现两个队伍打擂台赛，正着来和反着来效果是一样的。

这里可以简单理解一下：

如果赢了，那说明前面的人打死了所有的对手，而从后开始不会使胜负状态改变。

同理，输了的话，说明这个队伍已经全部被打败，每个人注定会被某个敌人打败。。

这样，我们把 $k$ 倒序后，就可以考虑 $p$ 到根的路径了。

具体的，我们可以处理出 $g[u][i]$ 表示在 $i$ 号节点到根的路径上，第一个节点 $i$ 被打败。

这个在dfs过程中可以由父亲传给儿子。

查询的时候把 $k$ 个数依次向上跳，直到跳出根或者用完为止。

还存在一种 $O(sum*m\log n)$ 的做法，不用倒序。

正序从根开始，依次看每个人能不能打败从当前点到 $p$ 的所有节点。

如果不能，就从 $p$ 倍增向上跳，直到跳到第一个当前人死掉的位置，作为新的开始。

判断的时候，枚举每种能打败当前点的颜色，看它在路径上是否出现过。

维护一个链上的前缀和就好了。

D.淘淘蓝蓝之电电鼠大战御坂美琴

吐槽题面……

发现 $d_i$ 都是 $n$ 的约数，这也许可以优化背包的复杂度。

我们对一个 $d$ 的选法，它一定占了 $p*n+r$ 这样的体积。

那么我们可以在 $\mod n$ 的剩余系下进行 $dp$ ，先不管 $W$ 的限制。

设 $f[i][j]$ 表示考虑到了前 $i$ 个约数，所用的和在分别 $\mod \frac n {d_i}$ 下的和为 $j$ ，所能得到的最大/n的个数。

转移可以从 $f[i-1][j-k*d[i]]+(a[i]-k)/(\frac n {d_i})$ 转移，表示选了 $k$ 个作为余数，剩下的都除了 $n$ 统计答案。

注意上限到 $\frac n {d_i}$ 。

最后统计答案时枚举余数 $i$ ，注意 $n$ 的个数不超过 $\frac {W-i}{n}$。