LCA智慧构造_专题_LCA

LCA 智慧构造

CF1762D GCD Queries

这是一道交互题，$t$ 组数据。

有一个 $0\sim n-1$ 的排列 $p$。你可以进行以下询问最多 $2n$ 次：

• ? i j：询问 $p_i$ 和 $p_j$ 两个元素，交互器会返回两个元素的 $\gcd$。

询问以后，你需要给出两个下标 $x,y$（可以相等），满足 $p_x=0$ 或 $p_y=0$，格式为 ! x y，如果答案正确，交互器会返回 $1$，否则返回 $-1$。

$\sum n\le2\times 10^4,1\le t\le 10^4$。

一个思路是每次询问全局，删掉非倍数，这样第一次只要不随到 $1$ 就可以，复杂度是等比数列求和。

但是没什么好的解决方案。

考虑 $(a,x),(a,y)$，若 $u=v$，则 $a\ne 0$，若 $u<v$，则 $x\ne 0$，两次排掉一个数。

#538. 「LibreOJ NOIP Round #1」数列递推

给定 $a_0,a_1,k>0$，递推 $a_i=ka_{i-1}+a_{i-2}$，每次给定一个下标集合问下标集合里值最大的和值最小的是谁。

$|a_0|,|a_1|\le 10^7,\sum|S|\le 10^6$。

一些基本的观察：$a_i,a_{i+1}$ 如果同号，那么之后就单调了。

我们考虑前面异号这部分，需要满足 $|a_{i-2}|>k|a_{i-1}|$，然后 $|a_i|=|a_{i-2}|-k|a_{i-1}|$，不难看出如果要一直满足前一个不等式，后面的式子最多持续 $\log$ 轮。

所以我们的流程是先算 $\log$ 轮等它单调，再算 $\log$ 轮等它绝对值超越之前的绝对值。

实现上只需要算到值域爆了停即可。

fib 模意义下循环节长度是 O(p)

证明：考虑列出矩阵 $A=\begin{bmatrix}0&1\\1&1\end{bmatrix}$，这个东西实质上满足 $A^k=\begin{bmatrix}f_{k}&f_{k+1}\\f_{k+1}&f_{k+2}\end{bmatrix}$。

由于它的行列式是 $-1$，我们可以得到 $f_kf_{k+2}-f_{k+1}^2=\pm 1$，联立 $f_{k+2}=f_{k+1}+f_{k}$ 之后这个方程只有一个自由元，所以只有 $O(p)$ 种取值。

Least Annoying Constructive Problem QOJ - 5528

有一个完全图，你需要把边集重排成一个环，使得每个长为 $n-1$ 的子段都是一个生成树。

APIO 听过这个题，但是没补。

尝试用一种好的方式理解这个构造。

考虑把边集分块，只需考虑相邻块之间的衔接。

每块如何构造？由于我们要把边集划分，最简单的方法就是找一个边集然后每次循环移位。

由于我们要循环移位，所以不能有两条跨度相同的边，否则在旋转的过程中两边会重复，那我们采用经典的 $+1,-2,+3,-4,\cdots$，画出来长这样：


衔接也是非常容易的，每次把平行的边换成旋转后的。

这样做足以解决序列了，但是环上会出一点点问题。

$n$ 为奇数的时候记得每组边相邻的和跨一个的加的顺序要固定，否则环上衔接的时候对不上。

偶数的时候则修不了，但我们可以利用奇数来做。

把一个点放到中间，外面跑 $\binom {n-1}2$ 的奇数解，然后每 $\frac n 2$ 条边就插入一条中间向边上的边。

CF468A 24 Game

你有一个整数序列，包括 $n$ 个整数 $1\sim n$。你每次可以从其中拿出两个数 $a,b$，将这两个数从序列中删除，并将 $a+b$、$a-b$ 或 $a\times b$ 放入这个序列。

经过 $n-1$ 次操作后，序列中只会剩下一个数，若这个数可能为 $24$，输出 YES 与构造方案，否则，输出 NO。

构造题要分把握得住还是不能把握得住，后者要想方设法浪费一些解，归纳到小的情况。

显然本题可以 $i-(i-1)$ 得到 $1$，然后乘上 $24$ 得到 $24$，所以 $i$ 可以归纳到 $i-2$ 的情况。

发现 $4,5$ 都有解，解决了。

P6892 [ICPC2014 WF] Baggage

有一无穷长的流水线 $a$，初始时 $\forall i\le0\text{ 和 } i>2n ,a_i=0$。否则，若 $i$ 为奇数，则 $a_i=2$；若 $i$ 为偶数，则 $a_i=1$。也就是说，$a_i=2$ 和 $a_i=1$ 是交替出现的。

现需要进行若干次 如下 操作，使得 $a$ 中的所有 非零元素 为 连续 的一段且所有的 $1$ 均在 $2$ 前面。

选择两个位置 $p$ 和 $q$，满足 $a_p\ne0,a_{p+1}\ne0$ 且 $a_q=a_{q+1}=0$，将 $a_q$ 设为 $a_p$，$a_{q+1}$ 设为 $a_{p+1}$，并且将 $a_p$ 和 $a_{p+1}$ 均设为 $0$。输出时将此操作表示为 p to q（$p$ 和 $q$ 是具体的值）。

最小化操作步数，并输出操作序列，出题人将用 $\text{Special Judge}$ 来评判您的答案的正确性。

$n\le 105$。

经典归纳好题，但是感觉这个构造很难想。

考虑把一个合法方案在前面加上 21 后面加上 21，考虑把它变成 11 和 22。

有点困难，不妨扩大为 2121，变成 1111 和 2222。

这个是能做的，原地做需要两次交换：

$$2\underline{12}1\cdots21\underline{21}\\\underline{22}11\cdots2\underline{11}2$$

但是六次还是太多了，有一个很神秘的构造。

将空位视为 $3$，我们要把 $332121[\cdots]2121$ 排序，变成 $1\cdots2\cdots33$。

$$\underline{33}2121[\cdots]2\underline{12}1\\1221\underline{21}[\cdots]2\underline{33}1\\1221[33\cdots]2211$$

然后等待内部完成排序后将前面的 $22$ 填进内部末尾的 $33$，再用后面的 $11$ 填进前面 $22$ 产生的 $33$。

这样我们就完成了 $4$ 次操作 $n\to n-4$，考虑证明答案中含 $n$ 的项就是 $n$。

考虑忽略空格后 $21$ 这个 pair 的数量，我们的目标是消为 $0$，初始有 $n$ 个，每次显然至多减少一个。

由于 $n\ge 3$ 但 $3$ 的时候不能仅借助 $33$ 复原，我们需要爆搜出 $3,4,5,6,7$ 的答案。

LOJ#540. 「LibreOJ NOIP Round #1」游戏

给定 $m$，构造一个图使得三元环个数等于 $m$，你需要保证点数 $\le 500$。

$m\le 2\times1 0^6$。

第一反应是用若干个完全图去凑，每个完全图贡献是 $\binom n 3$。

但是这样 $i,i+1$ 之间的鸿沟是 $i^2$ 级别的，新的规模是 $m^{2/3}$。

只会递归 $\log\log$ 次，其实这样就可以了。

如果想要进一步加强，我们可以用另一个点连向这些点，连 $d$ 的贡献是 $\binom d2$，减小了 gap，减小了常数。

题

给定 $m$，构造一个图使得独立集个数等于 $m$，你需要保证点数 $\le \lceil\log_2 m\rceil+1$。

$m\le 10^{18}$。

当然这个题无法 check，所以是一个思考实验。

考虑如果一个图的独立集个数是 $x$，那么使用 $c$ 个点每个点向那些点连一个菊花，则新的独立集个数变为 $2^c-1+x$。

所以我们每次可以把独立集个数加上 $2^i-1$，枚举个数然后判断即可。