9
赛纲介绍
本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 Alice 的简单数组 入门 T2 Alice 的数学构造 普及- T3 Alice 的交通网络 普及+/提高 T4 Alice 的分段游戏 普及+/提高 T5 Alice 的奇妙字段 普及+/提高 T6 Alice 的奇妙通信 普及+/提高
T1
题目大意
现在给你一个数组 a , 每次你可以将数组左移一格，问最终能否让这个数组，非降序。
题解
把数组视作首尾相接的环。定义“下降点”为满足
ai>a(i+1) mod na_i > a_{(i+1)\bmod n} ai >a(i+1)modn
的下标 iii。
充要条件：
存在某个左旋次数 rrr 使数组非降，当且仅当环上的下降点个数 ≤1\le 1≤1。
* 若下降点个数 cnt = 0：原数组已非降，最小 r=0r=0r=0。
* 若 cnt > 1：无论从哪切开，总会把至少一个下降点放到中间位置，无法整体非降，答案 −1-1−1。
* 若 cnt = 1：设唯一下降点在 (i)（即 ai>ai+1a_i>a_{i+1}ai >ai+1 ）。则左旋 (r=i+1) 次（把 ai+1a_{i+1}ai+1 放到开头）后序列必为非降；且这是最小的可行旋转次数。
参考代码
T2
题目大意
给定 TTT 组询问，每组给一个正整数 nnn。设 aaa 是 {1,2,…,n}\{1,2,\dots,n\}{1,2,…,n} 的某个排列，定义前缀乘积序列
b1≡a1(modn),bi≡bi−1⋅ai(modn) (2≤i≤n).b_1 \equiv a_1 \pmod n,\qquad b_i \equiv b_{i-1}\cdot a_i \pmod n\ \ (2\le i\le n). b1 ≡a1 (modn),bi ≡bi−1 ⋅ai (modn) (2≤i≤n).
若序列 bbb 恰好是 {0,1,…,n−1}\{0,1,\dots,n-1\}{0,1,…,n−1} 的一个排列（每个余数出现且只出现一次），则称该排列 aaa 可行。要求对每个 nnn 判断是否存在可行排列。
判定结论： 当且仅当 n∈1,2,4n\in{1,2,4}n∈1,2,4 或 nnn 为素数时，答案为 YES，否则为 NO。
题解
必要性
令排列为 a=(a1,…,an)\boldsymbol{a} = (a_1,\dots,a_n)a=(a1 ,…,an )，前缀积为
b1≡a1(modn),bi≡bi−1×ai(modn) (2≤i≤n).b_1\equiv a_1 \pmod{n},\qquad b_i\equiv b_{i-1} \times a_i \pmod{n}\ \ (2\le i\le n). b1 ≡a1 (modn),bi ≡bi−1 ×ai (modn) (2≤i≤n).
1. nnn 必须在末位：若某个 ak=na_k=nak =n 出现在 k<nk<nk<n，则 bk≡0b_k\equiv 0bk ≡0，而此后 bk+1,…,bnb_{k+1},\dots,b_nbk+1 ,…,bn 也都 ≡0\equiv 0≡0，无法成为 0,1,…,n−1{0,1,\dots,n-1}0,1,…,n−1 的排列。因此必须 an=na_n=nan =n，且恰有 bn≡0b_n\equiv 0bn ≡0。
2. (n−1)!≢0(modn)(n-1)!\not\equiv 0\pmod{n}(n−1)!≡0(modn) 必须成立：由于前 n−1n-1n−1 个元素正好是 1,…,n−1{1,\dots,n-1}1,…,n−1 的某个排列，
bn−1≡∏i=1n−1ai≡(n−1)!(modn).b_{n-1}\equiv \prod_{i=1}^{n-1} a_i \equiv (n-1)!\pmod{n}. bn−1 ≡i=1∏n−1 ai ≡(n−1)!(modn).
为避免 bn−1=0b_{n-1}=0bn−1 =0 与 bn=0b_n=0bn =0 重复，必须 (n−1)!≢0(modn)(n-1)!\not\equiv 0\pmod{n}(n−1)!≡0(modn)。
经典数论结论：对一切合数 nnn，都有
(n−1)!≡0(modn),(n-1)!\equiv 0\pmod{n}, (n−1)!≡0(modn),
仅有 n=4n=4n=4 例外（3!≡6≡2(mod4)3!\equiv 6\equiv 2\pmod{4}3!≡6≡2(mod4)）。而 nnn 为素数时由威尔逊定理 (n−1)!≡−1(modn)≠0(n-1)!\equiv -1\pmod{n}\ne 0(n−1)!≡−1(modn)=0。再合并平凡情形 n=1,2n=1,2n=1,2，得必然条件：n∈1,2,4n\in{1,2,4}n∈1,2,4 或 nnn 为素数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
充分性（构造）
* n=1n=1n=1：取 a=(1)a=(1)a=(1)，b=(0)b=(0)b=(0)。
* n=2n=2n=2：取 a=(1,2)a=(1,2)a=(1,2)（或 a=(2,1)a=(2,1)a=(2,1)），b=(1,0)b=(1,0)b=(1,0) 为全体剩余。
* n=4n=4n=4：取 a=(1,3,2,4)a=(1,3,2,4)a=(1,3,2,4)，b=(1,3,2,0)b=(1,3,2,0)b=(1,3,2,0)。
* n=pn=pn=p 为素数：构造
a1=1,ai≡i⋅(i−1)−1(modp) (2≤i≤p−1),ap=p.a_1=1,\quad a_i\equiv i\cdot (i-1)^{-1}\pmod{p}\ \ (2\le i\le p-1),\quad a_p=p. a1 =1,ai ≡i⋅(i−1)−1(modp) (2≤i≤p−1),ap =p.
其中 (i−1)−1(i-1)^{-1}(i−1)−1 指模 ppp 的乘法逆元。则
bi≡∏j=1iaj≡∏j=2ijj−1≡i(modp)(1≤i≤p−1),b_i\equiv \prod_{j=1}^i a_j \equiv \prod_{j=2}^i \frac{j}{j-1} \equiv i \pmod{p}\quad(1\le i\le p-1), bi ≡j=1∏i aj ≡j=2∏i j−1j ≡i(modp)(1≤i≤p−1),
且 bp≡0b_p\equiv 0bp ≡0，于是 bbb 正好是 0,1,…,p−1{0,1,\dots,p-1}0,1,…,p−1 的排列。
参考代码
T3
题目大意
给定一棵有 nnn 个点的无根树，第 iii 个点有正整数点权 aia_iai 。要求恰好切断树上 kkk 条边，把树分成 k+1k+1k+1 个连通块。每个连通块的代价等于该块内点权和的平方，总代价
Cost=∑i=1k***i2,\mathrm{Cost}=\sum_{i=1}^{k+1} s_i^2, Cost=i=1∑k****i2 ,
其中 sis_isi 是第 iii 块的点权和。求最小可能的总代价。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解
思路
任选根 111。在每个结点 uuu 的子树内维护“已结算代价 + 携带块点和”的二元状态，自底向上合并；切边时把子树携带块的平方落地，不断开时只合并点和，最后在根把剩余携带块平方收尾。
状态
对每个结点 uuu，定义
DPu[t]={(c, s) }\mathrm{DP}_u[t]=\{ (c,\ s)\ \} DPu [t]={(c, s) }
表示在 uuu 的子树内恰好切了 ttt 条边，已结算代价为 ccc，且仍与父亲连通的携带块点权和为 sss（此块平方尚未计入 ccc）。
叶子初始：
DPu[0]=(0, au),DPu[t>0]=∅.\mathrm{DP}_u[0]={(0,\ a_u)},\qquad \mathrm{DP}_u[t>0]=\varnothing. DPu [0]=(0, au ),DPu [t>0]=∅.
合并转移
设从 DPu[i]\mathrm{DP}_u[i]DPu [i] 取 (c1,s1)(c_1,s_1)(c1 ,s1 )，从儿子 vvv 的 DPv[j]\mathrm{DP}_v[j]DPv [j] 取 (c2,s2)(c_2,s_2)(c2 ,s2 )，有两类转移：
* 不断开边 u–vu\text{--}vu–v（合并携带块，不加切边）：
(i,j) → (i+j),(c′,s′)=(c1+c2, s1+s2).(i,j)\ \to\ (i+j),\qquad (c',s')=(c_1+c_2,\ s_1+s_2). (i,j) → (i+j),(c′,s′)=(c1 +c2 , s1 +s2 ).
* 切开边 u–vu\text{--}vu–v（儿子侧携带块在此落地结算）：
(i,j) → (i+j+1),(c′,s′)=(c1+c2+s22, s1).(i,j)\ \to\ (i+j+1),\qquad (c',s')=(c_1+c_2+s_2^2,\ s_1). (i,j) → (i+j+1),(c′,s′)=(c1 +c2 +s22 , s1 ).
对所有 i,ji,ji,j（不超过 kkk）枚举并取更优。
收尾
整树处理完后，在根 rrr：
Answer=min(c,s)∈DPr[k] (c+s2).\text{Answer}=\min_{(c,s)\in \mathrm{DP}_r[k]}\ \big(c+s^2\big). Answer=(c,s)∈DPr [k]min (c+s2).
支配剪枝（控状态）
对固定的切边数 ttt，对 DPu[t]\mathrm{DP}_u[t]DPu [t] 的候选按 sss 递增排序，仅保留使
Φ(c,s)=c+s2\Phi(c,s)=c+s^2 Φ(c,s)=c+s2
严格下降的“前沿”。因为后续操作只会使携带和 sss 非减且落地代价是 s2s^2s2（凸），被支配的状态在将来不可能更优。
正确性要点
* 单次记账：携带块只在切边处落地平方一次；不断开时不计平方，避免重复。
* 完备与不重：每条父子边都在“切/不断开”二选一中被唯一处理。
* 最优子结构：合并仅依赖 ,(c,s),,(c,s),,(c,s), 的可加性与携带性质，满足 DP 要求。
* 剪枝不伤最优：若同 ttt 下有 s1≤s2s_1\le s_2s1 ≤s2 且 c1+s12≤c2+s22c_1+s_1^2\le c_2+s_2^2c1 +s12 ≤c2 +s22 ，则任意后续合并/落地操作后前者不劣于后者。
复杂度
设剪枝后每个 ttt 的候选至多为 mmm（经验上很小）。一次父子合并约为 O(k2m2)O(k^2m^2)O(k2m2)，全树
O(n⋅k2⋅m2),空间 O(n⋅k⋅m),O\big(n\cdot k^2 \cdot m^2\big),\qquad \text{空间 }O(n\cdot k\cdot m), O(n⋅k2⋅m2),空间 O(n⋅k⋅m),
对 n≤5×103, k≤30n\le 5\times 10^3,\ k\le 30n≤5×103, k≤30 可行。
边界校验
* k=0k=0k=0：答案为整树总和 SSS 的平方 S2S^2S2（根处结算）。
* k=n−1k=n-1k=n−1：每点成块，答案 ∑ai2\sum a_i^2∑ai2 。
* 点权全正，直觉与剪枝一致（块越大平方越贵，早落地有利于优化）。
参考代码
T4
一、二分阈值 XXX
答案 fff 显然单调：若阈值从 XXX 变大到 X′X'X′（X′≥XX'\ge XX′≥X），可行性不会变差。
因此二分 XXX。边界可取
L=maxiai,R=∑i=1nai,L=\max_i a_i,\qquad R=\sum_{i=1}^n a_i, L=imax ai ,R=i=1∑n ai ,
在 [L,R][L,R][L,R] 上二分，判定函数 ok(X) 判断“是否能用 ≤k\le k≤k 段满足条件”。
若数组中压根没有目标颜色（∃i, coli∈S\exists i,\ \text{col}_i\in S∃i, coli ∈S 不成立），直接输出 −1-1−1。
二、判定 OK(X)：转化与 DP
约束 1：段和 ≤X\le X≤X
令前缀和 pre[i]=∑t=1iatpre[i]=\sum_{t=1}^i a_tpre[i]=∑t=1i at ，并设
lim[i]=min,j∈[0,i−1]∣pre[i]−pre[j]≤X,.\text{lim}[i]=\min{,j\in[0,i-1]\mid pre[i]-pre[j]\le X,}. lim[i]=min,j∈[0,i−1]∣pre[i]−pre[j]≤X,.
在 ai≥0a_i\ge 0ai ≥0 时，lim[i]\text{lim}[i]lim[i] 可用双指针线性求出：对每个 iii，让 jjj 右移，使区间和 ≤X\le X≤X。
约束 2：每段必须含 SSS
用 nxt[i]nxt[i]nxt[i] 表示从位置 iii 开始向右的第一个“目标颜色”所在下标（若不存在取 n+1n+1n+1）。
那么分一段 [j+1,i][j+1,i][j+1,i] 合法 ⟺ \iff⟺ nxt[j+1] <= i。
DP 设计
设 g[i]g[i]g[i] 表示前 iii 个位置最少需要多少段（满足两项约束），g[0]=0g[0]=0g[0]=0，其余初始为无穷大。
则
g[i];=;1+min,g[j]∣lim[i]≤j≤i−1, 且 nxt[j+1]≤i,.g[i] ;=; 1+\min{,g[j]\mid \text{lim}[i]\le j\le i-1,\ \text{且}\ nxt[j+1]\le i,}. g[i];=;1+min,g[j]∣lim[i]≤j≤i−1, 且 nxt[j+1]≤i,.
单调队列优化
当 iii 从小到大推进时：
* 允许作为转移来源的 jjj 必须满足 nxt[j+1] <= i。也就是，当 iii 到达某值时，新的 jjj 会陆续“解锁”。
* 同时 j≥lim[i]j \ge \text{lim}[i]j≥lim[i]，即窗口左端还要随着 lim[i]\text{lim}[i]lim[i] 右移而弹出。
维护一个按 g[j]g[j]g[j] 非降的双端队列 QQQ 存可行的 jjj。推进步骤：
1. 把新“解锁”的 jjj 依次入队，入队前把队尾中 ggg 不优的下标弹出，保持队列内 ggg 非降；
2. 把不满足 j≥lim[i]j\ge \text{lim}[i]j≥lim[i] 的队首弹出；
3. 若队首存在，g[i]=g[Q.front()]+1g[i]=g[Q.front()]+1g[i]=g[Q.front()]+1，否则 g[i]=∞g[i]=\inftyg[i]=∞。
这样 ok(X) 即判断 g[n] <= k。
代码
T5
题目大意
有一串数 (a1,…,an)(a_1,\dots,a_n)(a1 ,…,an )。你可以最多一次把某一段连续区间里（长度不超过 LLL）的数全部取反（乘 −1-1−1）。翻完之后，再从新数组里选一个非空连续子段，让它的和尽量大。问这个最大值是多少（也可以选择不翻）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解
思路解释
想象最后你选出来的“最大子段”是一整段，中间有一小段被你翻转过。那这件事等价于：
* 左边：接一段原数组的“最好尾巴”（以某个位置结尾的最大和，负数就不取）；
* 中间：接一段被翻转的区间（长度 ≤L\le L≤L）。
注意：翻转某一段，其贡献就是把这段的和从 SSS 变成 −S-S−S，净变化是 减去 2S2S2S。所以“翻哪一段最赚”？——在你选的整段里面，找一个和尽可能小、长度 ≤L\le L≤L 的中间段去翻；
* 右边：再接一段原数组的“最好开头”（以某个位置开始的最大和，负数就不取）。
于是，我们只要把“左边最好尾巴 +++ 中间翻转 +++ 右边最好开头”的组合做到最优即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
怎么高效做
1. 先算一个保底答案：不翻转时的最大子段和（经典的最大子段和，一次扫描）。
2. 准备三样“辅助信息”
* 前缀和 P[i]P[i]P[i]（方便快速算任意一段的和）；
* pre[i]\texttt{pre}[i]pre[i]：以 iii 结尾的最大子段和（负就当 000，不取）；
* suf[i]\texttt{suf}[i]suf[i]：从 iii 开始的最大子段和（负就当 000，不取）。
pre 正向扫一遍，suf 反向扫一遍就好了。
3. 把“翻转中间段”变成滑窗问题
设中间段的右端是 rrr。那它的左端 lll 只能在区间 [,r−L+1, r,][,r-L+1,\ r,][,r−L+1, r,] 里（长度 ≤L\le L≤L）。
这时“左边最好尾巴 +++ 这段被翻后带来的收益 +++ 右边最好开头”可以写成：
选 j=l−1∈[,r−L,,r−1,] 去最大化：(pre[j]+P[j]) + (suf[r+1]−P[r]).\text{选 } j=l-1\in[,r-L,,r-1,]\ \text{去最大化：}\quad (\texttt{pre}[j]+P[j])\ +\ (\texttt{suf}[r+1]-P[r]) . 选 j=l−1∈[,r−L,,r−1,] 去最大化：(pre[j]+P[j]) + (suf[r+1]−P[r]).
对于固定的 rrr，右边括号中的 (suf[r+1]−P[r])(\texttt{suf}[r+1]-P[r])(suf[r+1]−P[r]) 是常数；
左边需要在区间 j∈[,r−L,,r−1,]j \in [,r-L,,r-1,]j∈[,r−L,,r−1,] 里取 (pre[j]+P[j])(\texttt{pre}[j] + P[j])(pre[j]+P[j]) 的最大值。
——这就是一个滑动窗口最大值：用一个单调队列维护窗口内的最大 (pre[j]+P[j])(\texttt{pre}[j]+P[j])(pre[j]+P[j]) 即可。每次 rrr 右移一步，就：
* 把窗口左端过期的 jjj 弹掉；
* 把新进入的 j=r−1j=r-1j=r−1 按值递减地入队；
* 用队头的最大值更新答案。
4. 别忘了比较“不翻”的保底答案
最终答案 =max不翻的最大子段和, 上面滑窗得到的最大值=\max{\text{不翻的最大子段和},\ \text{上面滑窗得到的最大值}}=max不翻的最大子段和, 上面滑窗得到的最大值。
如果 L=0L=0L=0（不能翻），那就直接输出最大子段和的结果。
参考代码
T6
题面简介
给定一个最初无边的 nnn 点图，按时刻 t=1…qt=1\ldots qt=1…q 发生三类事件：
1. 1 x y：在无向点对 (x,y)(x,y)(x,y) 之间新增一条通道（允许多重边，计数 +1+1+1）；
2. 2 x y：在 (x,y)(x,y)(x,y) 之间摧毁一条通道（计数 −1-1−1，保证此时计数 ≥1\ge 1≥1）；
3. 3 x y：询问此刻 xxx 与 yyy 是否连通。
把所有回答为“连通”的询问的时刻记为 t1,t2,…t_1,t_2,\dotst1 ,t2 ,…，输出
X=t1⊕t2⊕⋯ .X=t_1\oplus t_2\oplus \cdots . X=t1 ⊕t2 ⊕⋯.
若没有一次连通询问，输出 000。图允许多重边，连通按“仍存在的通道”是否能成路来判断。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解
1. 离线把“边的存在”转成时间区间
对每个无序点对 e=x,ye={x,y}e=x,y 维护当前计数 cnt[e]（初始 000）与“活跃区间起点” st[e]。从 t=1t=1t=1 到 qqq 顺序扫描事件：
* 1 x y：令 e=x,ye={x,y}e=x,y。若 cnt[e]==0，则 st[e]=t；随后 cnt[e]++。
* 2 x y：令 e=x,ye={x,y}e=x,y。先 cnt[e]--；若此时 cnt[e]==0，则产生一个活跃区间 [,st[e], t−1,][,st[e],\ t-1,][,st[e], t−1,]，表示这条边在该时间段存在。
* 计数语义的关键：我们只在计数从 0→10\to 10→1 与 1→01\to 01→0 时开/闭区间（多重边只要计数 >0>0>0，这条无向边就视为存在）。
扫描结束后，若某些边仍满足 cnt[e]>0，则补上区间 [,st[e], q,][,st[e],\ q,][,st[e], q,]。
于是，每条逻辑“边是否存在”的历史都被表示为若干时间区间。
2. 时间线段树上挂边
建一个覆盖区间 [1,q][1,q][1,q] 的线段树。把每条边的活跃区间 [L,R][L,R][L,R] 加到线段树所有与之相交的结点上（常规“区间加到节点”的做法，复杂度 O(logq)O(\log q)O(logq) 每条区间）。
这样，线段树每个结点维护的是“它所覆盖的时间段内恒为存在”的边集合。
3. 回滚并查集（DSU WITH ROLLBACK）
准备可回滚的并查集：parent[] / size[] 以及一条操作栈用于记录每次 union 的变更（谁挂到谁、被改变的 size 值等）。提供函数：
* save()：记录当前栈大小；
* rollback(S)：把栈回滚到大小为 S 的状态（逐一撤销 union 的 parent/size 改动）；
* union(x,y)：若本来就同属一集合则不入栈；若合并，按启发式把小树挂大树并把改动入栈，便于回退；
* find(x)：路径不压缩的版本（避免难以回滚），只配合按秩/按大小合并即可。
4. 深搜线段树处理查询
从根结点 DFS：
* 入结点前：记下当前栈大小 S；把该结点挂着的所有边执行 union；
* 若是叶子（对应唯一时刻 ttt）：若第 ttt 个事件是询问 3 x y，则判断 find(x)==find(y)；若连通，则做
ans := ans ⊕ t.\text{ans}\ \mathrel{:=}\ \text{ans}\ \oplus\ t. ans := ans ⊕ t.
* 递归处理左右子结点；
* 回到本结点退出前：rollback(S) 撤销本结点施加的所有合并，环境还原给兄弟分支使用。
最终输出 ans。
参考代码
有帮助，赞一个