真希望雨能下不停雨爱的秘密能一直延续

Lost

2026-03-25 22:56:27

发布于：山东

702阅读

0回复

0点赞

（模拟赛记录）

同步在洛谷更新

2026.03.23

A

$T$ 组数据，每组数据给 $n$ 个数 $a_1,a_2,\ldots,a_n$ ，每个数的值要么是 $0$ 要么是 $1$ 。现在对每个 $i=1\ldots n$ 告诉你 $b_i=\sum\limits_{j=1}^{i-1}a_j$ 的值，问是否存在这样的 $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）

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$ 的限制条件形如：

$d_i=1$ ： $\pi_i<\pi_{i+1}$
$d_i=0$ ： $\pi_i>\pi_{i+1}$

问题变为计数有多少个长度为 $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$ 。

$Q$ 次询问，每次给定两个点 $u,v$ ，问 $u$ 到 $v$ 的唯一简单路径重排之后是否可以是回文的。若可以则输出 Meow 然后把 $u$ 到 $v$ 唯一简单路径上每个元素的值重排为字典序最小的 $01$ 回文串，否则输出 Wolf。

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$ 的值分类讨论即可。写起来代码是一坨。

attention：重剖没有必要用倍增来维护（（（

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)$ 的魅力值为：

有一个总动力值 $s$ ，初始为 $0$ ，还有一个魅力值 $m$ ，初始也为 $0$ 。
对于 $i=1\ldots n$ ，有 $p_i$ 的概率让总动力值 $s$ 和魅力值 $m$ 同时增加 $l_i$ ，有 $1-p_i$ 的概率让魅力值 $m$ 增加 $s-l_i$ 。

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：容斥原理，分类讨论

题意

$Q$ 次询问，每次询问给定四个区间 $[l_1,r_1],[l_2,r_2],[l_3,r_3],[l_4,r_4]$ ，问有多少个整数四元组 $(a,b,c,d)$ 同时满足：

$a\in[l_1,r_1]$
$b\in[l_2,r_2]$
$c\in[l_3,r_3]$
$d\in[l_4,r_4]$
$a\neq b,b\neq c,c\neq d,d\neq a$

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(i)g_2(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 分了，原因未知

有帮助，赞一个

去预览

0/2000

全部评论 80

Xylophone
奇怪，怎么刚做完狼坑就有模拟赛出这个了。气笑了这题不知道怎么评的蓝往单调数据结构那边想不到 10 分钟胡出来一个 $O(n)$ 做法。POI 蓝之耻说是。

2026-03-26 来自广东
17
Xylophone
dddqpzc

2026-03-26 来自广东
15
- 186****6897（互关）
  回复
  Xylophone
  78
  
  2026-03-31 来自浙江
  7
- Xylophone
  回复
  186****6897（互关）
  何意味。回去写你的停车场。
  
  2026-03-31 来自广东
  8
༺དༀ༒∞78威风的虫∞༒ༀཌ༻
6

2026-03-26 来自浙江
14
yanghongzheng
终于知道大佬的 lg 号了（

2026-03-26 来自北京
10
yanghongzheng
qp

2026-03-26 来自北京
7
Lost
ddd

2026-03-25 来自山东
7
- 可乐
  回复
  Lost
  ddd
  
  2026-03-30 来自江西
  2
- 六二大侠
  回复
  可乐
  d
  
  2026-04-07 来自浙江
  0
- 六二大侠
  回复
  六二大侠
  d
  
  2026-04-07 来自浙江
  0
AC
1

2026-03-31 来自浙江
3
Dream有关必回
a

2026-03-30 来自浙江
3
Dream有关必回
a

2026-03-30 来自浙江
3
Dream有关必回
6

2026-03-30 来自浙江
3
136****9752
6

2026-03-30 来自新疆
3
咕咕咕
%%%

2026-03-30 来自江西
3
[堕落王子]渡鸦
d

2026-03-30 来自浙江
2
wyfdd
h

2026-03-28 来自河北
2
Cute Boy
22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222

2026-04-06 来自浙江
1
Cute Boy
顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶

2026-04-06 来自浙江
1
Cute Boy
333

2026-04-06 来自浙江
1
Cute Boy
呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃

2026-04-06 来自浙江
1
Cute Boy
eeeeeeeeeeeee

2026-04-06 来自浙江
1
Cute Boy
呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃

2026-04-06 来自浙江
1

2026.03.23

A

B

C

D

2026.03.25

A

题意

题解

挂分原因

B

题意

题解

扩展

挂分原因

C

题意

题解

挂分原因

D

题意

题解

挂分原因

全部评论 80

热门讨论