A. 排球

Subtask 1,2

在读取输入的过程中,我们可以维护 sx,sy 两个变量,这两个变量分别表示第一支球队当前得了 sx 分,第二支球队当前得了 sy 分。在读入一行之后,更新这两个变量的值,然后判断当前这一局是否已经结束

判断的过程如下

1.如果 sx25sx>sy+1 ,那么说明第一只球队获胜

2.如果 sy25sy>sx+1 ,那么说明第二只球队获胜

3.否则当前这一局还没有结束

如果某一支球队获胜了两场,那么直接退出循环,输出哪只球队在大局获胜即可

B. 麻将

Subtask 1

暴力枚举所有分解情况即可。

Subtask 2

容易发现此时不存在任何编号的牌可能组成顺子,即只能通过刻子的方式胡牌。

直接判断每个位置是不是 x 的倍数即可。

Subtask 3

考虑贪心:

对于最小的非 0 的数字,优先匹配刻子总是比匹配顺子优。所以每次将最小的非 0ai 先对 x 取模,然后剩下部分必须用顺子匹配,如果无法匹配完说明无解。

如果将所有位置都变成 0 了说明合法。

时间复杂度 O(n2)

另解

考虑对原序列进行差分。令 b0=0,设 Δbi=bibi1,那么每次操作等价于选择一个 x,让 Δbx+1,Δbx+k1。如果最后差分数组整体为 0,则符合条件。

同样可以从左往右贪心。这样进行贪心的过程只有两个位置受到了影响。时间复杂度可以达到 O(n)

C. 二八定律

Subtask 1

考虑对于所有 n 个人进行状压枚举,枚举哪些人被我们选定,然后分别计算 A,B,确定答案,时间复杂度O(2n)

Subtask 2

首先我们将按数据从大到小对数据进行降序排序。对于每个前缀,我们将计算相应的数字 AB 。记 sum 为数据总和,记 prei 表示[1,i]这个前缀中数据的和,通过枚举 i ,我们可以得到 A=inB=preisum,然后对于所有的 i 求出 BA 的最大值。至于排序可以使用冒泡排序、选择排序、插入排序等排序算法,做到O(n2)的时间复杂度

Subtask 3

可以采用归并排序等算法,或者使用内置的 sort 做到时间复杂度 O(nlogn)

D. 矩阵

Subtask 1,2

容易发现最终结果与操作顺序无关,可以枚举每个 p 是否反转,然后逐个判断是否合法。

时间复杂度 O(n22n)

Subtask 3,4

容易发现,Li,i 一定等于 0,且 Li,j 一定等于 Lj,i。考虑对每个位置按被操作次数奇偶性进行染色:

其中红色表示对角线上的格子,对角线上带紫框的表示 (pi,pi),蓝色的表示操作奇数次,紫色表示操作了偶数次。可以看出,紫区,白区,红区中矩阵 A 的数字一定要为 0

也就是说,如果令 P={pi}Q={x|x[1,n],xP},那么 i,jP,Ai,j=0i,jQ,Ai,j=0

考虑构造一张 n 个点的无向图 G=(V,E),边 (i,j)E 当且仅当 Ai,j=1。容易发现,P 对应点集内没有边,Q 对应点集内也没有边。即此时 G 一定是一张二分图。

容易证明 G 为二分图也是有解的充分条件。

假设 P 对应点集为黑点,那么构造方案等价于给出图的一个黑白染色方案,使得黑点数量尽可能少的前提下黑点集合字典序尽可能小。

容易证明,对每个连通块的两种染色方案中,贪心取黑点数量尽可能少的前提下黑点集合字典序尽可能小的方案一定更优。

最后把所有黑点标号排序输出即可。

时间复杂度 O(n2)

E. 序列

Subtask 1

输出所有数的按位或和即可。

Subtask 2,3

我们可以设计一个 dp 算法:

fi 为将前 i 个数拆分成若干个子串的价值和最小值,显然有 fi=min{fj1+S(j,i)},其中 S(l,r) 代表子串 [l,r] 的价值。

暴力做就可以做到 O(n2) 了。

Subtask 4

然后我们发现一个事实:对于一个 i,只有 O(loga) 种不同的 S(j,i),因为 j 减小时区间按位或和如果增大必定为某一位从 0 变为 1

那么我们可以对一个固定的 i,求出 k 个区间 [l1,r1],...,[lk,rk] ,满足 1=l1r1<l2r2<...<lkrk=i ,使得对于每一个区间 j[1,k] 满足 x,y[lj,rj],S(x,i)=S(y,i) ,并且对于处于不同区间的位置来说其 S 不同

同时对于每一个区间都可以维护区间中 f 的最小值,那么暴力处理所有 S(j,i) 不相同的区间及其 fj1 的最小值,时间复杂度 O(nloga),可以通过所有数据。

F. 树的重心

Subtask 1

暴力枚举 2n 种割边方案,对于每个连通块找出重心。

复杂度 O(2n)

Subtask 2

枚举点 u 为根,用树形 dp 算出每个子树根所在连通块大小为 x 的方案数。然后枚举最大子树大小,背包处理。

复杂度 O(n3)

Subtask 4

i 成为重心当且仅当其所在区间 [l,r] 满足 il>riri>il,可以直接计算得到方案数。复杂度 O(n2)

Subtask 5

考虑先认为每个点都有贡献,然后一个个删掉贡献。

那么,一个点 u 没有贡献,当且仅当存在一个点 vuv 的边被保留了,并且考虑删完边之后 u,v 的连通块中,以 v 为根的子树中,u 的子树大小小于 v 除去 u 的大小,而且一个点最多被删掉一次贡献。

对于每个点可以 dp 出他所在的子树内,他所在的连通块恰好有 k 个点的方案数。

然后要求出每个点 v 为根,不考虑某个儿子 u 的子树时所在的连通块恰好有 k 个点的方案数,然后对于每一个 u,v 去统计一下,记录一个前缀和就可以了。

这部分是这样的:设 gx,y 表示以 fax 为根去掉 x 的子树后删边后根的连通块大小是 y 的方案。容易发现,y 可以和 sizex+1min

那么从 gfax 转移到 gx 的复杂度就是 sizex×vxsizev,容易发现,这和树形 dp 的复杂度是一样的。

时间复杂度 O(n2) 的。

G. 回文多项式

Subtask1

对于每一个询问将询问区间内部的所有多项式暴力乘起来,直接判断得到的多项式是否是回文多项式即可,时间复杂度O(q×(ki)2)

Subtask2

考虑加速 Subtask 1 的多项式乘法过程,那么通过分治 + NTT 即可在O(q×(ki)×log)的时间复杂度解决。

Subtask3

可以发现,每一个位置都是一次函数的情况下,我们可以发现只有本身就是回文多项式的一次函数和解互为倒数的一次函数相乘才会是回文多项式。我们可以考虑利用这一性质,利用集合哈希维护出这个区间的每一个一次函数的集合和每一个互为倒数的解的一次函数的集合,check 是否相同即可。

Subtask4

这个包的做法可能存在两种,一种是暴力分解每一个多项式使其变成一次函数之后用上一个包的做法来做,可能并不是特别好实现。

又或者是用出题人偶然发现的一个暴力做法实现,即暴力维护多项式相乘之后的前后若干项。经过暴力验证,是正确的,留给读者自行证明。

Subtask5

一个 n 次多项式 F 满足 [xi]F(x)=[xni]F(x) 时,我们可以发现 F(x)=xnF(1x) ,也就是说,我们实际上只需要判断 F(x)xnF(1x) 是否相同即可。

快速判断两个高次多项式是否相同,如果使用暴力的做法,是与次数相关的,复杂度不能接受。我们这里使用多项式哈希。

令哈希函数 G(F(x))=gn+1+(i=0n[xi]F(x)gi)(modp) 这个哈希函数是可以利用线段树方便维护的,我们考虑证明其正确性。

若两个相同次数的多项式 F(x),G(x) 的哈希函数相同,必然满足 i=0n([xi]F(x)[xi]G(x))gi=0(modp) 我们考虑当 F(x)G(x) 不同的时候,多项式 H(x)=i=0n([xi]F(x)[xi]G(x))xi 在模数 p 是质数的情况下最多是一个 n 次多项式,最多存在 n 个零点。若随机取 x ,则 H(x)0 的概率为 np 。说明两个多项式不相同但哈希函数相同的概率为 np

于是我们令 p 为一个 109 级别的质数,单次询问成功的概率是 1npq 次均成功的概率是 (1np)q ,约为 0.00004 ,所以单哈希不能满足我们的要求,需要双哈希,q 次均成功的概率为 (1(np)2)q ,约为 0.999

至此,该问题可以在O(qlogn)的复杂度内解决

H. 病毒实验

Subtask 1

暴力将每次询问的链取出,然后模拟即可。

时间复杂度 O(qn2)

Subtask 2

暴力将每次询问的链取出,用哈希判断每个前缀是否为回文串。

时间复杂度 O(qn)

Subtask 3

这个部分分主要给各种根号做法以及常数较大的做法。

一种根号做法是使用树上莫队,然后使用双向 PAM 实现。复杂度 O(nq|Σ|),这里 |Σ| 表示字符集大小。

Subtask 4

考虑将询问离线,按左端点位置排序。从右往左扫描的过程中使用 PAM 维护回文树的形态以及每个节点的深度。对于每次询问用树上倍增找到第一个回文前缀对应的节点,其在回文树上的深度就是答案。

时间复杂度 O(qlogn)

Subtask 5

首先对所有询问离线,然后进行点分治,对于每个点分中心处理其连通块内所有经过该点的询问。

对于询问 u,v,设 u 所在子树为 Lv 所在子树为 R,根据回文串位置分类讨论:

Case 1

红色线段是回文前缀位置,蓝色处是回文中心。

Su 表示从根到 u 路径组成的字符串。

整个回文串均在 L,等价于 Su 后缀回文子串个数。可以通过 dfs 并维护可撤销 PAM 统计,其中后缀回文子串个数就是该点在 PAM 的 fail 树上的深度。

这部分总复杂度 O(n|Σ|logn)

Case 2

回文串经过根到达了 R 子树,并且回文中心仍然留在 L 子树。

根据回文串的性质可以将这个串分成 x,s,x 三部分。其中 xSu 的前缀,xSv 的后缀。满足 s 是一个回文串,且 x=x

引理 1:ss+t 都是回文串,那么 s+t+t 一定是一个回文串。

引理 2: 一个字符串的所有回文前缀可以划分为 O(logn) 个等差数列。

我们利用 引理 2Su 进行回文前缀分解。对于每个等差数列,表示成 s=si+aij,j[0,bi] 的形式。(si 表示将字符串 s 重复 i 遍形成的字符串,s+t 表示字符串 st 前后拼接形成的字符串。)

考虑 s=s0+aj,j[0,b] 的情况,此时 Su 被划分成 s0+aj+y,我们不妨将 Sv 也分解为 ak+y+z 形式,其中 |y|=|y|

x 一定可以被表示成 ai+y,ib 的形式。根据 引理 1a 一定不是 yy 的前缀。此时若:

对于回文分解,可以用 Case 1 的 PAM ,对每个节点维护最深的不满足等差数列的祖先。对于计算 Sv 的分解,可以维护 a2i 的哈希值,然后倍增计算。

这部分总复杂度 O(qlog2n)

Case 3

回文中心在 R 子树。类似 Case 2,我们将回文串分解为 x,s,x,此时有 x=x

同样,我们将 s 分解为 s0+ai,ib 的形式,将 Su 也分解为 y+ai 形式,并在 s 往下 |y| 取出 y

同样,对 y 是否为 a 的前缀进行分类讨论,如果不是,对唯一的 x 进行检验。否则结果是两边可行幂次的差。

这部分复杂度 O(qlog2n)

总复杂度 O(n|Σ|logn+qlog2n)