solved by JJLeo
简化后题意:给出一张二分图,每次操作加一条边或删一条边,每次操作后,如果左侧有点度数为$0$,输出$-1$,否则输出连通块数量减去右侧度数为$0$的点的数量,不强制在线。
线段树分治模板题。
upsolved by
upsolved by
upsolved by
upsolved by JJLeo
upsolved by
solved by JJLeo
CF原题,变成了四种,加了个万能牌。
题解证明最多$21$张一定可以构成$SET$,我们和空气斗智斗勇优化到了$O(32n^2)$,裂开。
upsolved by JJLeo
给出$n$个字符串,将每个字符串重复循环无限次,问得到的$n$个新字符串有多少个本质不同的公共子串,若有无限个输出$-1$。$(\sum|s_i| \le 3 \times 10^5)$
首先求出每个字符串的最小表示法(使用Lyndon分解,C++自带rotate()也可以很好实现循环移位),将每个字符串用其最短循环节表示(求出next数组,设$x$为最后一个位置的next数组值,字符串长度为$len$,若$(len-x)|len$则最小循环节长度为$len-x$,否则最小循环节长度为$len$),如果此时出现了$n$个相同的字符串,显然有无穷多个公共子串;否则由弱周期引理可以证明,对于两个字符串来说公共子串长度不超过长串的三倍,对于多个字符串来说,只需考虑最短串和其它串的公共子串的交即可。
具体来说,将除最短串外的串扩大到四倍,将最短串扩大到最长串的四倍,然后求这些字符串的公共子串数目即可。使用SAM来求过于繁琐还容易写锅,对于多串问题可以使用更为简便的广义SAM。只需将所有串插入广义SAM,然后对于每个串,将所有能到达的点标记,然后考虑所有标记数为$n$的节点即可。标记时只需按照字符串走一遍,每走到一个点不断跳link直到跳到的点已经被该点标记为止,这样每个字符串相当于标记了属于自己的SAM,而SAM节点数量是线性的,因此总复杂度为$O(n)$。
solved by Bazoka13
每次可以选择给定两个整数中的一个,并且选择的数字必须未被选过,输出最多选择的数字数量
类似于 $2-sat$ 的想法,每组数字互相建边后 $bfs$ 计算即可
solved by JJLeo
一共有$n$个物品,每个物品有一定的数量和权值。每次必须取一个前缀,即前缀中每个物品各取一个,问获得权值最大是多少。
显然每次取最大的前缀即可,记录下当前断点最小值,搞个优先队列即可。mjx及时发现本题数据范围可达$10^{19}$,使用了__int128,成功1A。
0min:开局分题
???min:看榜冲I
60min:WA2,K更签到ZYF冲K
87min:ZYF AC K
110min:CSK AC I,ZYF 冲G
145min:ZYF AC G,ZYF 冲A
237min:ZYF AC A
till end:进入垃圾时间