【泛做】构造题选做 · 1

从网课和 uoj 群里的课件扒出来的构造题,都挺(不)好(会)的(做)。

1 神秘的题目

设 $f_A$ 表示 $A$ 的本质不同子串个数
给出 $x, y$,要求构造出两个字符串 $A, B$
满足:
$f_A = x , f_B = y , f_{A+B} = x + y$

$x, y ≤ 5000$


考虑 $x$ 个 $a$,$y$ 个 $a$ ,然后拼起来就好……

2 CF743C

给出 n,构造出 x, y, z,满足:

无解输出 −1
$n ≤ 10^4$


考虑通分(分时裂项),即

然后就做完了。

注意1要特判。

3 CF359B

给出 $n, k , 2k ≤ n$,构造出 $2n$ 的一个排列,满足:

$n ≤ 50000$


寄几想了一种构造,就是$a_{i+1} = a_i+k,~i=2p,~p \in \mathbb{N+}$,然后随便两次交换两项就好了。然而并不对,因为这样构造出的结果并不合法;于是遂决定改成$a_{i+1} = a_i+2k,~i=2p,~p \in \mathbb{N+}$,但也不对,单次交换的步长太长了,是$4k$。于是我又想能否有什么诡异的交换方法可以补救回来$2k$……失败了qaq

然而其实很简单,我们只要把步长控制为$1$就一定能凑出来。所以一开始先令$a_i=a_{i+1}+1$这种感觉,然后交换$k$次即可。

$\color{violet}{4~ \rm{CF}\it{512E}}$

对于一个正 n 边形,可以用 n − 3 条边分成 n − 2 个三角形
给出两种划分,你需要进行若干次操作把第一种划分变成第二种划分
每次操作选择一个四边形删去它的对角线,连另外一条对角线
n ≤ 1000,操作次数不超过 20000


开始掉线……

其实主要思想就是酱油瓶状态替换,把起始状态 $s$ 变成对角线都从 $1$ 出发的状态 $p$,再从 $p$ 出发变成终态 $t$。

具体操作好像是

别想了,掉线了怎么可能还会有?

$5$ 神秘的题目

给出一棵树,定义一个点的邻居集合为到它距离 $\leq 2$ 的所有点。

给出所有点的邻居集合,还原原树。

$n\leq 1,000$

考虑一个结论,如果两个点的邻居集合交集大小为 $2$, 那么交集中的点一定有连边。($\rm bitset$ 做到 $\frac{n^3}{w}$)

于是就可以先把 非叶子节点 两两之间的连边求出来

然后考虑如何求出叶子。发现叶子有个性质,就是叶子到某些非叶节点的距离一定 $=$ 与之相邻的非叶节点到某些非叶节点的距离 $+1$。所以就可以再把离每个非叶节点距离为 $1$ 的非叶节点求出来,称这个点集为旁边集合。那么如果叶子 $u$ 的邻居集合与非叶节点 $v$ 的旁边集合相同,那么 $u$ 就一定挂在 $v$ 上。

$6$ AT3877

给定 $\rm X,Y$, 给出 $[d_{i,j}]$ 表示当 $\mathrm X=i,\mathrm Y=j$ 时,$\rm S$ 到 $\rm T$ 的最短路。

构造这张图,使之点数 $<300$,无自环和重边,每条边的权值 $\leq 100$, 权值可以是数也可以是 $\rm X,Y$,并给出 $\rm S,T$ 。

设 $g_{i,j}$ 表示从 $\rm S$ 到 $\rm T$ ,经过了包含 $i$ 条 $\rm X$ 边, $j$ 条 $\rm Y$ 边的路径,其它边的边权最小和。

那么发现这东西可以这么转移出 $[d_{i,j}]$来

然后可以得到松弛条件

移项可以得到

于是考虑求出 $g $ ,之后反推出 $[d_{i,j}]’$ 观察是否吻合。吻合则考虑根据经过的 $\rm X,Y$ 连边即可。

$7$ ARC 095F

给定一棵树 $\rm T$, 要求构造一个排列 $p$ .

对于每一个 $p_i$ ,找到最大的 $j$ 使得 $p_j<p_i$,然后在 $i,j$ 间连边。

问是否可以构造出与 $\rm T$ 同构的树。

如果可以,则给出字典序最小的排列。

$n\leq 100,000$

反向考虑,观察对于一个排列生成的树。按照排列的权值升序操作,维护最靠右的位置 $mxp$ 即可。

然后发现由于一个排列不可能同时有两个最大值,这样生成的树一定会是一根长链周围分散着单点。

于是考虑把直径抽出来,对上面的点扫一遍。遇到有挂在上面的肯定考虑从小到大放在前面,然后就没有然后了。

可能实现还不太会,要再想想。

$8$ 小题整理

8.1 覆盖

平面上给定 $n$ 个点,每个点可以覆盖 $\frac{1}{4}$ 的平面,求最少需要多少个点才能覆盖所有点


orz我和ouuuyuuu一开始觉得题很傻,最多四个,结果发现原来最多两个就可以,然后发现我们很傻。。

找某一维坐标最大/最小的两个点,再判一下是不是只需要一个点就可以满足,就做完了。

8.2 CF477B

有 $n$ 个集合,彼此交集为空。

每个集合有 $4$ 个元素,两两之间均有 $\gcd = k$

求 $4n$ 个数中最大值的最小值

$1\leq n\leq 10000$

发现可以同除以 $k$ ,于是就变成两两互质了,于是 $4$ 个数中至多 $1$ 个偶数。

同时发现一个鬼能发现的性质,就是相邻两个奇数一定互质,那么就构造

可知它们互质。然后就没了。

$9$ CF 527D

每个元素有一个 $a_i$ 一个 $b_i$ .

求一个最大的点集使得 $\forall p,q\in \mathrm{S},\quad |a_p-a_q|\geq b_p+b_q$

$n\leq 200,000$

我丢,其实就是把每个元素看做 $(a_i-b_i,a_i+b_i)$ 这么一段区间,然后求的就是最长不相交的区间个数。

然后就没了……就没了……

$10$ ARC 084D

求出 $K$ 的倍数中,各位数字的和最小的那个数字的数字和。

$K \leq 100,000$

考虑从 $i$ 到 $i+1$ 连一条长度为 $1$ 的边,$i$ 到 $10\cdot i$ 连长度为 $0$ 的边。然后按照$\bmod k$ 的余数建边,最后就是 $1\to 0$ 的最短路。

$11$ 神秘的题目

给出一张 $n \cdot m$ 的网格图,曼哈顿距离为 $2$ 或 $3$ 的点之间连一条边,构造出一条哈密尔顿回路。

可能无解。哈密尔顿回路:经过每个点恰一次。

发现可以走法可以是棋盘染色,即黑白相间染色,先走完黑色再走完白色。

发现只有 $n=2,m=2$ 时无解。当 $\min(n,m)=1$ 时,考虑 $(1,2),(1,3),(2,4),(2,5)$ 都必须连(保证有回路),剩下的瞎构造即可。

$12$ CF 468A

用 $1\sim n$ 的所有数凑出 $24$,输出方案。

每个数都要用,只能用 +-× 三种运算。 $n\leq 100,000$

发现 $n\leq 3$ 显然不行。

然后 $n=4$ 的时候阶乘即可,$n=5$ 的时候发现可以 $5\times 3+4\times 2+1$ 这么算。

然后考虑 $n>5$,那么 $n$ 一定可以由 $n-2$ 推过来,因为只要乘上 $n-(n-1)$ 即可。发现这样总是可以构造出来合法解。

$13$ Loj #525

给定一个正整数 $k$,你需要寻找一个系数均为 $0$ 到 $k−1$ 之间的非零多项式 $f(x)$,满足对于任意整数 $x$ 均有 $f(x)≡0~(\bmod k)$

要求 $\deg(f)\leq 60000$

$k\leq 30000$
首先发现只要对 $0\sim k-1$ 成立那么就满足条件。 然后就变成傻题了,分治FFT!分治FFT!

然而分治FFT会T。不妨令 $q\geq \varphi(k)$,则由于扩展欧拉定理有:

那么如果令 $v=q+\varphi(k)$,就会有

然后就构造第 $\varphi(k)$ 项系数为 $k-1$,第 $2\cdot \varphi(k)$ 项系数为 $1$ 即可。