Noip后期模拟赛补题

Phrvth · 2024-11-05 10:03:52 · 个人记录

Noip后期模拟赛补题

Noip后期第一场

A

数轴上有 n 个相同的锁和 n 把相同的钥匙，开一把锁需要消耗一把钥匙。

每个锁的位置依次为 a_1,a_2,\cdots,a_n，每个钥匙的位置依次为 b_1,b_2,\cdots,b_n。

你一开始在数轴原点，可以携带钥匙，不可以携带锁，问开所有锁需要移动的最小距离。

对于 100\% 的数据，1\leq n\leq 10^5，1\leq a_i,b_i\leq 10^9，a_i<a_{i+1}，b_i<b_{i+1}。

Solution：

显然，第 i 把钥匙开第 i 把锁是最优的。并且你发现如果第 i 把钥匙在第 i 把锁的前面，即 a_i<b_i，那么明显这个锁是没用的，所以我们可以将 b_i=a_i，也就是将锁的位置提前，这样是不影响答案的，所以我们保证了 a_i\ge b_i。

接下来就简单了，考虑 dp，直接记 f_i 表示开完第 i 把锁所需要的最小代价。显然最优策略是往前走一段把钥匙全捡了，然后再往后走把所有锁开了，简单转移，然后因为是全局最小值，直接用个变量名记录一下即可。时间复杂度 \mathcal{O}(n)。

B

给定一个表达式 S，只包含 n 个变量，加法，乘法以及括号，所有变量相互独立，但输入中都用 \texttt{x} 表示。

你需要求出对于所有长度为 n 的排列 p，将 n 个变量依次赋值为 p_i 时表达式的结果之和。

由于答案可能很大，你只需要输出其对 10^9+7 取模的值。

记字符串中 \texttt{x} 的数量为 n。

对于 100\% 的数据，1\leq n\leq 5\times 10^3，1\leq |S|\leq 4n，S_i\in\{\texttt{x},\texttt{+},\texttt{*},\texttt{(},\texttt{)}\}，保证两层括号之间至少存在一个运算符。

Solution：

显然，套上一个期望的壳子可以发现，每一个 x 相乘的贡献可以独立来算，也就是分开来算 x,xx,xxx\cdots，考虑如果没有括号的话直接记录有几个这样的 x 相乘即可，如果有括号，就直接拆贡献，比如 (x+x)(x+x) 就可以变成 4xx，那如何做呢？

首先肯定要建立表达式数，如果当前符号是 +，那么就直接把左右两个子树相加，如果是乘，那么相乘，想高精度乘法那样做即可。

那如何求 a 个 x 相乘的值呢？首先肯定有 dp，记 f_{n,m} 表示取值从 1\sim n，m 个数相乘的值。有转移，f_{n,m}=f_{n-1,m} +f_{n-1,m-1}\times n。那么他的贡献就是 f_{n,a}\times (n-a)!a!。复杂度瓶颈在 dp，时间复杂度 \mathcal{O}(n^2)。

C

先搁着。

D

给定长度为 n 的序列 a_i，你需要处理 m 次操作：

给出 x,y，将 a_x 修改为 y。
给出 v，求出存在多少二元组 (l,r) 满足 1\leq l\leq r\leq n 且 v=\textrm{lcm}(a_l,a_{l+1},\cdots,a_r)。

对于 100\% 的数据，2\leq n,m\leq 10^5，op\in\{1,2\}，1\leq a_i,v,y\leq 10^9，1\leq x\leq n。

Solution：

简要题意是单点修改，查找全局区间 lcm 有多少个等于 v。

首先显然 lcm\le 10^9 不会超过 \log 个，所以直接暴力维护区间的所有 lcm 是 n\log n 的，这个可以线段树维护。

那么单点修改的时候，我们首先把 x 的贡献去掉，在把新的 x 的贡献加回来即可。那么我们怎么计算 x 的贡献呢？

这样，我们就要多维护几个值，在线段树上，维护从左边到后边的 lcm，和从右边到左边的 lcm，这样我们直接查询 [1,x] 和 [x,n] 的后缀和前缀，然后暴力合并即可。

这样的话你发现每次修改涉及到的值是左右两边的 \log 个 lcm，所以时间复杂度是 \mathcal{\log^2 n} 的。

查询的话直接用个 map 直接查就行了。可以通过此题。可以通过代码复习。

Noip第二场模拟赛

A

小诗梦到了一串密码，她将这串密码记作字符串 S。

这串密码长度为 n，且每一位都是 [1,k] 内的正整数，她规定了一种回忆方式：

小诗事先写下一个很长的字符串 T，并检验 T 每个长为 n 的子串是否等于 S。由于她忘记了所有关于 S 的信息，T 必须满足，无论 S 形态结构如何，都能在检验完所有长为 n 子串后猜出 S。

她想知道，这样的 T 长度最短是多少？由于答案过大，你只需告诉她长度对 10^9+7 取模后的结果。

数据范围：

对于所有测试点，1\leqslant n,k\leqslant 10^9。

Solutoin：

我会猜结论！首先答案的下限明显是 (n+k^n-1)-1，看看答案能不能达到这个下界。

看看样例，发现能过，然后交一发过了。

考虑证明。考虑把每一个状态都当成一个点，那么一个字符串往他后面加，就当成一条边连过去，你会发现这个图是一个度数为偶数的图，他是一个欧拉图！那么肯定存在一条欧拉回路。

B

小诗收到了来自粉丝的 n 个礼物，编号 1,2,\dots,n。

她想将这些礼物分成两组，并给予分组情况一个评分。

具体地，评分值为有序礼物编号对 (a,b) 的数量，满足 b 是 a 的倍数（即 b\bmod a=0），且 a 分到第一组，b 分到第二组。

她想知道，第一组的大小为 0,1,2,\cdots,n-1 时，评分的最大值分别是多少。

对于所有测试点，2\leqslant n\leqslant 3\times 10^5。

Solution：

考虑如果要把一个数分到第一组去，那么贡献就是 -以他作为倍数+他作为底的数量。

肯定可以 nlog n 的复杂度求出所有数的倍数个数，在 [0,n] 范围内。

然后考虑从1开始加入。

明显的，第一个肯定加 1，因为 n-1 都是他的倍数，那么在以后每个他的倍数在加入 A 的贡献就要减 1，这个如果考虑暴力修改的话，就是 logn 次单点修改，然后在加入的时候查 [1,n] 中没有被标记的数的最大值。

考虑如何维护他。可以使用线段树，支持单点修改，区间查 max 以及编号。

考虑如果有多个数权值相等，明显取最大的那个最优，因为他涉及到的编号肯定小。

修改的数量为 n/1+n/2+…n/n=nlogn，查询的复杂度为 nlogn，总时间复杂度为 O(nlogn)。

考虑如何以 logn 的复杂度求出一个数的所有约数。或者存下来，直接 d(n)logn。

然后发现你线段树学傻了，一个数加入左边的贡献是确定的，根本不用什么线段树维护呃呃呃。

C

小诗的伞上写着一串数字。

她对数字的喜好可以用序列 w_{1,2,\cdots,n} 表示，定义长为 n 的序列 a 权值为：

\prod_{i=1}^{n-2}w_{\max(a_i,a_{i+1},a_{i+2})}

伞上的数字已经因磨损而无法辨认，她想知道所有长为 n，值域 [1,n]\cap \mathbb{N} 的序列的权值和是多少。

由于答案过大，你只需告诉她答案对 10^9+7 取模后的结果。

数据范围：

对于所有测试点，3\leqslant n\leqslant 4000,0\leqslant w_i<10^9+7。

Solution：

这种东西直接考虑 dp，考虑记 f_{i,j,k} 表示填到前 i 位，以 i 为结尾的三元组他的最大值在这个三元组的 j 位置，并且值为 k，然后你考虑转移。

发现根本转移不了，因为如果最大值在这个三元组的最前面，新加入的数又比最大值小，那么这种情况我们不能知道新的最大值是什么。

所以考虑换一个状态，很厉害的状态！

记· f_{i,j,k},k\in\{0,1,2\} 表示填到第 i 个三元组，最靠右的最大值是 j，位置是 i+k，并且只确定了前 i 个元素的值。

刻画三种转移。

用填表法看，每一个转移都是一段前缀或者一段后缀，使用前缀和优化即可。很厉害！

D

不会，要学什么自动机。

Noip后期第三场模拟赛

A

给定一棵 n 个点的无根树，每次操作可以删除一个度数不超过 1 的结点，求 n 次操作将整棵树删空的方案数。两种方案不同当且仅当至少一次操作删除的结点不同。答案对 998244353 取模。

对于所有测试数据，满足 1 \le n \le 10 ^ 6，1 \le u, v \le n，u \ne v。

Solution：

考虑换根 dp。

记 f_u 表示把 u 删空的方案数。

f_{u}=\binom{siz_u-1}{siz_{v1}} \binom{siz_u-1-siz_{v1}}{siz_{v2}}\cdots \times \prod_{v} f_{v_i}

考虑将那一坨拆开。

f_{u}=\frac{(siz_u-1)!}{siz_{v1}!(siz_u-1-siz_{v1})!} \frac{(siz_u-1-siz_{v1})!}{siz_{v2}!(siz_{u}-1-siz_{v1}-siz_{v2})!} \cdots \prod_{v} f_{v_i}

删掉，所以得到：f_{u}=\frac{(siz_u-1)!}{\prod_{v} siz_{v_i}!}

这个简单换根。

B

一道大模拟。

C

一道 Kmp 自动机。

D

给定两个序列 \{a_n\}, \{b_n\}，保证 b_1 \ge b_2 \ge \dots \ge b_n。

求最大的非负整数 k，满足序列 \{a_n\} 存在一个恰好包含 k 个元素的区间，使得所有在该区间内出现过的元素的出现次数至少为 b_k。

形式化地说：求最大的非负整数 k，满足：\exists 1 \le i \le n - k + 1，使得 \forall i \le p \le i + k - 1，\sum_{j = i} ^ {i + k - 1} [a_j = a_p] \ge b_k。

对于所有测试数据，保证 1 \le n \le 10 ^ 6，0 \le a_i \le n，1 \le b_i \le n + 1，保证 b_1 \ge b_2 \ge \dots \ge b_n。

Solution：

容易发现答案并没有单调性，但肯定有某种性质，尝试寻找一下。

显然，如果一个区间不合法，那么如果 a_k 的次数 <b_{len}，那么所有区间里面有 a_k 这个元素的区间全部不合法。

所以我们可以考虑递归求解答案，如果合法则更新答案，否则递归子区间。

为了保证时间复杂度正确，需要采取启发式分裂。具体的。我们同时从左右两边开始找第一个不合法的元素，记为 p，那么考虑将小的区间的贡献减去，递归大区间。递归完大区间后，大区间的贡献已全部剪掉，再把小区间的贡献加回来即可，记小的区间长度为 S，那么每次操作的时间复杂度 \mathcal{O}(S) 的，这个同启发式合并是 \mathcal{O}(n) 的可以通过。

Noip 后期模拟赛第四场

A

我们称一个长度为 k 的序列 c 是好的，当且仅当对任意正整数 i 在 [1,k-1] 中，满足 c_{i+1}>b_i \times c_i，b 序列在下文描述。

胡子叔叔现在给你两个序列 a,b，你需要从 a 序列中找出一个最长的子序列 c，使得 c 是好的。

输出这个最长的子序列的长度即可。

对于 100\% 的数据，满足 1\le n\le 10^6，1\le a_i\le 10^{12}，1\le b_i\le 10^6。

Solution：

很容易发现这个东西很像最长上升子序列，所以写出转移方程 f_i = f_j+1(b_j\times a_{f_j}<a_i)。

这个东西直接二分优化，或者你上线段树，维护每个 f_i 表示长度为 i 的最小结尾，线段树上二分即可。时间复杂度 \mathcal{O}(n\log n)。

B

青蛙和胡子叔叔打算合作送快递！

街道可以抽象成一条数轴，一开始青蛙和胡子叔叔都在原点。一共有 n 个时刻的快递任务，只有完成了前一个送快递任务才可以去完成下一个。

第 i 个时刻，青蛙和胡子叔叔中的一个人要将快递送往位置 k_i，送完快递后，那个人将停留在位置 k_i。

请问如何分配二人送快递的任务才能使得两人送快递走过的总路程之和最小？

对于所有测试点，满足 1 ≤ n ≤ 10^6, 1 ≤ k_i ≤ 10^9。

Solution：

dp 题，首先很容易想到一个人肯定是送一段区间，然后另外一个人再送一段区间这种形式。

于是你定义了 f_i 表示一个人送以 i 结尾的段，但是这样似乎不行，然后你就定义 f_{i} 表示以 i 作为一段开头，然后写出转移方程，但是绝对值不好处理。然后有个经典套路就是把绝对值拆掉，然后开个权值线段树，在 a_i 的位置存 f_i+...，然后直接查两边即可。

时间复杂度 \mathcal{O}(n\log n)。

C

胡子叔叔给了你一张边带权无向图，共包含 n 个点和 a+b 条边，其中有 a 条边是蓝边，还有 b 条边是红边。

你需要选择两个非负整数，使得只保留边权 \le x 的蓝边和边权 \le y 的红边时，同色连通的点对至少有 k 对。求 x+y 的最小值，或报告无解。

我们定义一对点 (u,v) 是同色连通的，当且仅当存在一条从 u 到 v 的路径，满足路径上所有边颜色相同。这里点对是无序的，即 (u,v) 和 (v,u) 算是同一个点对，并且 (u,u) 不算在同色连通点对之内。

对于 100\% 的数据，满足 1\le n\le 2\times 10^5，0\le a,b\le 2\times 10^5，0\le k\le \frac {n(n-1)}2，1\le u,v\le n，1\le w\le 10^9。

Solution：

首先可以双指针，因为你发现 x 增加的时候，y 不可能增加，所以你可以双指针。

你发现有用的边只有可能在这棵树的最小生成树上，因为最小生成树是最小瓶颈生成树，最大值最小，所以只需要考虑最小生成树上的点。

然后考虑容斥一下，变成红边联通+蓝边联通-红蓝边都联通。

你考虑到红色边只有可能加点，蓝色边只有可能删点，然后考虑红色点做启发式合并，蓝色点做启发式分裂，两个都联通的开个 map 存一下，然后直接计算贡献即可。

这题特别困难。。

D

胡子叔叔给你一个长为 n 的序列 a。

定义一个合法二元组 (i,j) 需要满足 i,j 为整数，且 i\le j。如果 i>j，则 (i,j) 不构成合法二元组。

定义一个合法二元组 (i,j) 的分数为 a_i-a_j。

定义一个合法二元组 (i,j) 在区间 [l,r] 内，当且仅当 l\le i,j\le r。

有 m 次操作：

1 l r x：表示将序列中第 l 个位置到第 r 个位置都加上 x。

2 l r k：表示询问选出 k 个不同的合法二元组，每个合法二元组都在区间 [l,r] 内，这些合法二元组的分数和最高是多少。

即选出一些合法二元组 (i_1,j_1)，(i_2,j_2)，\cdots，(i_k,j_k)，满足这些选出的合法二元组两两不同，且分数和尽可能大。

两个合法二元组 (i_1,j_1) 与 (i_2,j_2) 不同，当且仅当 i_1\neq i_2 或 j_1\neq j_2。

换句话说，两个合法二元组 (i_1,j_1) 与 (i_2,j_2) 相同，等价于 i_1=i_2 且 j_1=j_2。

对于 100\% 的数据，满足 1\le n,m\le 10^5，1\le l\le r\le n，所有询问的 k 的和不超过 3\times 10^5，-10^6\le a_i,x\le 10^6。

Solution：

首先求区间内前 k 大二元组可以使用超级钢琴的套路，即求最大值，删最大值，再求最大值……。

考虑放到此题怎么考虑？首先求 [l,r] 的最大值怎么做？显然可以线段树简单合并。即左儿子的答案和右儿子的答案和左儿子的最大值减去右儿子的最小值。

然后我们要将 (x,y) 去掉怎么做？显然一个区间内 [l,r] 去掉 (x,y) 可以拆成 5 个有可能作为答案的区间，有些区间不相交，有些区间相交，把他全部推进堆里面算答案。那如果两个不相交的区间要去掉 (x,y) 那就明显可以拆成 4 个有可能作为答案的区间。注意细节即可。

Noip后期模拟赛第五场

A

沃若决定给扶苏一点小小的蠕虫病毒震撼！

具体来说，沃若手里有 n 种蠕虫病毒，而扶苏的电脑中有 m 张硬盘。第 i 种蠕虫病毒可以让扶苏电脑中的第 l_i 到第 r_i 张硬盘均被攻击 k_i 次。

现在，沃若将所有 n 种病毒都通过粉兔网络传输到了扶苏的电脑中，即将发动攻击。就在这时，扶苏告诉沃若自己的电脑中存放着许多洛谷机密。为了大局着想，沃若决定放下私人恩怨，保护洛谷谷民。

但是病毒已经发出，即便是沃若也不能完全撤回攻击了。沃若只能选择恰好 1 种蠕虫病毒让其失效自毁，而其余的蠕虫病毒仍然会攻击指定的硬盘。

对于每种蠕虫病毒，沃若想知道如果让其失效自毁，所有硬盘被攻击的最大次数。

对于 100 \% 的测试数据，保证 1 \leq n, m \leq 10^6，1 \leq l_i \leq r_i \leq m，1 \leq k_i \leq 1,000。

Solution：

直接上线段树区间修改区间 max 即可。

B

须弥洛谷中有一棵巨大的树，称为~~世界树~~扶桑。它的形态可以用一张有 n 个点和 n - 1 条边的无向连通图表示，点的编号为 1 到 n。

现在，大家要举办一场定向越野比赛。在设计路线时，扶苏会依次选择三个点 x, y, z (1 \leq x, y, z \leq n)，x 为起点，y 为检查站，z 为终点。选手需要沿着 x \rightarrow y \rightarrow z 的简单路径完成比赛。

但沃若很快就发现这样是不可行的，因为一条合理的路线必须满足 x \neq y, x \neq z, y \neq z，且同一条边最多只会被路线覆盖一次。

请计算扶苏所有可能设计的路线中，不合理路线的数量。

对于 100 \% 的测试数据，保证 2 \leq n \leq 10^6，1 \leq u_i, v_i \leq n。

Solution：

考虑容斥，即全部的数量减去合法的数量。

合法的数量怎么算？直接考虑将根节点设为 x，然后树形 dp 即可。最后换个根即可。

C

又到了疯狂星期四！沃若和扶苏来到了肯德基，买了许多蛋挞。

沃若觉得简单地吃太没意思了，拉着扶苏来玩一个吃蛋挞游戏：

他们都有一个得分序列，初始为空
第 1 轮吃的人会吃掉 1 个蛋挞，随后每轮吃的人都要比上轮多吃 1 个蛋挞
双方可以随时抢吃，但只有一个人吃完了本轮才能进行下一轮，同一个人可以连续多轮抢吃
每当一个人吃完了本轮的蛋挞，就将本轮吃的蛋挞数量加入自己的得分序列末尾
游戏可以在任何一轮吃完后结束，但至少进行 1 轮

例如，一种可能的最终得分序列是：

沃若：[1, 3, 4]
扶苏：[2, 5]

在这个例子中，沃若抢吃了第 1 轮，随后扶苏抢吃了第 2 轮，第 3, 4 轮均被沃若抢得，最终扶苏又抢吃第 5 轮。

已知沃若和扶苏分别可以吃下不超过 n, m 个蛋挞，请问最终可能的得分序列有多少种情况。两种情况视为不同，当且仅当沃若的得分序列不同或扶苏的得分序列不同。

由于答案可能很大，你只需要输出答案对 10^9 + 7 取模后的值。

对于 100 \% 的测试数据，保证 1 \leq T \leq 10,000，1 \leq n, m \leq 50,000。

Solution：

显然轮数是 \sqrt{n} 级别的，考虑把他写入状态，即记 f_{i,j} 表示考虑到了第 i 轮，A 吃了 j 个的方案数，直接转移即可。

最后前缀和一下，枚举每一轮算答案即可。

D

给定一个长度为 n 的数列 a。

有 m 次询问，每次给出 x 和 y。你要把数列划分成非空的两段（一个非空前缀和一个非空后缀），使得『x 在前缀中出现的次数 \times y 在后缀中出现的次数』最大。

形式化地，定义：

对于一组询问，你要找到一个 p \in [2, n]，最大化 A(p - 1, x) \times B(p, y)。

另有 20\% 的数据，数列中每个数字的出现次数不超过 100。
另有 20\% 的数据，数列中的不同数字数量不超过 100。
对 100\% 的数据，2 \leq n \leq 10^5，1 \leq m \leq 10^5，1 \leq a_i, x, y \leq 10^9。

Solution：

部分分提示明显。

设 B=100。考虑第一个部分分，即每个数字的出现次数不超过 B。

你发现每两个相同数字之间的 A(p,x) 是不变的，所以可以直接枚举每一个 x，然后二分出后面有多少个 y 即可。

考虑第二个部分分，即数列中不同数字数量不超过 B，那么我们枚举每一个块，做个前缀和，然后从后往前扫，开个桶，对于每个 a_j \ne a_i，答案为 pre_{i-1} \times Cnt_{a_{j}}，其中 Cnt 是桶。对于每两个块都预处理出答案即可。

最后考虑正解，明显根号分支即可，取 B=\sqrt{N}。

Noip后期模拟赛第六场

A

有一个 H\times W 的网格，左上角的格子坐标为 (1,1)，右下角的格子坐标为 (H,W)。

网格上有 n 枚棋子，第 i 枚棋子的坐标为 (x_i,y_i)。

你可以无限次（包括 0 次）任意进行以下操作：

将所有棋子向上移动一格。

如果某棋子原来在 (x,y)，则其被移到 (x-1,y)。特别地，若原来在 (1,y)，则其被移到 (H,y)。
将所有棋子向下移动一格。

如果某棋子原来在 (x,y)，则其被移到 (x+1,y)。特别地，若原来在 (H,y)，则其被移到 (1,y)。
将所有棋子向左移动一格。

如果某棋子原来在 (x,y)，则其被移到 (x,y-1)。特别地，若原来在 (x,1)，则其被移到 (x,W)。
将所有棋子向右移动一格。

如果某棋子原来在 (x,y)，则其被移到 (x,y+1)。特别地，若原来在 (x,W)，则其被移到 (x,1)。

定义所有棋子的最小包围矩形是满足以下条件的矩形：

所有边都平行于网格边缘
面积最小
所有棋子都在矩形内部

你的目标是：在任意多次操作后，让最小包围矩形的面积最小。在此基础上，让操作次数尽可能小。

本题共 20 个测试点，每个测试点 5 分。所有数据均满足：1\le H,W\le 10^9,1\le n\le 10^5。

Solution：

傻逼题，乱搞即可。

B

我们说一个 01 串是好的，当且仅当其能被写为 (0^k)1(0^k)1\dots 1(0^k) 的形式，k 是非负整数，且中间至少有一个 1。换句话说，其形如：“k 个 0，一个 1”不停重复，最后以 k 个 0 结尾，且至少有一个 1。

给定一个 01 串，求其最长的好子序列。子序列的定义是删去若干个位置后得到的串。

设 len 为 01 串长度。

所有数据均满足 1\le len\le 5\times 10^6。保证 01 串中至少有一个 1。

Solution：

首先考虑枚举 k，然后设将零重新编号，然后预处理出每个零后面第一个一后面第一个零的位置，然后设当前跳到第 x 位，直接跳到 nxt_x+k-1 位置即可。时间复杂度就是调和级数也就是 \mathcal{O}(n\log n)。

C

有 n 种松鼠，第 i 种松鼠有 b_i 只。初始时，第 i 种松鼠栖息在数轴上坐标为 a_i 的点上，保证 a_i 是整数。

松鼠会经常移动。具体地，有下面三种可能的移动方式：

给定 l,r,x：种类编号在 [l,r] 的松鼠全部往数轴正方向移动 x 单位。
给定 l,r：种类编号在 [l,r] 的松鼠全部移动到数轴上同一个整点。由于松鼠很聪明，所以这个整点一定是使得所有松鼠移动距离之和最小的整点。若有多个这样的整点，松鼠会选择坐标最小的。

对于每个 2 操作，你需要输出移动到的整点的坐标。
给定 id,y，种类为 id 的松鼠坐标不变，但总数变成了 y 只。

形式化地，你要支持对 a,b 进行如下三种操作：

给定 l,r,x：将 a_l,a_{l+1},\dots,a_r 加上 x。
给定 l,r：设整数 x 满足 \sum_{l\le i\le r}(b_i\times |a_i-x|) 是所有整数 x 中最小的（若有多个则取最小的那个），将 a_l,a_{l+1},\dots,a_r 全部改为 x。同时，请你输出 x。
给定 id,y：将 b_{id} 改为 y。

所有数据均满足：1\le n\le 5\times 10^5，1\le q\le 5\times 10^5，-10^8\le a_i,x\le 10^8，1\le b_i,y\le 10^8。

Solution：

首先 2 查询怎么做？明显将 a_i 排序，然后前缀和 b_i，找到第一个大于等于 mid 的 a_i 即可。

这里有个结论，就是颜色段均摊，如果只有区间推平操作，假设我们能用 \mathcal{O}(cnt\times F) 维护区间赋值，那么总时间复杂度为 \mathcal{O}(nF) 的。

为什么呢？因为你每次区间推平只会增加 \mathcal{O}(1) 个区间，但是会删掉很多区间，但是删掉的区间不会多于增加的区间，所以总时间复杂度是 \mathcal{O}(n+q) 的。

所以这道题你直接暴力找到所以连续段，也就是线段树二分一下，然后把他们排序之后再区间推平即可。时间复杂度 \mathcal{O}((n+q)\log n)。

D

有一场比赛，规则如下：

共有 n 人。编号为 i 的人初始有能力值 a_i，a_i 是一个正整数。所有人按照编号排成一列。
你作为裁判，会规划 n-1 轮对决，每轮对决里你从当前队列里选出一对相邻的人，让他们开始决斗。设对决的两人能力值分别为 p,q。若 p\ne q，一定是能力值大的人胜利；否则，你指定哪个人胜利。胜者留在队列里，败者离开队列。如果队列有空隙，后面的人向前移动把空隙补上。对决后胜者的能力值增加 1。

不难发现，如果你选出决斗的人的方式不同，你的指定胜利的人不同，最终的胜者就可能不同。我们说第 i 个人“可能获胜”，当且仅当存在一种你的确定赛程以及指定胜者的方式，使得最终的胜者是第 i 个人。

定义函数 f([a_1,a_2,\dots,a_n])=[b_1,b_2,\dots,b_n]，其中 a_i 是上面提到的能力值序列，b_i 是 0 或 1，表示第 i 个人是（b_i=1）否（b_i=0）可能获胜。

你需要解决的问题是：

给定 n,m,[c_1,c_2,\dots,c_n] 和 n 个集合 A_1,\dots,A_n，满足 \forall i,\forall j\in A_i,1\le j\le m。求有多少个正整数序列 [a_1,a_2,\dots,a_n] 满足：

设 f(a)=b。如果 c_i\ne 2，则 b_i=c_i。

答案对 998244353 取模。

所有数据均满足 1\le n\le 40,1\le m\le 80,0\le c_i\le 2。

Solution：

你先考虑如何快速求 b 序列，你肯定可以对于每个点 a_i 往前往后扫能打赢就打，这样做是 \mathcal{O}(n^2) 的。考虑怎么优化。

一个很重要的性质，你能打赢所有人等于你打赢了最大值。这样的话就可以把序列分成两部分，最大值左边的和最大值右边的，你考虑在最大值左边的怎么做？一个点 i 如果在最大值左边，肯定吧最大值左边的全打完再过来打最大值。

这提示我们可以使用最大值来分治。设最大值为 mid，那如果有 i \in [l,mid-1]，那么 i 胜利的充要条件是能把 [l,mid-1] 的全部打败，并且不能小于 a_{mid}-(mid-1)。

所以我们使用 Solve(l, r,x) 表示当前考虑到了 [l,r]，并且最小值是 x 的答案。则递归到了 l=r 就能判断 a_i 能不能赢。

把上面的改成在笛卡尔树上区间 dp。直接记 f_{l,r,x,y} 表示考虑到了 [l,r] 且最小值是 x 并且所有数都不能大于 y（笛卡尔树上的限制）。暴力转移时间复杂度 \mathcal{O}(n^3m^3)。

接下来就很套路了，直接再记一个 g_{l,r,x,y} 表示 y 恰好是最大值。

这样的话 f 可以用 g 前缀和求出来，g 也可以用 f 转移，也就是不用枚举最大值直接转移即可。

时间复杂度优化到 \mathcal{O}(n^3m^2)。

Noip后期第七场模拟赛。

A

给定一个长度为 n 的字符串 S，S 仅包含字符 0 和 1。

定义函数 f(l, r) (1 \leq l \leq r \leq n)：

将 S 中第 l 到第 r 个字符进行翻转（即把 0 变成 1，把 1 变成 0），把生成的字符串记为 T

求对于所有的 l, r (1 \leq l \leq r \leq n)，f(l, r) 的和。

对于 100 \% 的测试数据，有 1 \leq n \leq 10^6。

Solution：

唐诗题目，拆贡献随便做做。

B

给定一个有 n 个点，m 条边的无向图，无重边和自环。点的编号从 1 到 n。

对于每个顶点，你可以为他指定一个在 1 到 n 之间的整数，作为它的点权。点权之间两两不同，所以实际上是一个长度为 n 的排列。

定义 c_i 为：与编号为 i 的点相邻的点中，点权比编号为 i 的点小的点的数量。

请最小化 \max c_i - \min c_i，即最小化 c_i 的极差。

对于 100 \% 的测试数据，有 1 \leq n \leq 10^5，1 \leq m \leq 5 \cdot 10^5。

保证输入的图无重边和自环。

Solution：

唐诗题目，不会发现 \min c_i =0，所以你考虑最小化 \max c_i。

这个东西肯定和度数有关，所以考虑将度数从小到大排序，考虑填什么。

第一个明显填最大的最优，因为他的度数最小，他如果填了其他的数，那么如果最大值在一个度数比他大的点处，那么答案肯定会更大。

所以就这样填，填一个删掉一个。一个点的答案就是他的度数大小。

C

给定 n 个仅由小写英文字母构成的字符串，第 i 个字符串记为 S_i。

若干个字符串的匹配度定义为：他们的最长公共前缀与最长公共后缀的长度的较小值的平方。特别地，单独一个字符串的匹配度为 0。

你需要将所有字符串分为若干组，最大化每组字符串的匹配度之和。

对于 100 \% 的测试数据，有 2 \leq n \leq 10^5，所有字符串长度之和不超过 2 \cdot 10^5。

Solution：

一个很厉害的 trick！将这个字符串重构一下，就是把 s_{1\cdots n} 重构成 (s_1,s_n)(s_2,s_{n-1})\cdots。

这样的话最长公共前缀和最长公共后缀的较小值的平方变成了最长公共前缀的平方。

你又发现了两两分组肯定更优秀。所以你考虑把重构后的字符串全部插入到 Trie 树上，对于每一个前缀长度为 p，他对答案的贡献是他子树里的字符串数量除于二下取整乘上 p^2。但是这样会与他祖先算重，所以我们只计算他对祖先的增量，因为祖先已经算过一遍 p-1 的贡献，所以将 p-1 剪掉，即 p^2-(p-1)^2=2p-1。这道题就做完了。

D

传奇 Nim 游戏，不会莫队自闭了。

Noip后期第八场模拟赛

A

要求有多少个序列满足：

令 v=1\sim n
从 v 号点开始，走到 p_v，…，最后走回 v
记录每个点被走到的次数（起点算，终点不算，反正只算一次）
i$ 号点走到的次数恰好是 $i

答案对 998,244,353 取模

Solution

首先，一个点有一个出边，这个图为什么一定可以走回来？

因为这是个排列啊！不能有相同的入边，每个点只有一个出边，这是什么！这是环啊！

所以整个图就是若干个环，我们要在环上计数。

设我们当前的 a_i 统称为 k，a_i=k 的点数量是 c_k，则这个图有答案当且仅当 k | c_k，为什么？

因为一个环上 a_i=k，那么这个环只有 k 个点，a_i=k 的图有可能会有很多个由 k 个点组成的环，所以必须要 k 能被 c_k 整除

首先考虑这个图上有 \cfrac{c_k}{k} 个环，为了好描述，我们令 \cfrac{c_k}{k}=S，那么我们先从大的角度入手，即分给每个环多少个元素

那肯定是从 c_k 个点选 k 个了，然后再从剩下 c_k-k 个点选 k 个，以此类推，即贡献为

\cfrac{\binom{c_k}{k}\binom{c_k-k}{k} …\binom{k}{k}}{S!}

然后在考虑每个环里的贡献，即有多少种不同的环可以符合条件

我一开始想 1 号点不能在第一个，好难搞啊

但是后面大佬们告诉我，不要考虑细节，直接构造一个环就完事了，想想也确实是这样

因为你这个序列肯定是个环，因为具体在 1 号点填的是这条出边的终点，所以相当于求本质不同的环的个数！！！

所以就是圆排列，也就是 (k-1)! 了，然后有 S 组，相乘就好了

也就是贡献是：

\cfrac{\binom{c_k}{k}\binom{c_k-k}{k} …\binom{k}{k}}{S!} \times (k-1)!^{S}

做完了。

补充，本质不同环的数量是圆排列，考虑证明，我们令每一个圆排列第 i 个点是 a_i，然后他有连向 a_{i+1} 的边，这是一个环。

B

小缘得了玉玉症。

小缘找到了一片巨大的田地，田地的每个格子都可能有一些玉玉。

具体地：

第 1 行的所有格子都有 1 个玉玉。
第 i 行第 1 列的格子有 i 个玉玉。
第 i 行第 j 列（i,j\ge2）的格子里的玉玉个数是第 i-1 行第 j 列的格子里的玉玉个数与第 i 行第 j-1 列的格子里的玉玉个数的异或。

换句话说，记 g_{i,j} 表示第 i 行第 j 列的玉玉个数，那么：

g_{1,k}=1$，$k=1,2,\cdots
g_{k,1}=k$，$k=1,2,\cdots
g_{i,j}=g_{i-1,j}\operatorname{xor} g_{i,j-1}$，$i=2,3,\cdots$，$j=2,3,\cdots

小缘每次会给你一个矩形区域 r_1,r_2,c_1,c_2。小缘想知道所有满足 r_1\le i\le r_2，c_1\le j\le c_2 的田地 (i,j) 上的玉玉的 \operatorname {xor} 和。

对于 100\% 的数据，1\le T\le 10^6，1\le r_1\le r_2\le M，1\le c_1\le c_2\le M，1\le M\le 10^{18}。

Solution：

神奇打表题，我们按位考虑即可，怎么打就乱打发现规律就是如果 x \and y 不等于 0，那么那一位就是 0 否则是 1。

C

小缘得了鱼鱼症，他爱上了养鱼鱼。

养鱼鱼肯定要有水。小缘花了很多时间，挖了一个水池用来养鱼鱼。

水池长 n 米，宽 1 米。水池沿着长被均匀分成了 n 块，第 i 块（到地面的）深度为 D_i（地面为 0）。

初始时，水池里没有水。在开始养鱼鱼前，小缘决定花 m 天来调整水位。

每一天，小缘都会执行下面两个操作之一：

1 x v ：在第 x 块中倒入 v 立方米的水。
2 x ：查询第 x 块的水面到地面的距离。如果这块没有水，则答案就是这块的深度。

水是会流动的，它遵循如下规则：

如果一个块的相邻块的水位高于当前块，那么水会从相邻块流到当前块，直到两块的水位相等，或者水流完了。如果两侧的块中水位都低于当前块，那么一半的水流向左侧，一半的水流向右侧。

当水位超过 0 时，水会溢出。因此水位最大为 0，即水面到地面的距离非负。

小缘希望你来回答他的询问。他会送你许多鱼鱼作为报答。

注意：水是慢慢加入的，而不是在某块上瞬间加入 v 立方米的水。阅读样例和样例解释有助于你更好地理解题意。

对于 100\% 的数据，1\le n,m\le 2\times 10^5，1\le D_i\le 10^9，1\le x\le n，1\le v\le 2\times 10^{14}。

Solution：

锻炼码力的一道题。

我们发现一个坑如果加水超过了他的 \lim，就会和左边或者右边的坑合并，我们考虑使用并查集维护这个过程。

如果我要往 x 加 v 的水，预处理出 L_x,R_x 分别表示往左流会流到哪里，往右流会留到哪里，现在的问题变成了要往一个坑里面加水。

考虑分段维护这个过程，首先把水加到 \lim，然后合并，然后再加水即可。

很多细节。

D

神奇字符串题，不会后缀自动机。

Noip后期第九场模拟赛

A

有 n 位选手匹配对战，保证 n 是偶数。你要安排 n/2 场比赛，每场比赛中挑选 2 位选手同台竞技。需要保证每位选手恰好参加 1 场比赛。

比赛双方都会有得分。第 i 位选手的得分总是在区间 [l_i,r_i] 中，而具体得几分与对手无关，也无法预测。因此，如果安排第 i 位选手与第 j 位选手同台竞技，能得到的节目效果为：

\max_{l_i\le x\le r_i}\max_{l_j\le y\le r_j}|x-y|

求所有匹配方案中，节目效果总和的最大值。

对于 100\% 数据，2\le n\le 10^6, 0\le l_i\le r_i\le 10^9。

Solution：

明显的，一个数要么对答案贡献是 r_i 要么是 -l_i 的，那我们一开始钦定所有数都有 r_i 的贡献，那么将一个数变成 -l_i 需要将它减去 r_i+l_i。

对于原题可以把他变成 |x-y|=\max(x-y,y-x)。这样的话我们贪心选最小的 n/2 个点，把他们变成 -l_i 的贡献是自动满足这个条件的。所以是对的。

B

有 n 间屋子，由 n-1 条双向道路连接成了一个树形结构。其中，第 i 间屋子里居住了 1 个种族为 c_i 的人。

现在你要召集一个连通块内的人。设 a_j 表示被召集的种族为 j 的人个数，若存在 2a_k>\sum_{j=1}^{n} a_j，则种族为 k 的人会造反。

你想知道有多少个连通块会使某种人造反，答案对 998244353 取模。

对于 100\% 的数据，1\le n\le 3000，1\le c_i\le n。

Solution：

就是求绝对众数嘛，有个套路，就是枚举每个数作为绝对众数时的方案，那么我们考虑怎么计算当 x 为绝对众数时的方案数。

考虑每个 x 为 +1，其他的为 -1，就是计算有没有一个联通块的和 >0。

这个问题明显可以用树上背包来做，设 f_{i,j} 为以 i 为节点的子树之和为 j（已滚动），状态转移方程：

f_{u,i+j}+=f_{u,i}\times f_{v,j}

考虑如何优化这个转移，考虑设 x 的数量为 cnt_x，明显的，第二维的范围只有可能在 -cnt_x\sim cnt_x 中，这样就优化了转移。

考虑证明时间复杂度：

没优化

考虑就是物品大小为 1 的普通树上背包转移，考虑那个双重循环就是在枚举每一个以 u 为 lca 的点对，并且只会对 u 产生贡献，那么全局点对数量为 n^2 个，所以时间复杂度为 \mathcal{O}(n^2)。

优化了

如果有 k 的限制，那么肯定比没优化的好，猜测一下是 \mathcal{O}(nk)，考虑证明。

但是笔者不会证明，纯纯一个菜狗。

这样的话，每一次做就是 \mathcal{O}(ncnt_x) 的，考虑总时间复杂度为：\mathcal{O}(n^2)~~（乘法分配律嘛）~~

一个注意的吧，枚举范围的时候可以开个 l 和 r 数组，表示它下面有多少个 1 和 -1，但是要加上自己，这样就能枚举范围了。

C

有 n 个城市，N 市是 n 号城市。每个城市（含 N 市）都有一名代表到 N 市开会。

对于所有 1\le i\le n-1，都有参数 T_i 表示从 i 号城市出发，坐大巴可以到达 i+1, i+2, \ldots, i+T_i 号城市。

给定正整数 K 和非负整数 D。如果一名代表从 i 坐大巴到 j，其疲劳程度会增加：

\left\lfloor \frac{j-i}{K}\right\rfloor \cdot D

第 i 个城市有风景值 H_i，可能为负数。代表的舒适度为：所有经过城市的风景值之和 - 总疲劳程度。

因此你需要对于每个城市派出的代表，求出到 N 市的最大舒适度可以为多少。

对于全部数据 1\le K\le n\le 2\times 10^6, 0\le D,|H_i|\le 10^{10}。

Solution：

很明显的，因为是往后跑的，我们从后往前进行 dp，状态转移方程：

dp_i=H_i+\max_{i< j\le i+T_i} dp_j-\lfloor\frac{j-i}{K} \rfloor D

很明显，朴素的转移是 \mathcal{O}(n^2) 的，考虑使用数据结构来优化整个过程。

考虑后面那个东西很烦，把他拆成 \lfloor\frac{j}{K} \rfloor-\lfloor\frac{i}{K} \rfloor-[j\bmod k<i\bmod k]，这样，我们的状态转移方程就变成了：

\begin{aligned} dp_i=H_i+\max_{i< j\le i+T_i} dp_j-\lfloor\frac{j}{K} \rfloor D+\lfloor\frac{i}{K} \rfloor D+[j\bmod k<i\bmod k]D\\ dp_i=H_i+\lfloor\frac{i}{K} \rfloor D+\max_{i< j\le i+T_i} dp_j-\lfloor\frac{j}{K} \rfloor D+[j\bmod k<i\bmod k]D \end{aligned}

然后考虑维护 S_i=dp_i-\lfloor\frac{i}{k} \rfloor D，然后变成了我们要维护 S_j+[j\bmod k<i\bmod k]D 的最大值。

考虑将一个序列点拆成二维数点，即 (i,i \bmod K)，然后把他放在二维平面上，长这样：

然后我们就分两部分讨论：

明显可以用树套树（时间复杂度 $\mathcal{O}(n \log^2 n)$，寻思着卡卡应该能过（）但是，这么规律的图像想想性质吧。最右边那一段不完整的明显可以对于全局维护一个线段树，直接查就行了。主要是中间那几段完整的怎么查。考虑正规做法扫描线，从上往下扫，用可持久化线段树维护区间最值，查第 $x$ 个历史版本就行了。考虑不用可持久化线段树怎么做。发现这个东西是可以暴力可持久化的，具体做法是对于每一维开一个线段树，然后从上往下扫的时候将线段树复制一份，然后暴力单点改。不会超时吗？我们分析一下复杂度，竖着的是 $k$，横着的是 $\frac{n}{k}$ 个，总时间复杂度是 $\mathcal{O}(k\times \frac{n}{k}\log \frac{n}{k})$，化简一下得到 $\mathcal{O}(n\log\frac{n}{k})$，明显是可以的。至于单点修，先建好，然后再直接修改就行了吧。其实，可持久化线段树的时间复杂度和这个是一样的，因为他每一个位置都修改了一遍，一样的。后面来更新一下，其实这个东西可以写树状数组。维护 $t_i$ 表示 $u\bmod k = i$ 的段的前缀 max，即 $t_i$ 表示 $u \bmod k \le i$ 的最大值。用于查那些整段整段的部分，然后后面那部分没到整段的用个 $\max$ 数组记录一下一段中的前缀 $\max$ 即可。最后在这段的末尾进行更新即可。这个复杂度是对的。 ## D 定义一个序列 $[ b_ 1 , b_ 2 , ..., b _ m ]$ 是可爱的，当且仅当可以将这个序列中的每一个数分到两个非空集合中，使得第一个集合中的每一个数按位与的结果等于第二个集合中每个数按位或的结果。例如序列 $[1 , 7 , 3 , 11]$ 是可爱的，因为可以划分为 $[7 , 11] 和 [1 , 3]$ ，第一个集合中的每一个数按位与的结果为 $3$，第二个集合中每个数按位或的结果也为 $3$。现在给出一个长度为 $n$ 的序列 $a _1 , a _2 , ..., a _ n$ ，又给出 $q$ 组询问，每组询问形如 $ l _ i , r _ i$ ，你需要回答 $[ a _ l , a _{l +1} , ..., a _r ]$ 这个序列是否是可爱的。对于所有数据 $1 ≤ n, q ≤ 10^5$。 ## Solution：有个结论，如果我们枚举答案 $x$，再让我们记录一下他的**二进制下一的个数** $a$，然后如果一个数的二进制下的个数 $b < a$，那么他不可能放进与的集合里面，因为他零的数量已经超标了，如果 $>a$ 那么他不能放进或的集合里面，因为他一的数量已经超标了，如果 $=a$，那么只有可能有一个数，不可能有两个不同的数，设他们为 $x,y$，那么他们既不可能放进一个集合里面，也不可能放进不同集合，因为有一位 $x$ 是 $0$，$y$ 是 $1$ 的话，如果把 $x$ 放进与里面把 $y$ 放进或里面就寄了，但是如果把 $x$ 放入或里面，$y$ 放入与里面，那么你怎么确定 $y$ 没有一位满足 $x$ 是 $1$，$y$ 是 $0$？要么就是 $x$ 的全部 $1$ 都包含在 $y$ 里面了，但是由于 $x$ 和 $y$ 二进制下的一个数是相同的，所以证伪。所以我们只需要线段树维护出一段区间的与和或，然后随便搞搞即可。但是怎么判断一段区间内的所有二进制下 $1$ 的数量 $=x$ 是不同的呢？我们只需要预处理出 $nxt_x$ 表示 $x$ 右边第一个跟 $x$ 不同的数的位置，暴力搞一下即可。 # Noip后期第十场模拟赛 ## A 班上有 $n$ 位同学，他们的学号是从 $1$ 到 $n$，现在在操场上以某种顺序站成了一列纵队。现在，需要选三位同学 $a,b,c$ 依次进行报数，但是需要满足以下两个条件： - $a$ 站在 $b$ 的前面，$b$ 站在 $c$ 的前面（不一定相邻）； - $a$ 是三个同学中学号最小的，$b$ 是三个同学中学号最大的；问你，有多少种选取的方案呢？对于 $100\%$ 的数据，$1\le n\le 3 \times 10^6$； ## Solution：考虑到这个三元组 $(a,b,c)$ 最少要枚举两个数，而这个 $n$ 只允许小 $\log$，像什么线段树，你不是 lxl。但是我们注意到 $a<b<c$ 的三元组很好求，我们枚举 $b$，用树状数组维护出前面比它小的数和后面比他大的数乘法原理即可。但是我们要求的是 $a<c<b$ 怎么办啊？那我们用容斥原理，用两个方案加起来的减掉上面那个就可以了。总的怎么求呢？也就是要求 $a<b,c$ 的值，我们用树状数组维护出比 $a$ 大的数，然后从这里面任选两个，也就是 $\binom{sum}{2}$，然后减掉上面那个就好了。固定左端点吧，好做一点。 ## B 有一个方程 $$x^2-2kx+b=0$$ 求有多少组正整数参数 $k$ 和 $b(b \in [P,Q])$，满足这个方程的 $x$ 是有整数解的。对于 $100\%$ 的数据，$1 \le P \le Q \le 10^{12}$，$1\le T \le 10$。 ## Solution：解这个方程，解得：$x=k \pm\sqrt{k^2-b}$，这个东西有整数解就要保证根号里面那坨要是**完全平方数**。写出来就变成了 $k^2-b=t^2$，以初中数论知识可得，把右边的移过去，然后质因数分解得到：$(k+t)(k-t)=b$。但是注意了我们搞到的 $i$ 和 $\frac{i}{b}$ 必须是同奇偶的，证明略。所以我们就有个暴力的想法，枚举每一个 $b$ 算答案。时间复杂度会爆。注意到这里有大量重复运算，如枚举一个 $i$ 就枚举了 n 多次，所以我们枚举 $i$，求 $[i,R]$ 的所有可能得方案，即 $i\sim \lfloor \frac{R}{i} \rfloor$ 所有和 $i$ 同奇偶的数，这里必须保证 $\lfloor \frac{R}{i} \rfloor > i$，所以 $i\le \sqrt{R}$，所以单次枚举是 $\mathcal{O}(\sqrt{n})$ 的。最后用 $Q$ 的答案减掉 $P-1$ 的答案即可。 ## C 有一个长度为 $n$ 的整数序列，你需要支持两种操作： - 区间加法，把 $[L,R]$ 这个区间内的所有数 $v$，都令 $v\gets v+d$； - 询问在序列中选一个长度为偶数的子序列，子序列的偶数项的和减去奇数项的和最大是多少，同时在保证最大的前提下，子序列的长度最短是多少；满足所有数据 $1\le T \le 5$，$1\le n,Q\le 10^5$，$ |d| \le 10^5$，任意时刻 $0 < a_i < 2^{31}$。 ## Solution：子序列偶数项减去奇数项完全可以理解成第 $2$ 个减去第 $1$ 个，第 $4$ 个减去第 $3$ 个，发现这个东西是相互独立的，所以我们可以把每个操作看成一个整体，即 $a_k-a_j (j<k)$。这个东西不好维护，但是我们有个套路，就是把这个序列差分一下。于是乎，我们设 $b_i=a_i-a_{i-1}$，那么 $a_k-a_j=\sum_{i=j+1}^k b_i$，于是乎，这个相减，就变成区间加！于是乎这个操作就变成了在差分数组上选取几段相加起来最大，至于修改操作，就转换成了单点修。很容易想到把所有正数加起来就是第一问的答案。考虑第二个问题，也就是询问总段数最小，这个时候我们可以考虑选不选 $0$。 + 如果这个 $0$ 把左右的正数连在一起了，比如 $2,2,0,0,3,3$，这个时候这个 $0$ 就可以选。 + 否则不选。考虑线段树。维护四个值，$vl,vr,sum,all$，分别表示左边可以合并，右边可以合并，总段数和是否全为 $0$。注意，这个 $vl$ 和 $vr$ 是维护的正数，以及符合条件的 $0$，$all$ 是方便合并。轻易维护，细节较多。 ## D 有一个公园有 $n$ 个景点，用 $n-1$ 条双向道路连通起来。白云想参观里面的一些景点，从 $1$ 号景点出发。不过，它不想走重复的道路，所以，它规定，走的路线中，同一条边的同一个方向不能走两次。现在，白云想知道，对于任意的点 $i$，白云有多少种方案行走，最后停留在了点 $i$。两种方案不同，当且仅当走的边数不同，或者某一步走了两条不同的边。对于 $100\%$ 的数据，$1 \le n \le 10^4$。 ## Solution：肯定是树形 dp，首先要处理 $1$ 号节点的答案。考虑怎么做？直接记 $f_{i,j}$ 表示节点 $i$ 选了 $j$ 个儿子行走的方案数，明显这是一个 0-1 背包，滚动数组一下，最后 $F_i$ 的答案就是 $\sum_{i=0}^m f_i \times i!$。考虑类似于换根的思路，如果 $u \rightarrow v$ 的话，那么就考虑将 $F_u$ 传递给 $v$，考虑怎么传递？显然就是将计算 $u$ 答案的时候把儿子 $v$ 去掉的方案，考虑用 $v$ 这个儿子对 $u$ 倒着做 0-1 背包，把 $v$ 的贡献剪掉即可。就是一个普通换根题。比 T3 简单。 # Noip后期模拟赛第十一场 ## A 小诗有一个排列 $p_1,p_2,\cdots,p_n$，她可以每次选择一个长度为 $k$ 的区间 $[p,p+k-1]$（$1\leqslant p\leqslant n-k+1$），她可以选择区间内一个数 $v$，将整个区间内的数都修改为 $v$。现给定 $1\leqslant C\leqslant n$，她想知道将序列内所有数修改为 $C$ 的最小操作次数。如果无法满足，请输出 $-1$。数据范围：对于所有测试点，保证 $1\leqslant C,k\leqslant n\leqslant 2\times 10^5$。 ## Solution：唐诗题，直接构造区间的交集为一的区间即可。答案也就是 $\lceil \frac{n-1}{k-1} \rceil$。 ## B 小诗有一个整数 $x$（可以为负），她想找一个区间 $[l,r]$ 包含 $x$（即 $l\leqslant x\leqslant r$）使得 $\sum_{i=l}^ri$ 是素数，在此基础上最小化区间长度（即 $r-l+1$），保证存在这样的区间。小诗会询问 $T$ 次，如果你能准确无误地回答每次询问，她就会奖励你 100 分。数据范围：对于所有测试点，$1\leqslant T\leqslant 10^5,|x|\leqslant 10^7$。 ## Solution：先考虑到这个区间不能太长，因为当 $l > 0$ 时，$r-l+1\ge 3$ 时，这个区间相加肯定是个合数。证明：考虑这个序列的平均数 $x=\frac{\sum_{l\le i \le r}i}{r-l+1}$，所以这个区间和也能表示为：$x\times (r-l+1)$。 + 当 $r-l+1 \equiv 1 \pmod{2}$ 时，$x$ 是这个区间的中间的那个整数，又因为 $r-l+1\ge 2$，所以这个区间和肯定是一个合数 + 当 $r-l+1 \equiv 0 \pmod{2}$ 时，$x$ 时一个分数为中间两个数的平均数，且分母为 $2$，但是我们考察 $x\times(r-l+1)$，因为 $r-l+1$ 只能为大于 $2$ 的偶数，所以这个区间和肯定也是一个合数。所以我们就可以把合法区间两类，第一类是 $[p,p],p\in \mathbb{P}$，第二类是 $[q-1,q],2q-1 \in \mathbb{P}$，分别对应区间长度为 1 和 2 的区间。那这样不是没答案了？但是如果我们考察 $l<0,r>0$ 的区间，我们就会发现有重复的被抵消掉了，所以我们的限制变为了 $r-(-l)+1\le 2$ 即 $r+l\le 1$。所以这样的话，我们就可以将这种情况的两类合法区间表示出来了。 + 第一类，设左边的是 $-a,a>0$，右边的是 $p$，则可以表示为 $\frac{(p-a)(p+a+1)}{2}=p$，很明显的，$a=p-1$ 时明显满足，所以这个区间表示为了 $[1-p,p]$。 + 第二类，设左边的是 $-a,a>0$，右边的是 $q$，则可以表示为 $\frac{(q-a)(q+a+1)}{2}=2q-1$，明显的，$a=q-2$ 时明显满足，所以这个区间表示为了 $[2-q,q]

于是，我们就可以讨论了。

当 x>0 时，检查 [x,x],[x,x+1],[x-1,x]，以及最小的 [1-p,p],[2-q,q](p,q\ge x)。
当 x<0 时，我们就只需要检查最小的 [1-p,p],[2-q,q] (p,q\ge 1-x)。

C

神秘字符串题，不会。

D

小诗有一个排列 a_1,a_2,\cdots,a_n，她想类似冒泡排序地整理排列，以及在整理的过程中了解排列的一些信息。

具体地，你需要维护 q 次操作，操作分两类：

1，表示进行一次冒泡排序；
2 x y，表示她想知道 \sum_{i=x}^y a_i 的值是多少。

冒泡排序可以看作以下代码执行的结果：

for(int i=1;i<n;i++)
        if(a[i]>a[i+1])
                swap(a[i],a[i+1]);

数据范围：

对于所有测试点，1\leqslant n,q\leqslant 10^6，保证 a_i 是一个 1,2,\cdots,n 的排列。

Solution：

我们刻画每一次冒泡排序究竟是在干什么。

可以发现每次冒泡排序就是把这个序列的前缀最大值放到下一个前缀最大值的前面。

为了方便维护，我们把前一个前缀最大值放到下一个前缀最大值那里，以此类推，最后一个前缀最大值新开个位置放。

这样有什么好处？每个位置它不可能从是前缀最大值变为不是前缀最大值。因为他被平移过来肯定是比前面的任何元素要大。

所以只需要考虑维护新出现的前缀最大值。

需要单点修，考虑使用树状数组，因为不知道要干什么所以先考虑怎么求和。

对于 [l,r] 的求和，我们可以转化为 [1,l] 和 [1,r] 的前缀求和。

考虑建立一个权值线段树，因为前缀最大值单调递增，所以我们可以先求出这段区间有多少个前缀最大值，这个可以用树状数组维护区间的前缀最大值数量，然后使用线段树二分求解前缀最大值的区间和，然后最后再用树状数组维护出这段区间内不是前缀最大值的区间和，加起来即可。

考虑什么时候一个点加入前缀最大值，容易发现记他前面有 t 个比他大的数，他将会 t+1 时刻变为前缀最大值，这个轻易维护。

时间复杂度：\mathcal{O}((n+q)\log n)。

Noip后期第十二场模拟赛补题

A

小 A 有一个仅包含 01 的字符串，但是他觉得这个串太复杂了，他比较喜欢简单的 01 串。

定义一个 01 串是简单的当且仅当它的所有字符都是 0 或都是 1。比如 00000 和 111 都是简单的串但 0011100 和 001 不是。

给定一个 01 串 S，小 A 有 Q 次询问，每次询问 [l,r] 这段区间中有多少个简单的子串。

对于 100\% 的数据，1\le |S|,Q\le 5\times 10^5，1\le l\le r\le |S|。

Solution：

经典结论，颜色段数=区间长度-区间内 a_i=a_{i+1} 的个数。

前缀和一下即可。

B

小 A 觉得现有的排序算法都太慢了！因此他设计了一种新的排序算法：

对于长为 n 的序列 a_1\sim a_n，给定 m 对正整数 (x_i,y_i)。

对 m 对 (x_i,y_i) 依次进行如下操作：若 a_{x_i}>a_{y_i} 则交换两数。

显然这个排序算法并不总是对的。对于给定的算法请你分析出这个算法是不是一定能将任意一个长为 n 的序列升序排序。

为了估计这个算法的正确率，小 A 还想让你帮他求出对于所有 n! 种排列，有多少种排列能被这个算法升序排序。由于答案可能很大，你只需要输出答案模 10^9+7。

注：升序排序表示将一个序列排好序后，对于任意 1\le i<n 都有 a_i\le a_{i+1}。

对于所有测试点，1\le T\le 10，3\le n\le 18，1\le m\le 300，1\le x_i,y_i\le n。

Solution：

现在先考虑第一问，即判断一个 n! 的是否能被 m 对 (x_i,y_i) 升序排序。

这里有乱搞做法，就是判断 n,n-1\cdots 1 的序列能否被排序，如果能输出 Yes，否则输出 No。

还能随机化几组数据跑。

乱搞地方结束，进入正题：

n\le 9：

这一部分明显可以枚举每个排列然后 check 一下，时间复杂度是：\mathcal{O}(n!m)

n\le 18：

这一部分 n 变大了很多怎么办？

这里有个很神奇的结论，也就是我们可以把这个序列转变为 0,1 序列进行排序

具体的：如果以 1,4,2,3,5 举例，假设将 \ge 3 的数变为 1，否则变为 0，则这个序列变成了 0,1,0,1,1。

这个完美的转化可以证明：

必要性：

如果任何可以 n! 的序列都能被排序，但是有个 0,1 序列不能被排序，则肯定有对 1,0，此时前面的 1 的原数肯定是比后面的 0 的原数大的，所以必要性证毕。

充要性：

如果任何 0,1 序列都能够排序，但是有个原数序列不能被排序，则一定可以找到一组 x,y 使得 x>y，那么这时以 >y 为分界线划定 0,1，则 x,y 会变成 1,0，这矛盾，所以充要性证毕

所以求 n! 个序列能否被排序，变为了求解 2^n 个 0,1 序列能否被排序，时间复杂度为：\mathcal{O}(2^nm)，足以通过第一问。

考虑第二问怎么做：

因为要求所有能被排序的序列的方案数，假设现在有一个能被排序的序列，它所涉及到的 0,1 序列有什么。

发现是 0,0\cdots0,0 到 1,1\cdots 1,1 的路径，即每一次把一个数变为 1。

这种情况极其像路径计数，那就是状压的基本套路了，即考虑设 f_S 表示 S 能被排序的前提下，一直到 S 的方案数

明显的：f_T+=f_S，最后我们要的就是 f_{1,1\cdots1,1}，输出即可。

C

小 A 来到了 ION 3202 的嘉年华活动场地。最受选手欢迎的是一个叫“套圈”的游戏：将场地看作一个二维平面，有 n 个坐标上有字母，字母是 \texttt{I,O,N} 中的一个。选手的目标是扔出一个长方形的空心环，套住三种字母各至少一个。

小 A 对自己的投掷水平很有信心，他想让你求出最小的长方形周长，使其大小能足够在某个位置套住三种字母各至少一个。

对于 100\% 的数据，3\le n\le 10^5，0\le x_i,y_i\le 10^8，c_i\in \{\texttt{I,O,N}\}，保证三种字母都至少有一个。

Solution：

高质量扫描线题。首先只有可能有两种情况需要分讨。

这种情况的周长是 2(x_g+y_g-(x_r+y_r))

那么考虑这种的话，开两颗树状数组 T_1,T_2，我们对 x 轴从左到右扫一遍，如果遇到红点，那么就将 x_r+y_r 扔到T_1上，如果遇到蓝点，就把这个点的 T_2 更改为 1\sim y_b 的最大值，遇到绿点，就查询一下 1\sim y_g 的 T_2 的最大值，相减即是答案。

这种情况的周长是 2(x_g+y_b-(x_r+y_r))。同样按照所有点的 x 做一次扫描线，维护一颗线段树，线段树上 [l,r] 维护三个信息，R 表示所有 y_r \le l 的红点的最大值，B 表示所有 y_b \ge r 的蓝点的 y_b 的最小值，RB 表示最小的 y_b-(x_r+y_r)，使得 x_r\le x_b。遇到红点就将 [y_r,\max] 上更新 R，如果遇到蓝点就在 [0,y_b] 上更新 B 并且更新 RB。遇到绿点就查询对应叶子的最小值，注意下传顺序！

做一次时间复杂度是 \mathcal{O}(n\log n) 的，由于颜色之间的顺序和 x,y 坐标的对称，需要每种情况做一次也就是 3!\times 4=24 次。

D

困难 dp 题，不会。