English version

Each operation transform three adjacent characters into one. If the string starts with 11, the answer should be yes since we can first transform the remaining part into a single 0 or 1 and then the value of 11? is always $1$.

If the string ends with 1, only 101 has no solution, otherwise it starts with 11 or 0, or we can transform 10? in the front of the string into a 0. Then transform the rest part of the string into a single character to make the last operation 0?(anything):1 makes 1.

If an operation transformed a string ending with 0 into one ending with 1, it must be 1?1:0 makes 1.

Consider the case where the strings contains 11 as a substring. After transforming the remaining part, ?11?? or ??11? will be derived. The cases are 01100, 00110, 01110, 10110. All other cases start with 11 or end with 1.

All cases of ??11? have a solution:

(0?0:1)?1:0 makes 1.

(0?1:1)?1:0 makes 1.

1?(0?1:1):0 makes 1.

However, 01100 has no solution.

Since 0?0:1 equals 1, before the last 1, any two adjacent 0's with no 1 in between can be eliminated. Thus, if there are two 1's with an even number of 0's in between, and there are an even number of characters in front the former 1, i.e., (..)*1(00)*1(..)*0 in regular expression, the answer should be yes, since after eliminating the 0's in between, the 1's become adjacent. The parity of the characters before the former 1 guarantees that it will not become 01100.

Another case is that the string ends with 0 and every pair of adjacent 1's has an odd number of 0's in between. Since 0(1?0:1)0 makes 000, 1(0?1:0)1 makes 101, 10(1?0:0)01 makes 10001, there is no way to change the parity of the consecutive 0's to make 11 to change the ending 0 into 1.

In the remaining case, there are even 0's between some pair of adjacent 1's, but the number of characters before the first 1 is odd, there must be only one pair. Suppose the string is 1-indexed. It is because the indices of such pair of 1's must be [odd, even]; while the indices in the previous case must be [even, odd]. Thus, if there are two such pairs of this case [odd, even], in the parity sequence [odd, even, ..., odd, even] there must be an [even, odd] as a substring.

Therefore, any other pair of adjacent 1's must have odd 0's in between, i.e., $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{black}(00)^*\color{red}1\color{blue}((00)^*01)^*\color{black}(00)^+$ in regular expression. Any operation remains the string in this case, except that the string is $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{red}1\color{black}(00)^+$ and the operation is $\color{red}1\color{black}?\color{red}1\color{black}:0$ makes 1. Since it must ends with `00`, it becomes a string ending with `0` and every pair of adjacent 1's has odd 0's in between, which is a case mentioned before that has no solution.

In conclusion, it has a solution if and only of at least one of the two following conditions is met:

• It ends with 1 but it is not 101.
• It has two adjacent 1's such that there are even 0's in between and the number of characters before the former 1 is even.

中文版本

英文题解里描述了做本题的一种思路，以及证明。

如果要直接写做法的话，是下面这样：

假设字符串下标从 $1$ 开始编号。

首先判断是否存在 $i,j$ 使得 $i$ 是奇数，$j$ 是偶数，$s_i$ 和 $s_j$ 都是 1，且这两个字符中间都是 0。

• 如果是，那么先把中间的 0 和 $s_j$ 写成 (0?0:0?0:.....:1)，表达式的值为 1（一定有偶数个 0），然后分三种情况：

  • 如果 $i=1$，那么就直接把 $s_j$ 后面的部分变成一个数，最后变成 (1?1:*) 是 1。

  • 否则考虑把 $s$ 的第 $1\sim i-2$ 位变成一个数，并计算出这个值。

    • 如果值为 0 那么有 ((0?*:1)?1:*) 等于 1。
    • 如果值为 1 那么有 (1?(*?1:1):*) 等于 1。

• 否则，判断是否满足字符串末尾是 1 且本身不等于 101：

  • 如果是，那么字符串一定以 0 或 10 开头，于是第一位或前三位操作后一定是 0，然后留下开头的 0 和结尾的 1，把中间的部分变成一个数，最后 (0?*:1) 结果一定是 1。
  • 否则，无解。

此外，还有一种比较特别的解法：

可以发现构造的过程中需要用到不超过两层括号（不算整个表达式最外面一层）。所以如果你要是猜到了这一点可以直接使用动态规划从右到左扫这个字符串，记录每一层栈中的内容。最多三层栈，每层栈最多两个比特，一共 $6^3+6^2+6=258$ 种状态。大概也能过。

不知道有没有什么奇怪的乱搞可以搜过去。不过我还是欢迎吧。

引言

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

于是我翻出了这个压箱底的 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.

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