九月模拟赛回顾
Rem_CandleFire
·
·
个人记录
前情
2024/9/10
A.奇怪的极差（原题：Choose）
题目大意
定义一个序列的极差为该序列中最大值与最小值之差。给定长度为 n 的序列 A，选定整数 L(1\le L\le n-k+1)，再选定 k 个长度均为 L 的不同区间。记这 k 个区间的极差的最小值为 X，求 X_{max}。同时求出，当 X 最大时 L 的最小值。
### B.奇怪的反转（原题：？）
咕咕咕。
### C.奇怪的染色（原题：[Coloring](https://www.luogu.com.cn/problem/P9716)）
**题目大意**
去原题看。
## 2024/9/12
梦熊原场，略了。
## 2024/9/18
### A.序列（原题：？）
**题目大意**
给定长度为 $n$ 的序列 A，定义 $f(A)=\sum_{i=1}^n[A_i=i]$，$g(A)$ 表示将 $A$ 排序后的序列。求给定序列的所有子序列 $S$ 的 $f(g(S))$ 的和。
$1\le n\le 2\times10^5,1\le A_i\le n$。
**分析与做法**
直接将 $A$ 排序之后考虑 $A_i$ 对答案的贡献。显然对于 $A_i$，有 $i-1$ 个小于等于它的数，需要在这些数中选择 $A_i-1$ 个，贡献为 $\binom{i-1}{A_i-1}$。考虑 $A$ 后面的 $[i+1,n]$，每个数选货不选，共 $2^{n-i}$ 种可能。
答案为 $\sum_{i=1}^n{\binom{i-1}{A_i-1}2^{n-i}}$。预处理一下可以做到时间复杂度 $O(n)$。
### B.叠盘子（原题：？）
**题目大意**
有 $n$ 个盘子，每个盘子尺寸为 $a_i$，从 $1\sim n$ 按顺序选择。对于每个盘子，可以不要也可以拿走，拿走需要满足以下任一条件：
- 之前没拿过
- 此盘大于之前所有盘
- 此盘小于之前所有盘
问最多能拿走多少个盘子。
**分析与做法**
一眼枚举中间盘 $a_i$，分别向后、向前求以 $a_i$ 开头的 LIS 和 LDS，两边加起来减一就是选择 $a_i$ 的答案，对 $i=1\sim n$ 取最大值即可。
树状数组维护，时间复杂度 $O(n\log n)$。
### C.点兵（原题：[Royal Questions](https://www.luogu.com.cn/problem/CF875F)）
**题目大意**
去原题看。
**分析与做法**
并查集维护基环树森林。
### D.拟赛（原题：？）
略。
## 2024/9/19
### A.困难卷积（原题：？）
**题目大意**
给定长度为 $n$ 的序列 $a,b$，求 $$\sum_{i=1}^n{\sum_{j=1}^n{\lfloor\sqrt{|a_i-b_j|}\rfloor}}$$。
$1\le n\le 10^6,0\le a_i,b_i \le3\times10^6,\sum a_i,\sum b_i\le10^7$。
**分析与做法**
诈骗题，注意数据范围。离散化之后直接模拟即可。
### B.点集直径（原题：？）
**题目大意**
定义两个点的距离为欧几里得距离，点集 $S$ 的直径为最大的两点距离。给定点集 $S_1$，要求对其中的每个点 $(x,y)$ 改为 $(0,y)$ 或 $(x,0)$，得到点集 $S_2$，求最小化 $S_2$ 的直径。输出其平方。
$1\le n\le 10^5$，$|x_i|,|y_i|\le 10^8$。
**分析与做法**
枚举 $|x|$ 的最大值，然后二分答案。时间复杂度 $O(n\log V)$。
### C.对称之美（原题：？）
**题目大意**
考虑杨辉三角的对称轴，其穿过奇数行最中间的数，将这些排成序列 $a$ 有 $a_0=1,a_1=2,a_2=6,\dots$。给定质数 $p$ 和正整数 $m\in[1,p)$，求 $\sum_{i=0}^{p-1}{a_i\times m^i}\pmod{p}$。
共 $T$ 组测试数据。$1\le m<p\le 10^{14}$，$1\le T\le 10^4$。
**分析与做法**
发现 $a_n=\binom{2n}{n}$。变形：
$$\binom{2n}{n}=\frac{2n!}{n!\times n!}=\frac{2^nn!\prod_{i=1}^n{(2i-1)}}{n!\times n!}=2^n\frac{\prod_{i=1}^n(2i-1)}{n!}$$
当 $p=2$ 时有 $a_0=1$，其余 $a_n$ 中 $2$ 的个数有 $\sum_{k=1}\lfloor \frac{n}{2^k} \rfloor<n$，所以 $a_n\bmod p=0$。
其它情况下，对上式继续变形：
$$2^n\frac{\prod_{i=1}^n(2i-1)}{n!}\equiv(-2)^n\frac{\prod_{i=1}^{n}(-2i+1+p)}{n!}\equiv(-4)^n\frac{\prod_{i=0}^{n-1}{(\frac{p-1}{2}-i)}}{n!}\equiv(-4)^n\binom{\frac{p-1}{2}}{n}\pmod p$$
代入题目原式：$ans=\sum_{i=0}^{p-1}(-4m)^i\binom{\frac{p-1}{2}}{i}\bmod p$。
注意到此式符合二项式定理的形式，于是令 $n=\frac{p-1}{2},a=1,b=-4m$，那么答案为 $(a+b)^n=(1-4m)^{\frac{p-1}{2}}\bmod p$。
直接算会爆，考虑将乘法改为龟速乘，再用快速幂计算即可。时间复杂度 $O(T\log^2p)$。
### D.王道征途（原题：？）
**题目大意**
共 $m$ 部落，$n$ 个位置。有 $q$ 次事件，每次事件形如：
- `1 l r x`：$[l,r]$ 被 $x$ 占领。
- `2 l r x`：$[l,r]$ 出现了价值为 $x$ 的宝物。
若出现宝物时该位置被占领，则宝物被占领者获得，否则消失。求 $q$ 次事件后每个部落获得的总价值。
$1\le n,m,q\le 5\times10^5$。
**分析与做法**
时光倒流，那么我们发现问题变成了线段树裸题，直接做就行了。时间复杂度 $O(q\log n)$。
## 2024/9/27
### A.棋局（原题：？）
**题目大意**
A 和 B 在玩游戏，最初 A 的等级为 $R_m$，B 的等级为 $R_h$，每局游戏胜者等级加一，败者等级不变。设两个人某局游戏的等级为 $x,y$，则 A 赢下此局的概率为 $\frac{x}{x+y}$，B 赢下此局的概率为 $\frac{y}{x+y}$。
进行 $P+Q$ 局游戏，求 A 恰好获胜 $P$ 局且 B 恰好获胜 $Q$ 局的概率。
**分析与做法**
诈骗题，答案为：
$$ \binom{P+Q}{P} \frac{(R_m+R_h-1)!\;(R_m+P-1)!\;(R_h+Q-1)!}{(R_m+R_h+P+Q-1)!\;(R_m-1)!\;(R_h-1)!}$$
### B.庆典（原题：？）
**题目大意**
$n$ 个节点的树，边有边权和方向，每个节点上有一位游客，通过一条边需要边权的时间。将一条边翻转需要 $1$ 的代价。选择一个节点使所有游客都能在 $D$ 的时间内到达节点，并花费代价最少。
$1\le n\le 2\times10^5$。
**分析与做法**
换根 DP 秒了。注意要记录的是时间的最大值，通过记录最大值和次大值来实现第二个深搜的转移。
### C.游戏（原题：？）
**题目大意**
长度为 $n$ 的序列 $a$，共有 $q$ 次操作，每次操作给定一个区间 $[l,r]$，在其中选择 $k$ 个数，得分是这些数的 $\gcd$。
对于每个操作，求最大得分。$1\le n,q\le 10^5$，$\max(1,r-l-2)\le k\le r-l+1$.
**分析与做法**
咕咕咕。
### D.吃豆人（原题：[ダブルス](https://www.luogu.com.cn/problem/AT_njpc2017_f)）
**题目大意**
去原题看。
**分析与做法**
实数二分。
考虑一个人在 $x_i$ 的位置，另一个人可以到达 $[L,R]$。那么对于 $x_{i+1}$，考虑两个人谁能到，并且使 $[L,R]$ 最大。
时间复杂度 $O(n\log V)$。
## 2024/9/29
### A.序列（原题：？）
**题目大意**
对于长度为 $n$ 互不相同的序列 $A$ 和给定整数 $k$，求有多少重排 $A$ 的方式使满足：
- $\forall 1\le i<j\le n,i+j\equiv 1 \pmod 2$，有 $A_i+A_j\equiv k\pmod 2$。
答案对 $147744151$ 取余。$\sum n\le 10^6$。
**分析与做法**
考虑把 $n$ 个空位的奇数、偶数为拆开看。同时记 $b_i=A_i\bmod 2
显然，当 k=0 时所有 b_i 应该相同，答案为 n!。否则为 0。
当 k=1 时序列 b 中 1 的个数和 0 的个数差应当小于等于 1。当 n 为奇数时，答案为 \lfloor \frac{n}{2}\rfloor!\times \lceil \frac{n}{2} \rceil!。n 为偶数时答案为 (\frac{n}{2})!\times 2。
B.线段（原题：？）
题目大意
对于长度为 n 的数组 A，可以任意重排。对于满足 \gcd_{i=l}^r A_i=\min_{i=l}^r A_i 的区间 [l,r]，最大化 (r-l+1)\times\min_{i=l}^r A_i 的值。
**分析与做法**
设 $f_x$ 为最小值为 $x$ 的区间长度最大值。有转移方程 $f_x=\max\{f_{ix}\}+cnt_x$。答案为 $max\{xf_x\}$。转移时枚举倍数，时间复杂度有保证。
### C.摧毁（原题：？）
**题目大意**
对于一个 $n$ 个点 $m$ 条边的无向连通图，每条边通过时间是 $1$。给定两对点 $s_1,t_1,s_2,t_2$ 和对应的时间限制 $l_1,l_2$。求当从 $s_1$ 到 $t_1$ 时间不超过 $l_1$，从 $s_2$ 到 $t_2$ 时间不超过 $l_2$ 时，能删除最多的边数。
$n\le 3000$。
**分析与做法**
记 $D(x,y)$ 表示从 $x$ 到 $y$ 的最短路径，答案下限是 $m-(D(s_1,t_1)+D(s_2,t_2))$。
两对点的路径可能会有重复，枚举重复的路径的端点 $u,v$，则原边数 $m$ 需要减去的边数的最小值为：
$$\min\{ D(u,v)+\min(D(s_1,u)+D(v,t_1),D(s_1,v)+D(u,t_1))+\min(D(s_2,u)+D(v,t_2),D(s_2,v)+D(u,t_2)) \}$$
需要预处理出任意两点的最短路，因为边权均为 $1$，宽搜即可。时间复杂度 $O(n(n+m))$。
### D.派对（原题：？）
**题目大意**
对于 $n$ 个人，一开始两两之间关系值为 $0$。有 $m$ 个操作，每个操作是以下的一种。
- $x$ 和 $y$ 关系值增加 $1
称 x 和 y 认识当 x 和 y 的关系值大于等于 1。
**分析与做法**
按照时间顺序画一画图，考虑如何实现操作二。亦或是实现两个联通块的合并。
对于联通块 $x$ 和 $y$，如果更改普通并查集建立联系的方式，考虑新建节点链接两个联通块，则可以得到一棵重构树。操作二可以通过对以 $x$ 为根的节点的子树加一实现。离线构造子树，而后操作一搞个 `map`，操作二如果两个人在同一子树就加上他们 LCA 处的值，再加上两个人单独的部分。
时间复杂度 $O(n\log n)$，常数较大。[AC代码](https://www.luogu.com.cn/paste/m6v0sf3v)。
### E.图图（原题：？）
**题目大意**
对于长度为 $n$ 的序列 $A$ 和两个整数 $L,R$，满足 $1\le L\le R\le n$。
定义 $F^k(i)=[k\not=1]F^{k-1}(F(i))+[k=1]A_i$。
对于 $n$ 个点 $0$ 条边的有向图 $G$，对于 $1\le i\le n,L\le k\le R$，添加边 $(i,F^k(i))$，长度为 $1$。
有 $q$ 组询问，每次给出两个整数 $S,T$，求 $S$ 到 $T$ 的最短距离。
$1\le n,q\le 10^5$。
## [后续](https://www.luogu.com.cn/article/3l1b48wr)