八月杂题选做
s_r_f
·
·
个人记录
CF590E Birthday
建出AC自动机.
考虑建出字符串之间的包含关系图.
因为\sum\limits_{i=1}^n |s_i| \leq 10^7,所以我们不能在AC自动机上暴力跳,而是在AC自动机上用并查集维护fail树上的上一个点,然后暴力跳trie树上的父亲直到跳到一个存在的字符串即可.
然后O(n^3)把多余的边建出来,直接求最长反链方案即可.
最长反链方案怎么求?
建出拆点二分图并求出其最大匹配.
考虑求出拆点二分图的最大独立集,具体操作是:
从每个没有匹配的左部点开始dfs,
左->右的边只走没有匹配的,
右->左的边只走匹配的边,
然后所有dfs到的左部点和未dfs到的右部点就组成了最大独立集.
然后,左右都在最大独立集里的点i就在最长反链里.
O(n^3+\sum\limits_{i=1}^n |s_i|).
P4304 [TJOI2013]攻击装置
二分图匹配,答案=总点数-最大匹配数.
复杂度O(|V|^2)=O(N^4),代码很短.
CF522D Closest Equals
把询问离线然后随便扫描线一下即可.
O(n\log n)
P3196 [HNOI2008]神奇的国度
学习弦图知识.
弦图,即所有的长度>3的环之间都有"横叉边"的环,也就是说不存在一个环使得其除了环边之外点之间没有边并且长度>3.
弦图有一些重要知识:
1.
对于一般图,有最大团数 \leq 最小色数 最大独立集 \leq 最小团覆盖
而在弦图中,有最大团数 = 最小色数 最大独立集 = 最小团覆盖
2.$ 单纯点$:
在图G中, x为单纯点当且仅当 \{ 和x相连的所有点 \} + \{x \} 构成的点集的导出子图是一个完全图.
在弦图中,至少有一个单纯点;
在不是完全图的弦图中,至少有两个不相邻的单纯点.
3.$ 完美消除序列$:
完美消除序列是一个点序列,保证a_i是集合\{ a_i,a_{i+1},...,a_{n} \} 组成的图的导出子图中的单纯点.
一张图G是弦图,当且仅当G存在完美消除序列.
4.$ 完美消除序列的求法$:
a_n,a_{n-1},...a_1$从大到小求$.
先随便给定一个a_n,然后每次加入点的时候都取和当前已经确定的点连边最多的点作为下一个a_i.
可以O(n^2+m)暴力或者O((n+m)\log n)用线段树维护max.
5.$ 完美消除序列的性质$:
求最小色数可以在完美消除序列上从后往前贪心染色.
同时最小色数也 = \max\limits_{x=1}^{n}\{ 在完美消除序列上在x之前,且与x相邻的点的个数 + 1 \}
求最大独立集大小可以在完美消除序列上从前往后贪心取点.
6.$ 判断一个序列是不是完美消除序列$:
对于每个a_i,找到和它之间有边的,最早在序列中a_{i}之后的部分出现的a_x(x>i),满足a_x一定和其他点有连边即可.
复杂度O(m\times 一次查询边集的复杂度 ),如果n比较小就是O(n+m),否则就是O(n+m\log n).
而这道题我们只需要求出弦图色数即可.
O(n^2)$ 或 $O((n+m)\log n).
BZOJ1242/ZJU1015 Fishing Net弦图判定
判断是否有完美消除序列即可.
O(n^2+m)$ 或 $O((n+m)\log n).
P4716 【模板】最小树形图
最小树形图板子题.
O(m+n\log m),$不过感觉特别慢不知道为啥$,$可能有地方写假了吧$.
P4983 忘情
wqs$二分$+$斜率优化$.
P5785 [SDOI2012]任务安排
斜率优化.
需要在队列上二分.
P3538 [POI2012]OKR-A Horrible Poem
建出后缀数组,以支持O(1) LCP.
那么就可以快速check一个数字是否是[L,R]的一个循环节.
又因为答案必然是r-l+1的因数,所以直接一个一个除即可.
O((n+q)\log n).
P4007 小 Y 和恐怖的奴隶主
考虑用一个三元组(a,b,c)来表示状态,其中
a$为生命值为$1$的随从数量$,b$为生命值为$2$的随从数量$,c$为生命值为$3$的随从数量$.
经过简单枚举可以发现状态总数在m=3,k=8时达到165,这个165就是状态总数的上界.
不难发现有一个O(T\log n \times 166^3)的暴力矩乘做法,但是它太慢了.
我们考虑,把矩阵乘矩乘的次数减少,而是用矩阵乘向量来代替.
考虑K进制矩阵快速幂.
即对于值域内每个K^m,预处理出转移矩阵的K^m\times 1,K^m\times 2,K^m\times 3,...K^m\times (K-1) 次幂即可, 共需O(K\log_K(1e18))次矩阵乘法.
对于询问,我们把询问按照n从小到大排序,每次n变大的时候就直接利用预处理出来的矩阵乘到当前向量上即可,每组询问最多有O(\log_K(1e18))次矩阵乘向量.
均衡一下复杂度,大概在4-6的时候最优,我的代码里选取的K=4.
然后矩乘卡卡常数即可:
P6730 [WC2020] 猜数游戏
考虑建出一张有向图G, 有边i->j当且仅当存在一个正整数m使得a_i^m和a_j在模p意义下同余,然后在图G上计算答案.
Part1:建图
subtask1:模数为奇质数
模p意义下存在原根,设为g.
那么每个a_i都可以表示成g^{k_i}
考虑求出一个数a_i的指标和\phi(p)的\gcd的值k_i(k_i|\phi(p)):
显然k_i为满足a_i^{\phi(p)/k} 模p之后为1的最大的数.
枚举每个质因数p求它的次数,这个工作就可以在O(d(\phi(p)) \times \log p) 的时间内完成.
那么, i->j存在当且仅当k_i|k_j.
这样就可以O(1) check是否存在边i->j了
subtask2:模数为奇质数q的t(t>1)次幂
模p^k意义下也存在原根.
不难发现我们可以用同样的方法求出所有k_i,但是这回一个数可能会是q的倍数,我们记a_i的因数分解中存在的q的个数为m_i.
这次我们怎么check i->j是否可以连边呢?
首先如果m_i=m_j=0,那么就直接用上一个subtask的做法即可.
如果有一个m=0,而另一个m ≠ 0,那么边i->j不存在.
如果m_i≠0,m_j≠0,那么我们可以直接计算出可能使a_i^z=a_j的数字z,z=m_j/m_i,然后直接快速幂解决.
那么就可以O(\log p)的复杂度内check是否存在边i->j了
如果害怕T飞的话可以求出原根用光速幂,不过O(n^2\log p)实际情况下也能过.
Part2:计算答案
建出图之后,我们考虑怎么计算答案.
考虑一个a_i对答案的贡献.
有一个想法是a_i在答案中存在的条件为当且仅当没有任何数能够表示出它,记这些数的个数为cnt,那么a_i对答案的贡献就是2^{cnt}.
但是这样做忽略了环的情况,只能获得10pts.
举个例子,如果n=2,图G中存在边(1,2),(2,1),如果按照这种算法计算出来的答案就是2,而正确答案是3.
那么这个问题怎么解决呢?
不难发现如果有一个强联通分量S, S内部的所有点必然是能两两连边的,所以我们可以给一个强联通分量内的点强制一个顺序,就可以正确的计算出答案了.
Bonus:如何解决n\leq 10^5,p\leq 10^{18}
CF700E Cool Slogans
在SAM上可持久化线段树合并记录每个点的endpos集合,然后在SAM上dp即可.
O(n\log n)
CF438E The Child and Binary Tree
设答案多项式为F,输入的多项式为G,则F=G^2F+1,解得F=\large \frac{2}{ 1+\sqrt{1+4G} },
多项式开根,求逆即可.
O(n\log n).
IOI2019 视觉程序
考虑把距离转成切比雪夫距离然后分别check即可.
O(H+W)$次操作$,$用到的数的总和为$O(HW)$级别$.
CEOI2020 题解