【模拟赛记录】真希望雨能下不停 雨爱的秘密 能一直延续

· · 个人记录

2026.03.23

A

Data Range: $1\le T\le 10,1\le n\le 10^5,0\le b_i\le 10^9$。

预计难度：*800 / 橙

题解：

显然只需要满足 b_1=0 且 b_i-b_{i-1}\in\lbrace 0,1\rbrace 即可。时间复杂度为 O(n)。

挂分原因

没挂

B

P3594 [POI 2015 R3] 狼坑 Trous de loup

预计难度：*2000 / 蓝

容易发现删除的区间长度为 d 一定不会更差。直接枚举删除的区间 [l,l+d-1] 看上去就很没有前途，因此考虑换一个角度处理。注意到最长符合条件的区间长度满足单调性，因此考虑二分答案，然后再枚举删除的区间 [l,r]，选择一个被完全覆盖的长度为 d 的区间删除，这个地方肯定是贪心的选和最大的，因此求个前缀和之后二维数点ST 表就可以做到整体时间复杂度 O(n\log n) 解决问题。

注意数组大小是 10^6 而不是 5e5。（赛时 n 的范围是 1e6 而不是 2e6）

挂分原因

数组开小了，写题的时候因为带一个缺省源所以直接从上一道题上复制的整份代码修改，但是忘记修改数组大小 N 了

C

题意：

给定一个 1\sim n 的排列 p，你需要计数有多少个 1\sim n 的排列 q，使得 q 是 p 的好排列。答案对 10^9+7 取模。

定义 a 是 b 的好排列，当且仅当 i=1\ldots n，若 a_i\neq n 则执行操作 swap(b_{a_i},b_{a_i+1})。若操作全都执行之后 b 排列单调递增，则 a 是 b 的好排列。

Data Range: 1\le n\le 5000。

预计难度：*2500 / 紫

考虑套路的转化可行条件。容易发现题目给出的条件等价于：一个序列 q 是合法的当且仅当删除 q 序列的 n 后得到的序列 t 从后往前操作可以把升序排列变为 p。因此答案就是 n 乘以能够得到排列 p 的序列 t 的数量。

更确切的说：记 s_i 表示当前操作交换 a_i,a_{i+1} 两个数，则对于长度为 n-1 的排列 t，操作过程可以看作是：从排列 1,2,3,\ldots,n 开始按顺序执行操作 s_{t_1},s_{t_2},\ldots,s_{t_n-1} 并最终得到 p 排列。最后答案额外乘以 n。

注意到若 |i-j|>1，则 s_i 和 s_j 两个操作调换顺序不会影响最后得到的排列。考虑记 d_i：若 d_i=1 则表示 i 在 t 中出现在 i+1 的前面，否则（d_i=0）表示 i 在 t 中出现在 i+1 的后面。此时考虑把 1,2,3,\ldots,n-1 看作是图上的若干结点，则若 d_i=1 则连一条 i\to i+1 的边，否则连一条 i+1\to i 的边。则此时 t 正好是这张有向图的一个拓扑序。

记 S_1,S_2 两个集合为：S_1=\lbrace i+1\mid d_i=1\rbrace,S_2=\lbrace i+1\mid d_i=0\rbrace。则最终得到的置换 p 一定存在一个循环分解形如 1,S_1,n,S_2 的形式，且 S_1 一定是升序排列的，S_2 一定是降序排列的。

此时套路的记 \pi 为 t 的逆排列，则 d 的限制条件形如：

问题变为计数有多少个长度为 n-1 的排列满足上述 d 对 \pi 的限制。因此考虑套路的 dp：设 f_{i,j} 表示当前处理了排列的前 i 个元素，满足 d 的前 i-1 个限制，且最后一个数是这 i 个数里第 j 小的元素。则转移枚举下一个数的排名可以做到 O(n^3)。注意到转移的是一段连续的区间因此使用前缀和维护，时间复杂度优化到 O(n^2) 可以通过该题。

D

题意：

有一个 n 个结点的树，i 点的点权是 a_i。

Data Range: $1\le n,Q\le 10^5

预计难度：无法评定 / 紫

题解：用重剖查询 u\sim v 路径上 0,1 的数量，记 0 的数量为 c_0，1 的数量为 c_1，则若 c_0,c_1 都是奇数则无法构造回文串，否则特判 c_0=0,c_0=1,c_1=0 的情况，然后分类讨论 c_0\bmod 2 的值分类讨论即可。写起来代码是一坨。

挂分原因

使用了倍增来维护重剖（？，并在代码中出现了小 typo 把 tag 的默认值 -1 写成了 1

2026.03.25

A

预计难度：*2100 / 蓝

Tag：概率期望，Exchange-Argument

题意

有 n 个二元组，每个二元组有参数 (p_i,l_i)。你需要求出对于所有二元组的 n! 种排列顺序，其魅力值最大是多少。

定义 (p_1,l_1),(p_2,l_2),\ldots,(p_n,l_n) 的魅力值为：

Data Range: 1\le n\le 2\times 10^5。

题解

出题人样例只给 n=2，素质低下。

考虑直接 Exchange-Argument，对于两个二元组 (p_i,l_i)，(p_j,l_j)，计算其先执行 i 后执行 j 和先执行 j 后执行 i 两类情况对答案的影响，做差解不等式就可以得到排序条件。总时间复杂度为 O(n\log n)，没什么好说的。

挂分原因

挂成 40 了，原因是拆括号拆错了（但是因为赛时还拼了一个爬山所以小数据拍不出来问题 :(

B

预计难度：*3000 / 黑（难度全在代码实现和细节处理上，鉴定为大份）

Tag：数据结构，点分治，分类讨论

题意

有一个 n 个点的树，你还有 m 个二元组，第 i 个二元组是 (x_i,y_i)。现在你需要找出 1\le i\le j\le m 使得 D(x_i,x_j)+D(y_i,y_j) 的值最大，其中 D(i,j) 表示在树上 i 点到 j 点的唯一简单路径上边的数量。

Data Range: 1\le n,m\le 5\times 10^5。

题解

后面为了方便，记 d(i,j)=D(x_i,x_j)+D(y_i,y_j)。

考虑分别对 x,y 两个维度做点分治。先考虑 x 维度：设当前点分治处理的重心是 c，则若 x_i,x_j 删除 c 后属于不同的树或 x_i,x_j 中有一个值为 c，那么 x_i\to x_j 的唯一简单路径一定经过点 c。因此有 D(x_i,x_j)=D(x_i,c)+D(x_j,c)，即 d(i,j)=D(x_i,c)+D(y_j,c)+D(y_i,y_j)。此时考虑记 w_j=D(x_j,c) 那么对当前的 i 二元组只需要求出 \max\limits_j(w_j+D(y_i,y_j)) 的最大值加上 D(x_i,c) 即可。

此时问题被转化为：有 m 个点 y_i 带权 w_i，支持插入一个点 (y_i,w_i) 和查询一个点 y_i 的 \max\limits_j(w_j+D(y_i,y_j)) 两个操作。此时考虑再对 y 维度做一次点分治，此时把 y 按照其在 x 维度上删掉点 c 后属于的子树分类处理，然后大力分类讨论即可。总时间复杂度为 O(n\log^2n)，细节有一车，写起来非常赤石。

扩展

可以把二元组扩展成 k 元组，这样可以做 k 轮点分治，时间复杂度为 O(n\log^kn)。当然没人想写这个。

挂分原因

挂成 80 分了，原因暂时未知，应该是哪个地方边界或者细节出了点小问题

C

预计难度：*1800 / 绿

Tag：容斥原理，分类讨论

题意

+ $a\in[l_1,r_1]

Data Range: 1\le Q\le 10^6,1\le l_i,r_i\le 10^9(i=1\ldots 4)。

题解

根本不是题。。。。。。。

容易想到容斥计算答案，简单计算一下就可以发现答案可以被表示为：不考虑任何条件的方案数 - 钦定 a=b 的方案数 - 钦定 b=c 的方案数 - 钦定 c=d 的方案数 - 钦定 d=a 的方案数 + 钦定 a=b=c 的方案数 + 钦定 a=b=d 的方案数 + 钦定 a=c=d 的方案数 + 钦定 b=c=d 的方案数 + 钦定 a=b,c=d 的方案数 + 钦定 a=d,b=c 的方案数 - 三倍钦定 a=b=c=d 的方案数。

直接把上面所有情况都分类讨论出来即可，写的时候为了方便可以封装一个求线段交集的函数。

挂分原因

没挂

D

预计难度：*2700 / 紫

Tag：差分，并查集，扫描线，分类讨论

题意

给定一个长度为 n 的序列 s，求

\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)

对 998244353 取模后的结果。

题解

这套题里最好的一道题（？

直接对着这个式子做看着就很没有前途，因此考虑先做一个经典转化，记 f(v) 为所有同时满足 1\le a\le b<c\le d\le n,\max\limits_{i=a}^bs_i\le v,\max\limits_{i=c}^ds_i\le v 的不同四元组 (a,b,c,d) 的数量，则答案显然可以表示为 \sum\limits_ii(f(i)-f(las))，其中 las 是比 i 小的最大的不同值。

然后题目一下子就变得简单了。从小到大扫描所有值 i，则 [a,b],[c,d] 两个区间必须都落在 s_i\le v 的部分中。用并查集维护所有这样的连续区间，记这些区间长度分别为 L_1,L_2,\ldots,L_k（这个可以用并查集+扫描线简单维护），则此时分类讨论 [a,b] 和 [c,d] 在同一个连续区间内 / 不在同一个连续区间内两类情况讨论。

记 g_1(x) 表示长度为 x 的连续段中放了一个区间的方案数，g_2(x) 表示长度为 x 的连续段内放了两个区间的方案数，则显然有：

g_1(x)=\frac{x(x-1)}2\\ g_2(x)=\frac{x(x-1)(x+1)(x+2)}{24}

答案也是好统计的，显然有：f(v)=\sum\limits_{i=1}^kg_2(L_i)+\sum\limits_{i=1}^k\sum\limits_{j=i+1}^kg_2(L_i)g_2(L_j)。此时再记 s_1=\sum g_1(L_i),s_2=\sum g_1(L_i)^2,s_g=\sum g_2(L_i)，则可以用 s_1,s_2,s_g 来表示 f(v) 的值：f(v)=s_g+\frac12(s_1^2-s_2)，在并查集维护区间连续段的时候顺带统计 s_1,s_2,s_g 的值即可。

挂分原因

挂成 90 分了，原因未知