引言

今年命题会的时候，我们惊奇地发现今年的模拟题还没有着落。

于是我翻出了这个压箱底的 idea，当作一个中模拟。

idea 恰如其分来自在你清食堂的吃饭经历，获得了大家的一致认同。

时限只开 3s 是因为有 100 个点，开太久会更严重地卡评测的。std 跑了 1.6s。出题人试图开 5s 被系统部和赛务部的同学们拦下了

比赛情况

本题的完整版本预期难度是 medium，不过我个人认为是 easy+（？）。

丝路市西套村代表队获得了本题首杀！

本题大约有一半的队伍通过了本题。

同时，不少夺冠热门队伍在本题上获得了大量罚时。

题意简述

食堂餐桌座位分布在第一象限网格每个 $3 \times 3$ 完整格子右上角的 $2 \times 2$ 格子，剩下的部分为走廊。

每次可以从一个走廊格子走到四连通相邻格子。

每次一名顾客从最左下角的格子出发，试图找到最优的一个满足自己容忍条件的空座位。容忍条件形如桌子上坐了几人以及自己因此应该去哪里（请参考原题面）。

此外还会有部分座位突然出现或消失顾客，也即状态翻转。

输出每次顾客坐到了哪里，以及突然变化的顾客是来是去。

操作次数 $q$ 不超过 $5 \times 10^5$。第二类操作值域不超过 $10^4$ 且总是修改在餐桌处。3s/1GB。

思路

本题总体思路比较简单，这里直接给出完整版正解做法。

注意到第一类操作可能遇上的下标范围是 $O(\sqrt{q})$ 级别的，我们不妨考虑做预处理。

观察到其优先顺序是固定的，我们可以预先排序得到各个餐桌格子的优先顺序。这个排序可以通过数学方法或者 bfs 做到线性。

考虑第一类操作，我们可以用 set 或可删堆（对顶堆）存一下每个满足对应条件的位置。

第二类操作对于下标超界的部分也可以单独拿一个 set 存；没超界的部分可以和前面的部分使用同一套方法处理。

不用太多卡常，验题人开了八九个 set 都过了。std 不到 2kb。

本题非常善良，值域只开 $10^4$ 是为了方便压位（记得用 $10001$ 压）。没有特意卡 umap/bitset 之类的东西，应该是可以轻松过的。

总结

• 在这样一场毒瘤的比赛中，
• 这道题目无疑是出题人无私的馈赠，
• 经典的模型、较低的难度和不大的代码量，能帮助你把分数收入囊中
• 出题人相信，这个美妙的题目，可以给拼搏于 XCPC 的追梦之路上的你，提供一个有利的援助。

题意

求有多少个长度为 $n$ 的排列，使得 $S$ 为其长度为 $k$ 的字典序最大的子序列和其长度为 $k$ 的字典序最小的子序列的最长公共子序列之一。

题解

下文用 $T$ 代替 $S_0$，用 $R$ 代替 $S_1$。

性质一：考虑 $T$ 的形态，令 $i=\min\{i \mid i = k \lor T_i < T_{i+1}\}$，则 $T_1, T_2, \cdots, T_i$ 为 $p$ 字典序最大子序列长度为 $i$ 的前缀，$T_{i+1}, \cdots, T_k$ 为 $p$ 的长度为 $k - i$ 的后缀。

下称 $T_1, \cdots, T_i$ 为 $T$ 的头部，$T_{i+1}, \cdots, T_k$ 为 $T$ 的尾部。可以用类似的方式定义 $R$ 的头部与尾部。

容易发现 $S$ 唯一。考虑 $S$ 的形态。不妨令 $T$ 的尾部长度 $< R$ 的尾部长度。则 $T$ 的尾部一定是 $S$ 的一段后缀。删除这段后缀后，令 $R$ 尾部的剩下部分为 $p_l, \cdots, p_r$。则此时 $S$ 的一段后缀为有序集合 $\{p_i \mid i \in [l, r] \land p_i \in T \}$。删除这段后缀后，剩下的部分为两个头部的最长公共子序列。由于两个头部都是单调，因此 $S$ 剩下部分的长度至多为 $1$。

接下来可以考虑分类讨论开始 dp 计数了。

1. $S_1$ 为 $T, R$ 头部的一部分。

   对于 $S_1$ 前面的部分，我们要计数的问题是：有多少个长度为 $i$ 的排列，其字典序最大子序列的长度为 $j_1$，字典序最小子序列的长度为 $j_2$，且它们的最后一位一定是 $k$。发现 $\le k$ 的部分与 $\ge k$ 的部分是独立的，只需要分别 $dp$ 再组合数拼起来即可。现在的问题转换为：长度为 $i$ 的排列，其字典序最大子序列长度为 $j$，其最后一位和字典序最大子序列的最后一位为 $k$。这个容易用 $\Theta(n^3)$ 的时间复杂度 dp。

   对于 $S_1$ 后面的部分，不妨令 $S_2 < S_1$。则 $S_2$ 一定为 $R$ 的尾部。讨论 $T$ 的尾部是否比 $R$ 更长。

   1. $T$ 的尾部比 $R$ 的更长。

      则 $S_1$ 与 $S_2$ 之间必须存在数，且这些数都必须大于 $S_1$。对于 $S_2, \cdots, S_m$，其一定为原排列的一个后缀。这部分容易计数。

   2. T 的尾部比 R 的更短。

      令 $i = \min\{i \mid i = m \lor S_i < S_{i+1}\}$，则 $S_{i+1}, \cdots, S_m$ 为原排列的一个后缀。此时只需要对 $S_1$ 与 $S_i$ 之间的部分计数。此时问题转化成，有多少个长度为 $n'$ 的排列，其字典序最大子序列的长度为 $i$ 的前缀为 $S_1, \cdots, S_i$。这一部分也容易用 $\Theta(n^2)$ 或 $\Theta(n^3)$ 的时间复杂度 dp。

2. $S_1$ 为 $T, R$ 尾部的一部分。

   不妨令 $T$ 的尾部长度小于 $R$ 的尾部长度。则 $S$ 为 $T$ 的尾部。枚举 $R$ 的尾部长度与 $T$ 的尾部长度之差 $i$，再枚举 $T$ 的头部的最后一位 $p'$ 是多少。分开对 $p_1, \cdots, p'$ 和 $p', \cdots, S_1$ 计数。这两部分都可以用类似于 1 中对 $S_1$ 之前部分计数的方法计数。注意这个东西可以预处理，没有必要每枚举一次都重新计数一遍。

3. $S_1$ 为 $T$ 头部、$R$ 尾部的一部分或 $R$ 头部、$T$ 尾部的一部分。

   不妨令 $S_1$ 为 $T$ 头部、$R$ 尾部的一部分。

   $S_1$ 后面的部分与 1.2 相同。

   下面尝试对 $S_1$ 前面的部分计数。

   令 $k_2$ 为 $R$ 头部的最后一位，$k_1$ 为 $T$ 中 $S_1$ 前面的数。

   1. $S_1$ 为 $R$ 尾部的第一位。

      则 $S_1$ 的前一个数一定为 $k_1$。枚举 $k_2$，将 $\le k_2$ 的部分与 $> k_2$ 的部分使用类似于 1 中 $S_1$ 前面部分的方法分开 dp 计数。注意这个东西可以预处理，没有必要每枚举一次 $k_2$ 就重新 dp 一次。

   2. $S_1$ 不为 $R$ 尾部的第一位，且 $k_2 < S_1$。

      枚举 $k_2$，再枚举 $R$ 尾部在 $S_1$ 之前的长度，以 $k_2$ 或 $S_1$ 为界分开 dp，用上述方法仍然容易处理。

   3. $S_1$ 不为 $R$ 尾部的第一位，且 $k_2 > S_1$。

      这就要求 $k_2$ 必须在 $k_1$ 前面。注意到 $k_1$ 之后一定紧挨着 $R$ 尾部的第一位。枚举 $k_2$，再枚举 $R$ 尾部的第一位与 $S_1$ 之间有多少数，一样可以用类似的方法 dp。

总时间复杂度 $\Theta(n^3)$。

Bonus: $n \le 5000$。

瓶颈在于以下问题：有多少个长度为 $i$ 的排列，其字典序最大子序列的长度为 $j$。

设 $dp_{i,j}$ 为我们所希望求出的答案。每次尝试向已有排列中加入一个更小的数。如果这个数被放在了整个排列的最右边，则字典序最大子序列的长度会增加 $1$，否则不变。按照这个思路对 dp 式子进行转移，时间复杂度 $\Theta(n^2)$。

由于 $\Theta(n^2)$ 算法不仅要求对 dp 进行优化，还要求选手在分类讨论的过程中进行相当精细的实现，因此最终只开了 $n \le 400$ 来允许实现相对较差的算法通过。

题意简述

给定 $n$ 个非负整数 $x_1,x_2,\dots,x_n$。

对于任意 $n$ 个节点的无向连通图 $G$，将其节点由 $1$ 至 $n$ 标号，则其分数定义为 $$\text{score}(G) = \sum_{i=1}^n \sum_{j=i+1}^n \text{dist}_G(i, j)x_ix_j,$$ 其中 $\text{dist}_G(i,j)$ 表示图 $G$ 上 $i$ 到 $j$ 的最短路径长度。

你的任务是输出所有 $n$ 个节点的无向连通图中分数的最大值。

$1 \le n \le 300$，$0 \le x_i \le 2000$

解法

我们首先假设至少有两个 $x_i$ 不为 $0$，否则答案一定是 $0$。

定理 1：一定存在一棵树取到最大分数。

不是一棵树的 $G$ 删掉一条不改变连通性的边肯定会让 $\text{dist}_G(i,j)$ 变大，所以这个定理是显然的。不过只知道 $G$ 是一棵树还不足以解决本问题。

定理 2：一定存在一条链取到最大分数。

假设分数最大的 $G$ 是一棵树但不是一条链。以任一度数大于等于 $3$ 的点 $r$ 为根。不妨假设其度数为 $3$，三个子树为 $A,B,C$，子树根分别 $a,b,c$，子树的 $x$ 的和分别为 $x_A,x_B,x_C$。假设 $x_A \le x_B \le x_C$。

考察如下调整：删去 $(r,b)$ 加上 $(a,b)$。此时从 $C$ 和 $r$ 到达 $B$ 的距离增加 $1$（多经过 $a$），从 $A$ 到达 $B$ 的距离减少 $1$（少经过 $r$），其他距离均不变。

因此图的分数变化为 $(x_r+x_C-x_A)x_B$。当这个值大于 $0$ 的时候，我们就可以得到一个分数更大的方案，矛盾。

若 $(x_r+x_C-x_A)x_B = 0$，有两种情况：

• $x_B = 0$，此时子树 $B$ 里的所有点 $p$ 都有 $x_p = 0$。将这些点插入到任意两个 $x$ 不为 $0$ 的点 $a, b$ 的路径中（注意我们假设了至少有两个 $x$ 不为 0），这样一定会让分数变大。
• $x_A=x_B=x_C$ 且 $x_r=0$。此时我们尝试进行调整以最大化第二个目标 $\text{score}^\star(G) = \sum_i \sum_{j > i} \text{dist}_G(i,j)$。注意到这个就是所有 $x$ 都是 $1$ 的版本所以一定可以进行调整，而这样调整一定不改变 $\text{score}(G)$。

因此每次调整要么会提升 $\text{score}(G)$，要么 $\text{score}(G)$ 不变的同时 $\text{score}^\star(G)$ 增加，而两者均为正整数且有上界。故不断进行调整后必然到达一个 $(\text{score}(G), \text{score}^\star(G))$ 的局部最大值，此时无法进行以上调整，也就是不存在度数大于等于 $3$ 的点。证毕。

运用以上定理，我们此时的任务是把 $x$ 重排为 $x'$，最大化 $\sum_i \sum_{j>i} (j-i)x_ix_j$。

我们还需要以下有关这个问题的解的性质。

定理 3：一定存在一个单谷的重排 $x^\star$ 达到最大分数。

不妨假设 $x$ 两两不同且大于 $0$，这可以通过给每个数加上一些微小扰动完成。

若最优的重排 $x^\star$ 不是单谷的，则存在 $p$ 满足 $x^\star_{p-1} < x^\star_p>x^\star_{p+1}$。考虑两种调整：

• $\text{swap}(x^\star_{p-1},x^\star_p)$，分数增加 $(x^\star_p - x^\star_{p-1})(x_{p+1 \sim n} - x_{1 \sim p-2})$；
• $\text{swap}(x^\star_{p+1},x^\star_p)$，分数增加 $(x^\star_p - x^\star_{p+1})(x_{1 \sim p-1} - x_{p+2 \sim n})$

注意到两个增量的第一项都是正的，而两个第二项的和为 $x_{p-1}+x_{p+1}$ 也是正的，因此必然存在一个调整增大分数。证毕。

最后我们把分数式子稍微变换一下。

$$\begin{align*} \sum_i \sum_{j>i} (j-i)x_ix_j & = \sum_i \sum_{j>i} \sum_{k=i}^{j-1} x_ix_j \\ = & \sum_k \sum_{i \le k} \sum_{j > k} x_ix_j \\ = & \sum_k x_{1 \sim k} \times x_{k+1\sim n}, \end{align*}$$

也就是说分数等于每个位置的前缀和和后缀和的乘积的和。

由于最优解是单谷的，考虑从大到小依次加入每个 $x_i$，此时每个 $x_i$ 一定加在未加入的部分的第一个或最后一个。加入进去之后，可以确定一个前缀和（加在后面是确定后缀和，其实也就是确定了剩余位置的前缀和），也就确定了分数中一项的贡献。

因为分数只关心每个位置的前缀和是多少，依此设计 DP：设 $f_{i,j}$ 表示加入了前 $i$ 大数，加在前面的所有数的和为 $j$ 时分数的最大值。加在后面的数的和可以直接通过 $i$ 和 $j$ 推导出来。转移枚举第 $i+1$ 大数放在前面还是后面，加上对应项的贡献即可。

复杂度 $O(n^2 \max x_i)$。

简要题意

给定正整数 $n$，构造一个 $1$ 至 $n$ 的排列 $p_1,p_2,\dots,p_n$ 满足以下条件：

• 对于 $1 \le i \le n$，设 $c_i = \lceil \frac{p_1+p_2+\dots +p_i}{i} \rceil$，则在 $c_1,c_2,\dots,c_n$ 中至少有 $\lfloor \frac{n}{2} \rfloor$ 个质数。

$n \le 10^4$

解法

本题有很多（乱搞）解法，这里给出一个可以严格证明的做法。

考虑将 $c$ 的一个前缀都赋值成相同的质数。这可以通过取一个质数 $p$ 并将前缀排列成 $p, p-1, p+1, p-2, p+2, \dots$，这样长度为 $2\min(p, n-p+1)-1$ 的前缀的 $c$ 值都是 $p$。

根据 Bertrand's Postulate，对于任意整数 $x$，$[x,2x]$ 内至少存在一个质数。

取其中的任意一个质数，长度 $\left(2\lfloor \frac{n}{3}\rfloor-1 \right)$ 的前缀就都是质数了。

题目要求共有 $n$ 个结点，将其中 $k$ 个点染成黑色（本题解中为了方便描述，通称所有未染色的点为白点），求黑点两两距离及白点两两距离，使他们之和最大。

我们可以将距离转化为路径，然后再将路径拆分成边，就可以记录每条边被经过的次数，直接计算即可。

问题来了！：那么每条边会对答案贡献多少呢？

我们不妨设这条边的一侧共有 $w$ 个点，其中有 $t$ 个点被染成黑色了；

那么这一侧共有 $t$ 个黑点，（$w-t$）个白点；类似，另一侧有（$k-t$）个黑点，（$n-w-k+t$）个白点；

令 $sz$ 为这条边的边权，那么贡献就是 $val=sz*(t*(k-t)+(w-t)*(n-w-k+t))$;

解题的大致思路就是计算每条边对答案的贡献，最后利用状态转移方程求出最优解。

首先给出状态数组：$f[x][y]$;

$f[x][y]$ 表示给以 $x$ 为根结点的子树染上 $y$ 个点所得的对于整棵树的最大贡献；

方程如下：

$f[i][j]=max(f[i][j],f[i][j-t]+f[z][t]+val);$( $z$ 表示 $i$ 的子结点)

目标状态：$f[1][k]$;

PS:中间可能遇到非法情况，建议把 $f[x][y]$ 预处理成非法情况，方便跳过处理（代码最后有针对这点的样例，可自行调试）；

强烈建议参考代码理解！！！！！

Over.

(第一次写题解，不足之处请大家多多包涵》_《)

题意

$n$ 只猫娘，每只猫娘每天要么自己举行了排队，要么会追随自己最好的朋友去参加她要去的派对。

举办的派对有 $3$ 种类型，在每一天晚上都会有一只猫娘举办了某种类型的派对，这只猫娘会一直举行下去直到自己换类型，问每天晚上这三种类型的派对都几只猫娘参加。

思路

首先把猫 $i$ 与自己的朋友连一条有向边，那么整张图就是一个内向基环树。每当一只猫娘举行了派对，这个结点相当于把自己和父亲结点的连边断开了，我们就需要统计每个举办派对的结点子树大小。

如果我们直接对着每一天的修改一个一个做，那么要处理分裂的问题，也能做但是不是很好写，所以我们考虑倒着做。

具体来说，每一天把当前猫娘举办的派对的答案回溯到这只猫娘举办的上一个派对那里（因为这只猫娘从上一个派对到举行当前派对这段时间一直都没变），但是如果这是这只猫娘举办的第一个派对了，那么来她排队里的猫娘和她自己都会跟随她的父亲结点，相当于连上了一条边，可以直接用dsu做，假如当前父亲节点追随的结点举办了派对，那么我们需要把当前结点子树的大小统计进这个派对的类型中。

差点忘了，我们既然从后往前做了，那需要初始化每种类型在最后时刻的人数，可以直接把一直都没举行派对的猫娘直接和她们的父亲节点连起来，然后对于有派对的把对应类型类加上自己子树的大小，然后从后往前一步一步更新当前答案这题做完了。

有一个注意的点在于并查集合并方向要写对，不然只能得 $4$ pts（也可能是我写法问题）。

这题洛谷评蓝是不是太夸张了（