2021牛客暑期多校第八场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 38/1357 | 6 | 10 | 11 |
A¶
upsolved by 垃圾出题人
题意¶
爬
题解¶
爬
B¶
upsolved by JJLeo
题意¶
\(n\) 个人排成一个队列，第 \(i\) 个人生命值为 \(h_i\)，你有以下两种操作：
- 对第 \(i\) 个人造成 \(d_i\) 点伤害，花费 \(m_i\)，其中 \(1 \le i \le 4\)。
- 对前四个人造成 \(40000\) 点伤害，花费 \(m_5\)。
一次操作后如果有一些人生命值 \(\le 0\) 则他们就死了，将被移出队列，后面的人会补上。
求将所有人打死的最小花费。(\(1 \le n \le 20\)，\(1 \le h_i \le 10^5\))
题解¶
我们考虑记录当前队列前四个人是哪四个人 (或空位)，状态数不超过 \(\sum \limits _{i=0}^4\dbinom{20}{i} = 6196\)。
我们将操作 2 称作 AOE，因为 \(h_i \le 10^5\)，每个人最多受 \(2\) 次 AOE 后还能存活，可以记录前四个人各受到了多少次 AOE，状态数不超过 \(3^4\)。
单体伤害显然没法记打了多少，不妨令每次使用单体攻击就直接打死一个人，考虑直接转移，枚举每次放 AOE 或者用单体杀死一个人，但这是不正确的，因为有可能在一个人受到的单体伤害并非都在最后这个位置受到的，我们还需要记录每个人之前经过到哪些位置，状态数不超过 \(4^4\)。
这样状态数太多了，可以发现很多状态是废的。对于受到的 AOE 次数，位置靠前的受到的次数不少于位置靠后的次数，因此必须有序，有效状态不超过 \(15\) 个；对于每个人经过的位置，每个人必然经过目前所在位置，除此之外第 \(1,2,3,4\) 个人能经过的位置至多有 \(3,2,1,0\) 个，因此有效状态不超过 \(8\times4\times2=64\) 个。
还需要预处理一个背包，表示对于每个位置集合，只使用这些位置的技能打对应血量所需要的最少花费，这样选择用单体伤害杀死一个人的时候就可以根据其经过的位置集合直接 \(O(1)\) 获取费用，设 \(H\) 为最大生命值，时间复杂度为 \(O(2^4H)\)。因为伤害可以溢出，还需要做一个后缀最小值。
以上就是出题人给出的题解，事实上最恶心的坑他完全没说，离谱出题人先 \(\sum\)。
最坑人的一个地方在于，如果一个人在位置 \(p\) 被单体伤害杀死，那么背包所处理出的方案必须使用了在这个位置对应的技能，换句话说就是致命一击是要在这个位置产生的，否则他在之前的位置就死了却没有移出队列，那么其它人所经过位置集合就是错的。
那么我们再处理出每个位置集合中必须包含最左侧位置所造成伤害的背包，再做后缀最小值，这样看起来就对了。实际上还是错的！这里不能求后缀最小值，因为可能你对应方案造成的伤害非常溢出，导致还没到最左侧位置所造成的伤害就已经把它打死了，因此我们要保证溢出伤害不能 \(\ge\) 最左侧一次造成的伤害，这可以将后缀最小值改为单调队列来得到答案。
然而这样还缺了一种情况，那就是先用单体伤害但没打死，然后又被一次 AOE 给打死了，这样一次 AOE 后会有数个人一起死，而且因为是 AOE 杀死的，不要求单体伤害的致命一击是在这个位置产生的，因此最开始的背包数组还要保留。考虑释放 AOE 的时候枚举哪些人会死，将其中 AOE 没打死的用对应位置集合的单体伤害的费用加上，因此复杂度还需要乘上一个 \(2^4\)。注意有一些人是会被 AOE 直接打死的，因此只需要枚举其它人死不死，可以减小常数。
上述两种情况在死人后都需要模拟后续补人情况，以及为移动的人更改其位置集合，稍微模拟一下即可，如果原状态不满 \(4\) 个人则说明后面已经没人可补了，否则根据最后一个人的编号就可以确定补进来的人。
最后，当前队列前四个人是哪四个人 (或空位) 可以先 dfs 出所有状态，再用一个 \(21\times21\times21\times21\) 的四维数组来存每个状态的 id，这样就可以不用开以 vector 为键值的 map 了，剩掉这个 \(\log\) 后就可以顺利通过本题了。运算量大概是 \(6196\times 15 \times 64 \times 2^4=95\,170\,560\)，实现过程图方便用了一些 vector 增大了常数，但枚举哪些人死的 \(2^4\) 跑不满，因此可以通过。
C¶
upsolved by 2sozx
题意¶
给定一个联通图，给每个点染 \(R,G,B\) 三色之一，如果一条边链接了相同的颜色，那么这条边将被删除，一个染色方案是合法的当且仅当边删除后图依然联通。构造一个合法的染色方案满足下面两个条件其中一个。
- \(R,G,B\) 颜色出现次数相同。
- 存在一个出现次数最多的颜色使得没有一条边链接的点均为这个颜色。
\(n \le 3\times 10^5, m\le 5\times 10^5\) 且 \(n\) 是 \(3\) 的倍数。
题解¶
证明几个结论：
- 对于一个图的任意 dfs 树，所有叶子结点不会有边。
如果叶子结点有边，那么 dfn 序小的在遍历的时候一定会走到另一个叶子上，这样 dfn 序小的点就不是一个叶子结点了。
- 对于一棵树黑白染色，黑白颜色出现次数差的绝对值不超过叶子结点的个数。
考虑将整棵树划分成很多条链，每条链均已叶子为尾部，显然链数等于叶子个数。考虑每条链对于颜色出现次数差的贡献，仅可能为 \(0\) 或者叶子颜色出现次数 \(+1\)，因此总体出现次数差一定不超过叶子结点的个数 。
- 如果黑白染色后两种颜色均出现 \(\ge \dfrac{n}{3}\) 次，那么可以新加一种颜色使得三种颜色均出现 \(\dfrac{n}{3}\) 次。
考虑黑色出现次数为 \(\dfrac{n}{3} + x\) 次， 白色出现次数为 \(\dfrac{n}{3} + y\) 次，如果有合法的方案一定是将黑色替换 \(x\) 次， 白色替换 \(y\) 次，考虑按深度替换。每替换一次黑色，最多会 ban 掉一个白色使得这个白色不能被替换，白色同理，因此最多 ban 掉 \(x + y\) 个颜色，由于 \(x + y = \dfrac{n}{3} \le \dfrac{n}{3}\) ，因此这样的构造即可将三种颜色均出现 \(\dfrac{n}{3}\) 次。
G¶
upsolved by
题意¶
不会（x
题解¶
H¶
upsolved by JJLeo
题意¶
题解¶
I¶
upsolved by 2sozx Bazoka13 JLK?
题意¶
德扑，你有俩牌，桌上有五张，五个对手各有随机两张，你比所有人都厉害的概率是多少。
题解¶
模拟略，如果你当前能比某两张牌强，在这两张牌连条边即可，即可转化为询问大小为 \(5\) 的匹配有多少个。
首先我们枚举两个匹配，然后把她们连的边就都不考虑了，在其余的考虑三个匹配即可。
考虑三边的匹配，考虑容斥即可，已存模板，每次看到这可以对着模板想想。
总复杂度是 \(O(m^3)\) 的。
记录¶
0h：CSK直接发现大签到，爆冲。看起来K也是签到，爆冲，寄了。MJX看D是签到，给ZYF喂了一下ZYF乍一下没听明白，MJX直接写了，过了。CSK继续爆冲，又寄了。看A是个大水题，但是题面让人恶心，测试题意交了两次寄了。
1h：CSK继续爆冲，寄了。A好像有个corner case 改了过了。所以为什么会有抄了 0 行代码还能错的呢？
2h：CSK和MJX想了好几次K还是感觉没啥问题，又寄了。MJX和ZYF看了看J，感觉好蠢，树上扫一遍就可以，直接写，过了。看F，感觉暴力bitset可过(?，直接冲
3h：交上去WA了，MJX和CSK准备K直接随便跑跑取个最优解得了，然后过了(?。MJX看ZYF代码，发现自己起点和终点直接寄了，改了就过了。
结束，下班！