CFR606

CFR606 div1

比较经典的模型:CF1276C Beautiful Rectangle

CF1276F Asterisk Substrings应该国人随手口胡

因为交一发要等20min才测,然后fail了两次,所以1h才过A,遂自闭

B也很败笔,先用20min写了个假容斥,又用20min写拍才终于想到反例并考虑怎么修,感觉应该能修但极度麻烦,冷静一下决定换个做法重新写,最后1h50min才过

菜的真实.jpg

CF1276A As Simple as One and Two

请先思考后再展开

只要判掉twone的o,其他情况都是无脑选择中间那个就是最优的

code

CF1276B Two Fairs

请先思考后再展开

当A不是割点显然为0,当B不是割点也是0

否则,答案就是$(去掉A后与B不连通)*(去掉B后与A不连通)$

code

CF1276C Beautiful Rectangle

题意:构造面积最大的矩形,在给出的$n \le 4e5$个数中选面积个填入,使得每行元素不同,每列元素不同

请先思考后再展开

不妨设$行数n \le 列数m$,接下来我们将通过构造法证明,当保证每种数在n以内时(与种类数无关),一定有解:

能将这些数分成n行使得每行的元素都不同很容易,我曾经的理解是选出行大小最小的若干个行丢进去,但这样破坏了列的信息怎么也不会搞。其实我们观察到,任意时刻一定只有两种大小(A和A+1),优先填A即可,相当于一个表格,每列从上往下填,填完这列就换到下一列。先填入大小为n的数,再填比n少的数,这样就能保证所有大小为n的数恰一列,其他数最坏是相邻的两列,最坏中最坏的情况是只有中间的一行是没有这种数的。即便如此,通过拧魔方即$A’*{i,(i+j)\%m}=A*{i,j}$可以保证不重。

$O(nlogn)$,code

CF1276D Tree Elimination

题意:给出一棵大小为$n \le 2e5$的树,初始每个节点都有标记,按照题目给出顺序枚举所有边,当两端点都还有标记时,去掉其中一个标记并将那个点的编号写下,问能得到多少种不同的编号序列

请先思考后再展开

明显就是按题意模拟的树形dp,代码很短,但调了很久
$$
将孩子按照边权排序,集合S1为小于(x,fa)的部分,S2为大于的部分
\\
h(x)=(x,fa)的方向为(x \to fa)=\prod_{i \in son} f_i+\sum_{i \in S2} (\prod_{j<i} f_j )h_i(\prod_{j>i} g_j ),i表示哪个连向x
\\
f(x)=fa会在(x,fa)后用到=(\prod_{i \in S1} f_i*\prod_{i \in S2} g_i)+\sum_{i \in S1} (\prod_{j<i} f_j )h_i(\prod_{j>i} g_j )
\\
第一部分表(fa \to x),第二部分i表示哪个连向x
\\
g(x)=fa会在(x,fa)前用到=\prod_{i \in son} f_i+\sum_{i \in son} (\prod_{j<i} f_j )h_i(\prod_{j>i} g_j )
$$
code

CF1276E Four Stones

咕咕咕

CF1276F Asterisk Substrings

题意:给出一个字符串S,问${S,对于每个i将第i个字符替换成?得到的字符串}$这个集合内所有本质不同子串,$|S| \le 1e5$

请先思考后再展开

将S的本质不同子串先计算,剩下就是求本质不同的$a?b$这样的字符串,枚举a并得到其end-pos集合,那么合法b数量等价于在反串的后缀树上,若干个叶子(集合位移两格)到根的链并的所代表子串数。

因为不是联通块而是到根的链并,显然反串后缀树上$(fa \to x)$的边权定为$len_x-len_{fa}$,那么就是强制加入根的点集的最小联通块边权和,经典地放到dfs序上set解决,启发式合并维护,预处理st表lca后是$O(nlog^2n)$,code

口胡另一个$O(nlog^2n)$的做法:树上dsu,维护重子树的虚树,用线段树上二分找到祖先中第一个在虚树上的(见套路集锦)

$O(nlogn)$做法:将树上dsu改成线段树合并,没细想,可看rose代码

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/bea389e9.html
转载请注明出处,谢谢!