2020牛客暑期多校第八场

排名	当场过题数	至今过题数	总题数
32/685	4	6	11

A

solved by JJLeo

题意

简化后题意：给出一张二分图，每次操作加一条边或删一条边，每次操作后，如果左侧有点度数为\(0\)，输出\(-1\)，否则输出连通块数量减去右侧度数为\(0\)的点的数量，不强制在线。

题解

线段树分治模板题。

B

upsolved by

题意

题解

C

upsolved by JJLeo

题意

设 \(f(n)\) 是将 \(n\) 划分为三种 \(x,x,\cdots,x,x+1,x+1,\cdots,x+1,x+2,x+2,\cdots,x+2\)，且 \(x,x+1,x+2\) 都至少出现了一次的方案数。\(T\) 组数据，求 \(\sum\limits _{i=l}^r f(i)\)。(\(1 \le T \le 10^4,1 \le l,r \le 10^5\))

题解

设定一个阈值 \(M = 2000\)，对于 \(x < M\)，直接完全背包；对于 \(x > M\)，直接暴力枚举所有可能情况即可。

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发现无法跟榜时不要慌张，及时开别的题，说不定就发现模板题了。另外还是要加强对乱搞题的训练。