Comet OJ - Contest #11 题解&赛后总结

比眉伴天荒 2023-08-17 16:04 107阅读 0赞

# Solution of Comet OJ - Contest \#11 #

## A.eon ##

\-Problem designed by Starria-

在模 10 意义下，答案变为最大数的最低位(即原数数位的最小值)和原数最低位的差。

令$S$为输入数字串，则答案为 $(\\min\_\{i=1\}^\{n\}S\_i-S\_n)%10$ 。

时间复杂度 $O(n)$ 。

## B.usiness ##

\-Problem designed by Winniechen-

这是一个很显然的动态规划问题。

令$g\_\{i,j\}$表示第$i$天，手里有$j$个节点，最多会返还多少节点。

第$i$天获得节点的过程转移为$g\_\{i,j+f\_j\}=\\max(g\_\{i,j+f\_j\},g\_\{i-1,j\})$，而对于存储节点的过程，只需对每一种存储方式做一个完全背包即可。

## C.elebration ##

\-Problem designed by Starria-

定义长度不超过 $\\frac\{n-1\}\{2\}$ ，且不含重复颜色的段为合法的段。记 $pre\_x$ 为以 $x-1$ 为右端点的合法段最远的左端点， $nxt\_x$ 为以 $x$ 为左端点的合法段最远的右端点。

枚举题面所述三元组中的 $a,b(a<b\\le nxt\_a+1)$ ，则合法的 $c$ 是 $(b,nxt\_b+1\]$ 与 $\[pre\_\{a\},n\]$ 的交集。也就是说，当 $pre\_\{a\}>nxt\_b$ 时， $b$ 的贡献是 $nxt\_\{b\}+2-pre\_\{a\}$ 。

每次向右移动 $a$ 时，将 $(nxt\_a+1,nxt\_\{a+1\}+1\]$ 区间内的 $b$ 的贡献挂在 $nxt\_b$ 上，在移动 $pre\_\{a\}$ 时将经过的贡献减去即可。

时空复杂度 $O(n)$ 。

利用数据结构可以简单地维护交集，这哪里卡得掉没有刻意去卡。

## D.isaster ##

\-Problem designed by Winniechen-

对于一个图很难处理，所以考虑将图简化，直接建立一棵生成树达到原来的效果。

由于我们询问的时候，要求只能走到编号 $\\le y$ 的点，所以保留的边两端点编号的 $\\max$ 应当尽可能小，这样就有更多的边可以被一次询问用到。

所以我们将边按照两端点的 $\\max $ 排序，建立一棵 [kruskal 重构树][kruskal]。（这个不会自行解决）

在此基础上维护一棵线段树和一个倍增数组，每次找到 kruskal 重构树上能到达的最高点，然后询问子树乘积和，修改就直接修改即可。

## E.ffort ##

\-Problem designed by Winniechen-

假设总攻击次数为 $k$ ，那么我们要把这 $k$ 次相同的攻击分配给 $n$ 个不同的人，根据插板法来看也就是在这 $k$ 次攻击里插 $n$ 个板。记令攻击次数恰为 $k$ 的方案为 $ans\_1$ ，插板方法为 $ans\_2$ ， $k$ 的贡献即为 $ans\_1\\times ans\_2$ 。

维护 $k$ 次项系数为一个第 $i$ 种数据结构攻击次数中插 $k$ 个板的方案的多项式 $F\_i(x)$ ，那么 $\[x^k\]F\_i^\{a\_i\}(x)$ 就是第 $i$ 种里插 $k$ 个板的方案数了。

由于我们只有 $n$ 个板，所以多项式长度始终不超过 $n$ 。在模 $x^\{n\}$ 意义下做多项式快速幂，最后再将 $m$ 个多项式合并即可。

整体复杂度最优可以达到 $O(nm\\log n)$ ， std 写的是 $O(nm\\log n\\log a\_i)$ 。

## F.arewell ##

\-Problem designed by negiizhao-

令 $E\_S$ 表示点集 $S$ 内部的边数， $E\_\{S,T\}$ 表示 $S$ 与 $T$ 之间的边数， $F\_S$ 表示 $S$ 是 DAG 的方案数。

枚举入度为 0 的点集 $T$ ，转移为 $F\_S=\\sum\_\{T\\subseteq S,T\\neq \\varnothing \}(-1)^\{|T|-1\}F\_\{S\\backslash T\}2^\{E\_\{T,S\\backslash T\}\}$ 。

$S$ 中入度为 0 的点集的每个子集都会算一次，对其简单容斥即可得到系数 $(-1)^\{|T|-1\}$ ，而系数 $2^\{E\_\{T,S\\backslash T\}\}$ 来自于 $S\\backslash T \\rightarrow T$ 的边只能断掉或指向 $T$ 。

对DAG计数稍有了解的人可以从这里开始阅读

$2^\{E\_\{T,S\\backslash T\}\}$ 可以写作 $2^\{E\_S - E\_T - E\_\{S\\backslash T\}\}$ ，因此原式化为$$\\frac\{F\_S\}\{2^\{E\_S\}\}=\\sum\_\{T\\subseteq S,T\\neq \\varnothing \}\\frac\{(-1)^\{|T|-1\}\}\{2^\{E\_T\}\}\\ast \\frac\{F\_\{S\\backslash T\}\}\{2^\{E\_\{S\\backslash T\}\}\}$$

对上述式子进行[子集卷积][Link 1]即可。

对DAG计数稍有了解的人可以从这里开始阅读$\\surd$

## 赛中后吐槽总结 ##

*  BY Winniechen&Starria

### 出题人的一些吐槽 ###

*  为什么10min还没有人过B （在10min的时候
 *  为什么大家D都一直在Wa啊！
 *  为什么有人会写树状数组啊！
 *  CD是不是顺序反掉了啊……（这是Starria的锅！
 *  B看起来出难了（手动狗头）
 *  怎么有人1h不到就出F了！
 *  （看起来F卡人常数了….
 *  听说有人觉得题面不好，我不这么认为
 *  1.5h的时候，终于六道题的一血都出来了，这让出题人很激动
 *  2h的时候，终于有人A掉5道题了
 *  2h 10min的时候，终于有 >10个人切 四道题了
 *  2h 23min的时候，终于有第二个切E的人了！
 *  在最后的10min的时候，发现supy的F被卡常了
 *  然后终于出现了这场比赛唯一一个AK的选手！
 *  最后看起来，CD放反了，EF放反了
 *  为啥D题大家都没有发现$a\_i ,v \\le 10^9$会比$998244353$大
 *  为啥$B$题会有那么多人wa那么多发
 *  C题出题人为何如此毒瘤
 *  为何题面会出成这个样子
 *  尽请期待后天晚上的视频题解，届时出题人Winniechen和Starria会为大家讲解这次试题，并解答一些花絮！

### 出题人的一些自我坦白与反思总结 ###

*  其实原来的题目不是这个样子的，只不过在考试前三天，F的算法出现了问题，今天才出好这个F的数据，所以让人感到抱歉
 *  每道题的数据都被dreamoon加强过，原来我的数据菜得要死
 *  然后两位（三位）出题人都是鸽子，都很能拖
 *  主要负责人（Winniechen）多数时候不能及时的传递信息，并且不参照出题手册出题，让AA姐等工作人员感到棘手，在此我深表歉意
 *  谢谢大家支持！
 *  出题人的QQ：Winniechen 1967199892 , Starria 972808330

转载于:https://www.cnblogs.com/Winniechen/p/11566727.html

[kruskal]: https://www.cnblogs.com/zwfymqz/p/9683523.html
[Link 1]: http://vfleaking.blog.uoj.ac/slide/87#/