======2020牛客暑期多校第八场====== [[https://ac.nowcoder.com/acm/contest/5673|比赛链接]] =====A.===== **solved by JJLeo** ====题意==== 简化后题意：给出一张二分图，每次操作加一条边或删一条边，每次操作后，如果左侧有点度数为$0$，输出$-1$，否则输出连通块数量减去右侧度数为$0$的点的数量，不强制在线。 ====题解==== 线段树分治模板题。 =====B.===== **upsolved by** ====题意==== ====题解==== =====C.===== **upsolved by ** ====题意==== ====题解==== =====D.===== **upsolved by ** ====题意==== ====题解==== =====E.===== **upsolved by JJLeo** ====题意==== ====题解==== =====F.===== **upsolved by ** ====题意==== ====题解==== =====G.===== **solved by JJLeo** ====题意==== CF原题，变成了四种，加了个万能牌。 ====题解==== 题解证明最多$21$张一定可以构成$SET$，我们和空气斗智斗勇优化到了$O(32n^2)$，裂开。 =====H.===== **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)$。 =====I.===== **solved by Bazoka13** ====题意==== 每次可以选择给定两个整数中的一个，并且选择的数字必须未被选过，输出最多选择的数字数量 ====题解==== 类似于 $2-sat$ 的想法，每组数字互相建边后 $bfs$ 计算即可 =====J.===== **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：进入垃圾时间 =====总结===== * MJX这场疯狂划水 * CSK要及时与队友讨论思路，同时思路的整理要更快速 * ZYF发现无法跟榜时不要慌张，及时开别的题，说不定就发现模板题了。另外还是要加强对乱搞题的训练。