（模拟赛记录）
同步在洛谷更新
2026.03.23
A
> TTT 组数据，每组数据给 nnn 个数 a1,a2,…,ana_1,a_2,\ldots,a_na1 ,a2 ,…,an ，每个数的值要么是 000 要么是 111。现在对每个 i=1…ni=1\ldots ni=1…n 告诉你 bi=∑j=1i−1ajb_i=\sum\limits_{j=1}^{i-1}a_jbi =j=1∑i−1 aj 的值，问是否存在这样的 aaa 序列。
>
> Data Range: 1≤T≤10,1≤n≤105,0≤bi≤1091\le T\le 10,1\le n\le 10^5,0\le b_i\le 10^91≤T≤10,1≤n≤105,0≤bi ≤109。
预计难度：*800 / 橙
题解：
显然只需要满足 b1=0b_1=0b1 =0 且 bi−bi−1∈{0,1}b_i-b_{i-1}\in\lbrace 0,1\rbracebi −bi−1 ∈{0,1} 即可。时间复杂度为 O(n)O(n)O(n)。
B
P3594 [POI 2015 R3] 狼坑 Trous de loup
预计难度：*2000 / 蓝
容易发现删除的区间长度为 ddd 一定不会更差。直接枚举删除的区间 [l,l+d−1][l,l+d-1][l,l+d−1] 看上去就很没有前途，因此考虑换一个角度处理。注意到最长符合条件的区间长度满足单调性，因此考虑二分答案，然后再枚举删除的区间 [l,r][l,r][l,r]，选择一个被完全覆盖的长度为 ddd 的区间删除，这个地方肯定是贪心的选和最大的，因此求个前缀和之后二维数点ST 表就可以做到整体时间复杂度 O(nlogn)O(n\log n)O(nlogn) 解决问题。
注意数组大小是 10610^6106 而不是 5e55e55e5。（赛时 nnn 的范围是 1e6 而不是 2e6）
C
题意：
> 给定一个 1∼n1\sim n1∼n 的排列 ppp，你需要计数有多少个 1∼n1\sim n1∼n 的排列 qqq，使得 qqq 是 ppp 的好排列。答案对 109+710^9+7109+7 取模。
>
> 定义 aaa 是 bbb 的好排列，当且仅当 i=1…ni=1\ldots ni=1…n，若 ai≠na_i\neq nai =n 则执行操作 swap(bai,bai+1)swap(b_{a_i},b_{a_i+1})swap(bai ,bai +1 )。若操作全都执行之后 bbb 排列单调递增，则 aaa 是 bbb 的好排列。
>
> Data Range: 1≤n≤50001\le n\le 50001≤n≤5000。
预计难度：*2500 / 紫
考虑套路的转化可行条件。容易发现题目给出的条件等价于：一个序列 qqq 是合法的当且仅当删除 qqq 序列的 nnn 后得到的序列 ttt 从后往前操作可以把升序排列变为 ppp。因此答案就是 nnn 乘以能够得到排列 ppp 的序列 ttt 的数量。
更确切的说：记 sis_isi 表示当前操作交换 ai,ai+1a_i,a_{i+1}ai ,ai+1 两个数，则对于长度为 n−1n-1n−1 的排列 ttt，操作过程可以看作是：从排列 1,2,3,…,n1,2,3,\ldots,n1,2,3,…,n 开始按顺序执行操作 st1,st2,…,stn−1s_{t_1},s_{t_2},\ldots,s_{t_n-1}st1 ,st2 ,…,stn −1 并最终得到 ppp 排列。最后答案额外乘以 nnn。
注意到若 ∣i−j∣>1|i-j|>1∣i−j∣>1，则 sis_isi 和 sjs_jsj 两个操作调换顺序不会影响最后得到的排列。考虑记 did_idi ：若 di=1d_i=1di =1 则表示 iii 在 ttt 中出现在 i+1i+1i+1 的前面，否则（di=0d_i=0di =0）表示 iii 在 ttt 中出现在 i+1i+1i+1 的后面。此时考虑把 1,2,3,…,n−11,2,3,\ldots,n-11,2,3,…,n−1 看作是图上的若干结点，则若 di=1d_i=1di =1 则连一条 i→i+1i\to i+1i→i+1 的边，否则连一条 i+1→ii+1\to
ii+1→i 的边。则此时 ttt 正好是这张有向图的一个拓扑序。
记 S1,S2S_1,S_2S1 ,S2 两个集合为：S1={i+1∣di=1},S2={i+1∣di=0}S_1=\lbrace i+1\mid d_i=1\rbrace,S_2=\lbrace i+1\mid d_i=0\rbraceS1 ={i+1∣di =1},S2 ={i+1∣di =0}。则最终得到的置换 ppp 一定存在一个循环分解形如 1,S1,n,S21,S_1,n,S_21,S1 ,n,S2 的形式，且 S1S_1S1 一定是升序排列的，S2S_2S2 一定是降序排列的。
此时套路的记 π\piπ 为 ttt 的逆排列，则 ddd 的限制条件形如：
* di=1d_i=1di =1：πi<πi+1\pi_i<\pi_{i+1}πi <πi+1
* di=0d_i=0di =0：πi>πi+1\pi_i>\pi_{i+1}πi >πi+1
问题变为计数有多少个长度为 n−1n-1n−1 的排列满足上述 ddd 对 π\piπ 的限制。因此考虑套路的 dp：设 fi,jf_{i,j}fi,j 表示当前处理了排列的前 iii 个元素，满足 ddd 的前 i−1i-1i−1 个限制，且最后一个数是这 iii 个数里第 jjj 小的元素。则转移枚举下一个数的排名可以做到 O(n3)O(n^3)O(n3)。注意到转移的是一段连续的区间因此使用前缀和维护，时间复杂度优化到 O(n2)O(n^2)O(n2) 可以通过该题。
D
题意：
> 有一个 nnn 个结点的树，iii 点的点权是 aia_iai 。
>
> QQQ 次询问，每次给定两个点 u,vu,vu,v，问 uuu 到 vvv 的唯一简单路径重排之后是否可以是回文的。若可以则输出 Meow 然后把 uuu 到 vvv 唯一简单路径上每个元素的值重排为字典序最小的 010101 回文串，否则输出 Wolf。
>
> Data Range: 1≤n,Q≤1051\le n,Q\le 10^51≤n,Q≤105
预计难度：无法评定 / 紫
题解：用重剖查询 u∼vu\sim vu∼v 路径上 0,10,10,1 的数量，记 000 的数量为 c0c_0c0 ，111 的数量为 c1c_1c1 ，则若 c0,c1c_0,c_1c0 ,c1 都是奇数则无法构造回文串，否则特判 c0=0,c0=1,c1=0c_0=0,c_0=1,c_1=0c0 =0,c0 =1,c1 =0 的情况，然后分类讨论 c0 mod 2c_0\bmod 2c0 mod2 的值分类讨论即可。写起来代码是一坨。
attention：重剖没有必要用倍增来维护（（（
2026.03.25
A
预计难度：*2100 / 蓝
Tag：概率期望，Exchange-Argument
题意
有 nnn 个二元组，每个二元组有参数 (pi,li)(p_i,l_i)(pi ,li )。你需要求出对于所有二元组的 n!n!n! 种排列顺序，其魅力值最大是多少。
定义 (p1,l1),(p2,l2),…,(pn,ln)(p_1,l_1),(p_2,l_2),\ldots,(p_n,l_n)(p1 ,l1 ),(p2 ,l2 ),…,(pn ,ln ) 的魅力值为：
* 有一个总动力值 sss，初始为 000，还有一个魅力值 mmm，初始也为 000。
* 对于 i=1…ni=1\ldots ni=1…n，有 pip_ipi 的概率让总动力值 sss 和魅力值 mmm 同时增加 lil_ili ，有 1−pi1-p_i1−pi 的概率让魅力值 mmm 增加 s−lis-l_is−li 。
Data Range: 1≤n≤2×1051\le n\le 2\times 10^51≤n≤2×105。
题解
出题人样例只给 n=2n=2n=2，素质低下。
考虑直接 Exchange-Argument，对于两个二元组 (pi,li)(p_i,l_i)(pi ,li )，(pj,lj)(p_j,l_j)(pj ,lj )，计算其先执行 iii 后执行 jjj 和先执行 jjj 后执行 iii 两类情况对答案的影响，做差解不等式就可以得到排序条件。总时间复杂度为 O(nlogn)O(n\log n)O(nlogn)，没什么好说的。
挂分原因
挂成 40 了，原因是拆括号拆错了（但是因为赛时还拼了一个爬山所以小数据拍不出来问题 :(
B
预计难度：*3000 / 黑（难度全在代码实现和细节处理上，鉴定为大份）
Tag：数据结构，点分治，分类讨论
题意
有一个 nnn 个点的树，你还有 mmm 个二元组，第 iii 个二元组是 (xi,yi)(x_i,y_i)(xi ,yi )。现在你需要找出 1≤i≤j≤m1\le i\le j\le m1≤i≤j≤m 使得 D(xi,xj)+D(yi,yj)D(x_i,x_j)+D(y_i,y_j)D(xi ,xj )+D(yi ,yj ) 的值最大，其中 D(i,j)D(i,j)D(i,j) 表示在树上 iii 点到 jjj 点的唯一简单路径上边的数量。
Data Range: 1≤n,m≤5×1051\le n,m\le 5\times 10^51≤n,m≤5×105。
题解
后面为了方便，记 d(i,j)=D(xi,xj)+D(yi,yj)d(i,j)=D(x_i,x_j)+D(y_i,y_j)d(i,j)=D(xi ,xj )+D(yi ,yj )。
考虑分别对 x,yx,yx,y 两个维度做点分治。先考虑 xxx 维度：设当前点分治处理的重心是 ccc，则若 xi,xjx_i,x_jxi ,xj 删除 ccc 后属于不同的树或 xi,xjx_i,x_jxi ,xj 中有一个值为 ccc，那么 xi→xjx_i\to x_jxi →xj 的唯一简单路径一定经过点 ccc。因此有 D(xi,xj)=D(xi,c)+D(xj,c)D(x_i,x_j)=D(x_i,c)+D(x_j,c)D(xi ,xj )=D(xi ,c)+D(xj ,c)，即
d(i,j)=D(xi,c)+D(yj,c)+D(yi,yj)d(i,j)=D(x_i,c)+D(y_j,c)+D(y_i,y_j)d(i,j)=D(xi ,c)+D(yj ,c)+D(yi ,yj )。此时考虑记 wj=D(xj,c)w_j=D(x_j,c)wj =D(xj ,c) 那么对当前的 iii 二元组只需要求出 maxj(wj+D(yi,yj))\max\limits_j(w_j+D(y_i,y_j))jmax (wj +D(yi ,yj )) 的最大值加上 D(xi,c)D(x_i,c)D(xi ,c) 即可。
此时问题被转化为：有 mmm 个点 yiy_iyi 带权 wiw_iwi ，支持插入一个点 (yi,wi)(y_i,w_i)(yi ,wi ) 和查询一个点 yiy_iyi 的 maxj(wj+D(yi,yj))\max\limits_j(w_j+D(y_i,y_j))jmax (wj +D(yi ,yj )) 两个操作。此时考虑再对 yyy 维度做一次点分治，此时把 yyy 按照其在 xxx 维度上删掉点 ccc 后属于的子树分类处理，然后大力分类讨论即可。总时间复杂度为 O(nlog2n)O(n\log^2n)O(nlog2n)，细节有一车，写起来非常赤石。
扩展
可以把二元组扩展成 kkk 元组，这样可以做 kkk 轮点分治，时间复杂度为 O(nlogkn)O(n\log^kn)O(nlogkn)。当然没人想写这个。
挂分原因
挂成 80 分了，原因暂时未知，应该是哪个地方边界或者细节出了点小问题
C
预计难度：*1800 / 绿
Tag：容斥原理，分类讨论
题意
QQQ 次询问，每次询问给定四个区间 [l1,r1],[l2,r2],[l3,r3],[l4,r4][l_1,r_1],[l_2,r_2],[l_3,r_3],[l_4,r_4][l1 ,r1 ],[l2 ,r2 ],[l3 ,r3 ],[l4 ,r4 ]，问有多少个整数四元组 (a,b,c,d)(a,b,c,d)(a,b,c,d) 同时满足：
* a∈[l1,r1]a\in[l_1,r_1]a∈[l1 ,r1 ]
* b∈[l2,r2]b\in[l_2,r_2]b∈[l2 ,r2 ]
* c∈[l3,r3]c\in[l_3,r_3]c∈[l3 ,r3 ]
* d∈[l4,r4]d\in[l_4,r_4]d∈[l4 ,r4 ]
* a≠b,b≠c,c≠d,d≠aa\neq b,b\neq c,c\neq d,d\neq aa=b,b=c,c=d,d=a
Data Range: 1≤Q≤106,1≤li,ri≤109(i=1…4)1\le Q\le 10^6,1\le l_i,r_i\le 10^9(i=1\ldots 4)1≤Q≤106,1≤li ,ri ≤109(i=1…4)。
题解
根本不是题。。。。。。。
容易想到容斥计算答案，简单计算一下就可以发现答案可以被表示为：不考虑任何条件的方案数 - 钦定 a=ba=ba=b 的方案数 - 钦定 b=cb=cb=c 的方案数 - 钦定 c=dc=dc=d 的方案数 - 钦定 d=ad=ad=a 的方案数 + 钦定 a=b=ca=b=ca=b=c 的方案数 + 钦定 a=b=da=b=da=b=d 的方案数 + 钦定 a=c=da=c=da=c=d 的方案数 + 钦定 b=c=db=c=db=c=d 的方案数 + 钦定 a=b,c=da=b,c=da=b,c=d 的方案数 + 钦定 a=d,b=ca=d,b=ca=d,b=c 的方案数 - 三倍钦定
a=b=c=da=b=c=da=b=c=d 的方案数。
直接把上面所有情况都分类讨论出来即可，写的时候为了方便可以封装一个求线段交集的函数。
挂分原因
没挂
D
预计难度：*2700 / 紫
Tag：差分，并查集，扫描线，分类讨论
题意
给定一个长度为 nnn 的序列 sss，求
∑1≤a≤b<c≤d≤nmax(maxi=absi,maxi=cdsi)\sum\limits_{1\le a\le b<c\le d\le n}\max(\max\limits_{i=a}^bs_i,\max\limits_{i=c}^ds_i) 1≤a≤b<c≤d≤n∑ max(i=amaxb si ,i=cmaxd si )
对 998244353998244353998244353 取模后的结果。
题解
这套题里最好的一道题（？
直接对着这个式子做看着就很没有前途，因此考虑先做一个经典转化，记 f(v)f(v)f(v) 为所有同时满足 1≤a≤b<c≤d≤n,maxi=absi≤v,maxi=cdsi≤v1\le a\le b<c\le d\le n,\max\limits_{i=a}^bs_i\le v,\max\limits_{i=c}^ds_i\le v1≤a≤b<c≤d≤n,i=amaxb si ≤v,i=cmaxd si ≤v 的不同四元组 (a,b,c,d)(a,b,c,d)(a,b,c,d) 的数量，则答案显然可以表示为
∑ii(f(i)−f(las))\sum\limits_ii(f(i)-f(las))i∑ i(f(i)−f(las))，其中 laslaslas 是比 iii 小的最大的不同值。
然后题目一下子就变得简单了。从小到大扫描所有值 iii，则 [a,b],[c,d][a,b],[c,d][a,b],[c,d] 两个区间必须都落在 si≤vs_i\le vsi ≤v 的部分中。用并查集维护所有这样的连续区间，记这些区间长度分别为 L1,L2,…,LkL_1,L_2,\ldots,L_kL1 ,L2 ,…,Lk （这个可以用并查集+扫描线简单维护），则此时分类讨论 [a,b][a,b][a,b] 和 [c,d][c,d][c,d] 在同一个连续区间内 / 不在同一个连续区间内两类情况讨论。
记 g1(x)g_1(x)g1 (x) 表示长度为 xxx 的连续段中放了一个区间的方案数，g2(x)g_2(x)g2 (x) 表示长度为 xxx 的连续段内放了两个区间的方案数，则显然有：
g1(x)=x(x−1)2g2(x)=x(x−1)(x+1)(x+2)24g_1(x)=\frac{x(x-1)}2\\ g_2(x)=\frac{x(x-1)(x+1)(x+2)}{24} g1 (x)=2x(x−1) g2 (x)=24x(x−1)(x+1)(x+2)
答案也是好统计的，显然有：f(v)=∑i=1kg2(Li)+∑i=1k∑j=i+1kg2(i)g2(j)f(v)=\sum\limits_{i=1}^kg_2(L_i)+\sum\limits_{i=1}^k\sum\limits_{j=i+1}^kg_2(i)g_2(j)f(v)=i=1∑k g2 (Li )+i=1∑k j=i+1∑k g2 (i)g2 (j)。此时再记 s1=∑g1(Li),s2=∑g1(Li)2,sg=∑g2(Li)s_1=\sum g_1(L_i),s_2=\sum g_1(L_i)^2,s_g=\sum g_2(L_i)s1 =∑g1 (Li ),s2 =∑g1
(Li )2,sg =∑g2 (Li )，则可以用 s1,s2,sgs_1,s_2,s_gs1 ,s2 ,sg 来表示 f(v)f(v)f(v) 的值：f(v)=sg+12(s12−s2)f(v)=s_g+\frac12(s_1^2-s_2)f(v)=sg +21 (s12 −s2 )，在并查集维护区间连续段的时候顺带统计 s1,s2,sgs_1,s_2,s_gs1 ,s2 ,sg 的值即可。
挂分原因
挂成 90 分了，原因未知
