非传统题型选讲

本处的非传统题，指构造、交互、提答、通信等这一类较传统问题不同，解法不普遍的题型。

本文将会讲解一些这样的题，并给出一些题的通用方法。

配套题单。

知识点

先复习一下简单的知识点，然后进入我们的讲题。

鸽巢原理

将 $n$ 个物品分为 $k$ 份，最大的一份至少为 $\lceil \frac{n}{k}\rceil$ 个，最少的一份至多有 $\lfloor \frac{n}{k}\rfloor$ 个。

矩阵染色

对某一个 $k$ ，将矩阵中的每个位置 $(x,y)$ 染上第 $x+y\ \bmod\ k$ ，使得相连的 $k$ 个格子颜色不同。

DFS 树

给定一个无向图或有向图，用 DFS 找出图中的一棵生成树。

重要的事实：无向图的非树边一定是后向边。

随机化

随机永远会是最后的手段，有的题目使用随机是有一定作用的。

分块

是的没错，分块永远是适配于所有题目的。

常见的方向还有二进制分解，二分，分治，递归，限于篇幅不再一一赘述。

这些都是解决这一类非传统题型的利器。

例题

2020 美团杯最长公共子序列

题目描述

这是一道水题。

显然如果我们选择询问 $(i,j)$ ，若 $i$ 的位置在 $j$ 之前，询问则会返回 $2$ ，否则则会返回 $1$ 。

那么我们询问一组 $(i,j)$ ，就可以得到 $i$ 与 $j$ 的相对关系，做一遍快速排序即可。

参考代码

IOI 2014 Game

题目描述

要想在前 $r-1$ 个问题中不让对手猜出答案，当且仅当最后他问的一条边如果在图中是桥边。

由于最后一个回答没有作用，所以我们假设最后一个问题的答案为真，即整张图为连通图。

然而对手问的边不一定，所以我们要最大化桥边数量，哪种图的桥边最多呢？树！

我们随便取一个点 $n$ ，显然对手会问 $n-1$ 次与 $n$ 有关的信息，考虑在前 $n-2$ 次回答假，在最后一次回答真。

那么，总的策略就是，对于询问 $(u,v)$ ，其中 $u<v$ ，如果这是关于点 $v$ 的第 $v-1$ 次询问，回答真，否则回答假。

参考代码

JOISC 2020 Legendary Dango Maker

题目描述

提交答案题有大量的解法，包括但不限于找性质、贪心、爆搜等各种奇淫技巧，其中较为常见的是随机化算法。~~所以玩提答可以合法浪费时间。~~

对于这道题，我们先转换模型，找出所有的美丽串，将美丽串作为点，相互冲突的美丽串之间连边，那么问题直接转化为一般图最大独立集问题，直接模拟退火即可。

这里阐述一下模拟退火的原理：

考虑我们现在有一个解，对这个解做出随机的修改，如果这个解比我们的最优解要优秀，那么我们一定保留，如果这个解要屑一些，我们以一定概率保留。

实现上，设置常数 $k$ ，变化量 $\Delta$ ，终点 $E$ ，维护初温 $T$ ，每次作出修改时，设解的变化量为 $\Delta f$ ， $T=T\times \Delta$ ，而上述的一定概率就等于 $e^{\frac{-\Delta f}{kT}}$ 。

而模拟退火的麻烦点就在这里，上述设置的对程序的运行有着大量的影响，所以我们需要调参。

套用到一般图最大独立集问题中，我们先预先求出一个独立集，然后我们考虑修改，每次尝试将一个点加入并求合法独立集，最后比较这个解与我们的最优解即可。

参考提交

CF R 562 Xor Permutations

题目描述

~~你看这个构造，真是太逊了！才乱搞几下就 A 了。~~

方便起见，设 $n=2^k$ 。

先证明，有解当且仅当 $\oplus^{n}_{i=1} a_i=0$ ，证明如下：

由 $p_i\oplus q_i=a_i$ ，得 $p_1\oplus q_1\oplus p_2\oplus q_2\oplus\ldots\oplus p_{n}\oplus q_{n}=\oplus^{n}_{i=1} a_i$ 。
因为异或具有交换律与结合律，得 $\oplus^{n}_{i=1}p_i\oplus \oplus^n_{i=1}q_i=\oplus^n_{i=1}a_i$ 。
又因为 $p,q$ 均为排列，所以 $\oplus^n_{i=1}p_i=\oplus^{n}_{i=1}q_i=0$ 。
所以有解当且仅当 $\oplus^n_{i=1}a_i=0$ 。Q.E.D.

接下来考虑如何构造，考虑调整算法：

图源自邓明扬的论文，在参考资料中有提到。

考虑将每个 $a_i$ 与一个 $0\sim n-1$ 之间的常数匹配，匹配到 $a_i$ 的作为 $p_i$ ，由于 $p_i\oplus q_i=a_i$ ，所以 $q_i=a_i\oplus p_i$ 。

每次我们随机一个未匹配的 $p_i$ ，检验是否有能直接与 $p_i$ 匹配的 $a_i$ ，如有，直接匹配，如果没有，随机选取一个未匹配的 $a_i$ ，断掉异或值等于 $p_i\oplus a_i$ 的匹配，切换成 $a_i$ 与 $p_i$ 的匹配。

笔者在测试自己的一份代码时，发现这个乱搞相当得快，目前也无法证明这个算法的时间复杂度、正确性（邓明扬，IOI2021 AK 选手，都证明不出这玩意，我何苦为难自己？）。

参考代码

CGR 12 C Errich-Tac-Toe

题目描述

这玩意与传统的井字棋规则相比，少了一个对角线，且只要连续三个一样就能赢。

在构造题目中，遇连续多少个就要想到染色，类似的，在这题中，对于格子 $(x,y)$ ，按 $(x+y)\bmod3$ 分类，显然为了平局，只需要将连续的三个格子没有相同颜色即可。

类似的，我们有如下 $6$ 种方法来达成目的：

第一类格子全改为 X，第二类格子全改为 O。
第一类格子全改为 X，第三类格子全改为 O。
第二类格子全改为 X，第一类格子全改为 O。
第二类格子全改为 X，第三类格子全改为 O。
第三类格子全改为 X，第一类格子全改为 O。
第三类格子全改为 X，第二类格子全改为 O。

然而这还有个操作限制 $\lfloor\frac{k}{3}\rfloor$ 。但是我们发现这六种方法的操作数总和是 $2\times k$ ，依据鸽巢原理，最少的一份最多有 $\lfloor \frac{k}{3}\rfloor$ ，选取最少操作步数的一种方案即可通过本题。

参考代码

WF 2014 Baggage

题目描述

As a resault,nobady solved this problem during the WF 2014:)

首先这个题有别于我们之前所讲的构造，他要求最优解，然而我们连最优解的答案是什么都不知道，而且这题好像也没别的什么性质。

考虑先爆搜抑或是手玩，于是你发现一个关键点，这个最优解在一定的小范围内是 $n$ ，其实我们可以估计出一个答案的下界：

设相邻的两个字母不相同的对数为 $d$ ，那么一开始 $d=2\times n-1$ ，目标状态 $d=1$ ，这之间的变化量为 $2\times n-2$ ，每一次操作最多使得 $d$ 减掉 $2$ ，但第一次操作无论如何 $d$ 都只会减掉 $1$ 。
所以答案的下界为 $1+\lceil\frac{2\times n-3}{2}\rceil=1+n-1=n$ 。

注意观察爆搜出的解，当 $n>3$ 时，在结束时所有的货物均在 $-1\sim 2\times n -2$ 处，这启示我们特判 $n=3$ 的情况，处理剩下的情况，将大问题规约到子问题。

这种方式是这样的：

__BABABABA…BABABA
ABBABABABA…BAB__A
ABBA__BABA…BABBAA

此刻我们发现，中间的 __BABA…BA 是一个子问题，递归下去做。

ABBAAAA…BBB__BBAA
A__AAAA…BBBBBBBAA
AAAAAAA…BBBBBBB__

至此，我们便完成了构造。

具体实现方向是，将 $n=3,4,5,6,7$ 的情况进行打表，按上述方式递归即可。

参考代码

CF R 649 Ehab's Last Corollary

题目描述

考虑建立出 DFS 树。

因为这是一张无向图，所以他的非树边一定是后向边，那么在 DFS 的过程中，如果遇到了非树边 $(u,v)$ ，满足 $|dep_u-dep_v|< k$ 时，从 $u$ 到 $v$ 的树上简单路径上的点可以构成一个大小不超过 $k$ 的简单环。

接下来考虑找不到简单环的情况，方便起见，设 $lim=\lceil\frac{k}{2}\rceil$ 。

若 $m=n-1$ ，也就是原图是一棵树，考虑将节点按深度奇偶性分类，显然在同一类的点是一个独立集，而我们分成的这两个集合总大小为 $n$ ，依据鸽巢原理，较大的那一份至少为 $\lceil\frac{n}{2}\rceil\ge lim$ 个，直接对这一份乱取 $lim$ 个即可。
否则，说明这张图上不存在一条非树边满足 $|dep_u-dep_v|<k$ ，也就是说，对于距离在 $[2,k)$ 之间的点对，不存在有边相连，那么，我们取深度最深的那个点，他的深度一定 $\ge k$ ，取他与他的 $2,4,\ldots,2\times lim-2$ 级祖先作为独立集一定是满足条件的。

参考代码

CF R 628 Ehab's Last Theorem

题目描述

~~这题和上题是同一个出题人~~

为了下面方便讨论，设 $lim=\lceil\sqrt{n}\rceil$ 。

建出 DFS 树，同上题，如果在遍历中出现了后向边 $(u,v)$ 且 $|dep_u-dep_v|\ge lim-1$ 时，自 $u$ 到 $v$ 的树上简单路径上的点可以构成一个简单环。

如果没有环，按照 $dep_u\bmod (lim-1)$ 的值来分类，对于一对在同一类的，呈父子关系的点，他们的树上简单路径距离一定 $\ge lim-1$ ，而我们在上面已经确定，对于一对这样的点，没有后向边将他们相连，所以同一类的点构成了一个独立集。

依据鸽巢原理，最大的一类里至少包含 $\lceil\frac{n}{lim-1}\rceil\ge lim$ 个，所以选取最大的一类中的任意 $lim$ 个点就可以满足条件。

参考代码

CF R 684 Graph Subset Problem

题目描述

先考虑至少有 $k$ 个邻居的子集怎么做，考虑将 $deg<k$ 的节点塞到一个队列中，每次删点并同时处理相邻点的 $deg$ ，当队列为空时，剩下的点就是一个满足条件的子集。

如果上面的子集为空，我们就要考虑判断团，实际上，在做上述的过程时，如果我们遇到一个节点 $u$ ，满足 $deg_u=k-1$ ，就可以考虑他与他的邻居为一个团，判定方法十分简单，直接暴力枚举 $\frac {k(k-1)} 2$ 条边，使用 set 或是哈希表判断一下就行了。

参考代码

SDOI 2019 热闹的聚会与尴尬的聚会

题目描述

我们先分析这个离了谱的条件： $\lfloor\frac{n}{p+1}\rfloor\le q$ 并且 $\lfloor\frac n{q+1}\rfloor\le p$ ，推导过程如下：

\lfloor\frac{n}{p+1}\rfloor\le q\\ \lceil\frac {n+1}{p+1}-1\rceil\le q\\ \lceil\frac {n-p-1+1}{p+1}\rceil\le q\\ \frac{n-p}{p+1}\le q\\ n-p\le q(p+1)\\ n\le pq+q+p\\ n<pq+q+p+1\\ (p+1)(q+1)>n

那么，因为题目要求构造的两个集合是独立的，所以分别最大化 $p,q$ 即可。

最大化 $p$ 非常简单，将节点按度数排序，每次尝试删掉度数最小的节点 $u$ 使答案变大，直到图被删空为止，记录所有时刻里 $p$ 最大的一刻作为答案。

最大化 $q$ 呢？显然这是一个一般图最大独立集问题，wjr 并不想在年纪轻轻的时候就挑战图灵奖，所以这里只有用模拟退火才能解决了。

问题是否就止步于此呢？我们上述的做法完全没有用到上述两个问题的关联，实际上，在上面的三道题中，都出现了图上两个看似毫不相干的问题的构造，而且这两个构造是有一定关联性的，网上有人称这些问题是“图上二选一构造问题“（见参考资料）。

所以说，我们设计这样一个，由最大化 $p$ 的做法修改而来的算法：

每次选出度数最小的 $u$ 。
将 $u$ 加入第二个点集。
删除 $u$ 与 $u$ 的邻居。

同样的，记录 $p$ 最大的时刻作为第一个点集，而在算法最后我们也得到了第二个点集。

正确性呢？我们设第二个点集为 $E$ ，显然对于每个度数最小的 $u$ ， $u\in E$ ，而 $p=\max\{deg_u\}$ ，也就是说，每次删去的点数最多有 $p+1$ 个，共删了 $q$ 次，所以 $(p+1)q\ge n$ ，所以满足条件 $(p+1)(q+1)>n$ 。

至此，问题得到解决。

参考代码

IOI 2019 Spilt

题目描述

三个点集的大小没有关系，我们不妨假设 $a\le b\le c$ ，这样方便构造。

容易发现我们只需要分别构造大小为 $a$ 和 $b$ 的点集即可，因为如果构造大小为 $c$ 的点集，其必然可以删掉一些点，转化为大小为 $b$ 的点集。

算法一： $m=n-1$

从部分分出发，我们考虑如何处理树的情况，此时选出的两个联通子集 $A,B$ 均为子树，所以枚举每一条边，判断这条边左右两边是否存在一个大小不小于 $a$ 的子树和一个大小不小于 $b$ 的子树，分别构造即可。

但是，我们仔细分析这题的性质，如果我们取出这棵树的重心 $C$ ，那么有解的条件为，将 $C$ 提为根后，至少有一棵 $C$ 的儿子子树大小 $\ge a$ 。

如果全部 $<a$ 的话，集合 $A$ 与集合 $B$ 必然有交且交于重心。

所以，我们从上述的儿子子树中选取 $a$ 个相邻的点，再选取重心与其他子树共 $b$ 个点，即可完成题目。

算法二：一般图

受算法一的启发，考虑建出 DFS 树，找到 DFS 树的重心 $C$ ，去掉 $C$ ，DFS 被划分成若干子树，设在 $C$ 上面的子树为 $T$ ，剩下的子树分别为 $S_1,S_2,\ldots,S_k$ 。

如果 $T$ 或某个 $S_i$ 的子树大小 $\ge a$ 的话，同算法一可以出解。
否则，考虑前文提到的无向图上 DFS 树的性质，发现在 $T$ $T$ 和 $S_i$ $S_{i}$ 之间可能有连边（后向边），在 $S_i$ $S_{i}$ 与 $S_j$ $S_{j}$ 之间不可能有连边（无横叉边）。
- 如果 $T$ 与所有相连的 $S_i$ 的大小总和 $< a$ ，那么一定无解，因为集合 $A,B$ 一定交于重心。
- 否则考虑处理一个集合 $X$ $X$ ，初始时 $X$ $X$ 里面包含 $T$ $T$ ，按任意顺序往 $X$ $X$ 里面添加与 $T$ $T$ 相连的子树 $S_i$ $S_{i}$ ，直到 $X$ $X$ 的大小 $\ge a$ $\geq a$ ，剩下的节点显然是足够构造出 $B$ $B$ 的，按如下方法构造 $A,B$ $A, B$ ：
  - 构造 $A$ ，先将 $T$ 加入 $A$ 中，找出 $X$ 中所有与 $T$ 相连的点 $u_i$ ，将 $u_i$ 加入 $A$ 后，如果仍然不够，考虑将每个 $S_i$ 里的其他点加入，从 $u_i$ 开始在子树中 DFS 即可。
  - 构造 $B$ ，显然重心 $C$ 是要加入的，然后把不在 $X$ 中的子树依次加入即可。

参考代码

CF R 614 Rin and The Unknown Flower

题目描述

算法一

我会暴力！问一次 C，问一次 H，剩下的都是 O！

费用 $1+1=2$ ，显然无法通过。

算法二

事实上问一次 C 是不是太过浪费了呢？我们问 CC，CO，CH 同样可以问出除了最后一个位置的 C，费用只有 $\frac 3 4$ 。

同样的，我们再来确定 O，为了最大化利用先前的询问，问 HO，OO 就可以问出除了第一个位置的所有的 O，费用共 $\frac 5 4$ 。

那么显然在第 $2$ 个到第 $n-1$ 个位置中，没有被问来的一定是 H，而第一个位置，如果没有问出来的话，显然有 O，H 两种可能，同理，对最后一个位置，如果没有问出来的话，显然有 C、H 两种可能，共 $2\times 2=4$ 种可能，询问 $3$ 个即可。

费用 $\frac 5 4+\frac 3{n^2}$ ，可以通过本题

……

……的 $n>4$ 部分。

笔者在写这一段中做了测试，只实现这个做法会 WA On Test 3，因为当 $n=4$ 时，总费用为 $\frac 5 4+\frac 3 {16}=1.4375>1.4$ 。

算法三

单独处理 $n=4$ 的情况。

同样的，先询问 CC、CO、CH、HO，如果有一个成功了，至多有两位没有确定，且前三位没确定的不可能有 C，至多 $6$ 种可能，费用为 $\frac 4 4+\frac 5 {16}=1.3125$ 。

如果上述均未成功，再询问 OO，如成功，有如下可能：

OOOO，显然可以直接输出。
OOO*，最后一位可能是 C 或 H，这是显然的。
OO**，第三位只可能是 H，最后一位可能是 C 或 H。

至多 $2$ 种可能，费用为 $\frac 5 4+\frac 1{16}=1.3125$ 。

如果上述均未成功，那么字符串一定形如 *HH*，第一位不可能是 C，最后一位不可能是 O，询问 HHH 就可以确定字符串，费用为 $\frac 5 4+\frac 1 9=1.3611$ 。

与算法二结合即可 AC。

参考代码

Technocup 2020 Elimination R3 Not Same

题目描述

下面，设答案矩阵为 $b$ 。

算法一

从 $1$ 到 $n$ 依次考虑每一列，假如现在考虑第 $i$ 列，按如下方法构造：

考虑之前的 $(n+1)\times (i-1)$ 的矩阵，如果某两行相同，设这两行分别为 $r_1,r_2$ ，我们使 $b_{r_1,i}=1$ ， $b_{r_2,i}=0$ ，剩下的 $a_i-1$ 个 $1$ 随便乱放。
如果没有相同的两行，直接将 $a_i$ 个 $1$ 随便乱放。

证明如下：

将相同的行放到一组，记录每个组内行的个数，得到一个可重集 $S$ ，初始时 $S=\{n+1\}$ ，结束状态 $S=\{1,1,\ldots,1\}$ ，共 $n+1$ 个 $1$ 。

我们对某两行操作的效果，其实相当于选出一个大于 $1$ 的元素 $x$ ，将其拆分成两个元素 $x_1,x_2$ ，再丢进集合内。

原集合最多可被操作 $n$ 次，所以必然可以被构造出来。

参考代码

算法二

因为列置换不影响答案，所以将 $a$ 从大到小排序。

对于每个 $a_i$ ，从第 $i$ 行开始放 $1$ ，一路往下放，放到底了就循环上去放。

证明如下：

若行 $i,j(i<j)$ 相同。

因为 $a_{i+1}\le n$ ，所以 $b_{i,i+1}=0$ ，又因为行 $i$ 与行 $j$ 相同，所以 $b_{j,i+1}=0$ ，所以 $a_{i+1}\le j-i-1$ 。

如果 $i+2\le j$ ，考虑第 $i+2$ 列。要么 $b_{i,i+2}=b_{j,i+2}=0$ ，要么 $b_{i,i+2}=b_{j,i+2}=1$ ，如果是后者，那么 $a_{i+2}\ge j-i+1$ ，又因为我们从大到小排了序， $a_{i+1}\ge a_{i+2}\ge j-i+1$ ，与前文不符，所以 $b_{i,i+2}=b_{j,i+2}=0$ ，所以 $a_{i+2}\le j-i-2$ 。

类似的，我们可得 $\forall k\in[1,j-i],a_{i+k}\le j-i-k$ ，当 $k=j-i$ 时， $a_{j}\le j-i-j+i=0$ ，与题意不符。

参考代码

CGR 8 Ski Accidents

题目描述

$\frac 4 7 n$ ，诡异的标点个数，我们不如思考一下，这个 $\frac 4 7 n$ 能启发我们什么， $1+2+4=7$ ？

我们考虑把节点分为三个集合 $A,B,C$ ，满足 $4|A|\ge 2|B|\ge |C|$ ，那么必然的是 $|C|\le \frac 4 7 n$ ，只要把 $C$ 删除了就满足条件了。

考虑怎样构造三个集合，我们按如下的构造方法：

$A$ 里面是所有入度为 $0$ 的点与所有入边来自 $C$ 的点。
$B$ 里面是至少有一条入边来自 $A$ 的点，且没有来自 $B$ 的入边。
$C$ 里面是至少有一条入边来自 $B$ 的点。

由于每个点的出度最多为 $2$ ，所以有 $4|A|\ge 2|B|\ge |C|$ 。

而删去 $C$ 后，唯一剩下的边是 $A\to B$ 之间的边，所以也是符合条件的。

因为原图是一个有向无环图，所以可以迅速完成划分。

参考代码

UR 5 怎样提高智商

题目描述

既然要求正确答案尽可能多，那么显然会有 $a_i=b_i=c_i=d_i$ 。

我们来 xjb 胡一个构造：因为第零题不存在，所以 $a_i=0$ ， $h_i$ 乱取，这显然四个都可以选，我们假设选了 A，那么第二题问什么比较好？A 有 $1$ 个？那第一题只能选 A 了；A 有 $0$ 个？那第一题可以选 B、C、D 三种选择，是不是要好一些。

以此类推，所有问题都形如 $c$ 有 $0$ 个，其中 $c$ 是随便一个字符，此时的答案总数为 $4\times 3^{n-1}$ ，可以证明这是最优的。

参考代码

UER 8 打雪仗

题目描述

算法一

我们的操作步数够多！我们直接让小 A 把整个序列发过来。

期望得分： $20$ 分。

算法二

考虑将原本的 $01$ 串三等分，那么必然有一段含小 B 需要的元素达到半数，我们让小 A 把这一段全丢过来。

那么剩下的两段，我们就让小 A 只把小 B 需要的元素丢过来。

那么，小 B 需要传送 $\frac 4 3 n$ 的信息，小 A 最多需要传送 $\frac 2 3 n+\frac 2 3 n=\frac 4 3 n$ 的信息，可过。

期望得分： $100$ 分。

cnyz's Blog