Alioth_ 的博客

Alioth_ 的博客

IOI2020国家集训队作业云做题记录

posted on 2021-08-19 17:20:30 | under 未分类 |

CF506E Mr. Kitayuta's Gift

最终串长度为偶数的情况下 考虑DP $f_{i,l,r}$表示最终串考虑了前后$i$个字母 给的$s$串还有中间$l$到$r$没用时的方案数 $g_i$表示最终串考虑了前后$i$个字母时给的串已经用完时的方案数 转移时根据$s_{l}$是否等于$s_r$讨论 看最终串左右两侧放哪个字母(转移一次左右各放一个相等的字母)但这个DP复杂度太高 考虑优化 发现$i$为阶段 最终其实是在一个自动机(或DAG)上走$i$步的方案数

即从abaac开始走$n$步到GOAL的方案数 但是这样自动机上点的个数是$n^2$的 考虑简化 发现点可以分为红绿两类 绿的点$s_l=s_r$ 于是可以简化路径

这样点的个数为$O(|s|)$级别 可以邻接矩阵自乘转移了

还有总长度为奇数的情况 这时从一个有两个字母的绿点无法直接结束(可以到终点再自环走一步结束) 我们考虑去掉这种直接结束的方案数 就是原图做一遍 然后只保留上述边并去掉终点自环再做一遍 方案数相减即可

CF512D Fox And Travelling

可以发现一个边双以及多个边双之间的点永远也遍历不到 考虑缩点 每个连通块缩成一棵树 如果有环则是有根树(根遍历不到)没有环则是无根树

有根树可以DP $f_{x,i}$表示选$i$个的方案数 合并时$f_{x,i+j}=f_{x,i}\times f_{y,j}\times \binom{i+j}{j}$其实就是个EGF

无根树就每个点做一遍 求和后发现所有大小为$i$的都多算了$n-i$次

最后所有的合起来做个EGF卷积即可

CF526G Spiders Evil Plan

首先考虑一次询问怎么做 如果$2y$比树的叶子个数多 那么所有边都可以选 否则就是选$2y$条可以到叶子的路径 考虑长链 选最长的$2y$条长链即可

我们发现每次选的一定经过直径两端之一 那么考虑随便一端 作为根 选择$2y-1$条长链就行了(因为此点一定是叶子)实现时可以把每个链搞个排名 求个前缀和之类的 如果不包括$x$ 那么找到从$x$所在长链到向上碰到(倍增跳)第一个已经选了的链的这个路径 要么把那个点所在链的后半部分替换成$x$所在路径 要么把最小的链替换成$x$所在路径 两者求max即可