【泛做】构造题选做 · 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$

考虑如果给定一个排列,如何通过这种方式生成一棵树。那肯定是按照权值从小到大枚举每个权值所在的位置,每次在 $\max_right$ 和枚举的 $i$ 之间连边,并更新 $\max_right$。

可以发现,由于给定的是排列,局部最大值唯一,那么只会出现「非局部最大值向局部最大值连边」和「上一个版本的局部最大值和当前局部最大值连边」两种连边方式。所以不难看出最后的树的形态就是一个一阶毛毛虫——直径旁边挂着一堆点,每个点与直径的距离均为 $1$ 。所以是否合法求一下直径然后check即可。

考虑如何构造。发现只要求同构,那么肯定是从 $1$ 开始重新编号。对于每个直径上的 $x$,设与其相连且不在直径上的点的个数为 $\deg_x$,迄今为止一共有 $s$ 个点已经编完号了,那么只要让 $x=s+\deg_x+1$,剩下的点依次赋值为 $s+1,s+2,s+3\cdots s+\deg_x$ 就完了。可以知道这样一定是最优的方案。

从直径两端分别处理一下取个字典序最小即可。复杂度 $O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int dfs(int u, int faa){
int ret = u, s ;
fa[u] = faa, dep[u] = dep[faa] + 1 ;
for (int k = head[u] ; k ; k = next(k)){
if (to(k) != faa){
s = dfs(to(k), u) ;
if (dep[ret] < dep[s]) ret = s ;
}
}
return ret ;
}
int main(){
cin >> n ;
int rt1, rt2, num, u, v ;
for (int i = 1 ; i < n ; ++ i)
scanf("%d%d", &u, &v), add(u, v) ;
rt1 = dfs(1, 0) ; fa[rt1] = 0 ;
dep[rt1] = 0 ; rt2 = dfs(rt1, 0) ;
//cout << rt1 << " " << rt2 << endl ;
for ( ; rt2 ; rt2 = fa[rt2])
vis[rt2] = 1, d[++ tot] = rt2 ;
//cout << tot << endl ;
for (int i = 1 ; i <= n ; ++ i){
if (vis[i]) continue ; bool ans = 0 ;
for (int k = head[i] ; k ; k = next(k))
if (vis[to(k)]) { deg[to(k)] ++, ans = 1 ; break ; }
if (!ans) return puts("-1"), 0 ;
}
num = 0 ;
for (int i = 1 ; i <= tot ; ++ i){
for (int j = 1 ; j <= deg[d[i]] ; ++ j)
p[num + j] = num + j + 1 ;
p[num + deg[d[i]] + 1] = num + 1 ; num += deg[d[i]] + 1 ;
}
num = 0 ;
for (int i = tot ; i >= 1 ; -- i){
for (int j = 1 ; j <= deg[d[i]] ; ++ j)
q[num + j] = num + j + 1 ;
q[num + deg[d[i]] + 1] = num + 1 ; num += deg[d[i]] + 1 ;
}
for (int i = 1 ; i <= n ; ++ i)
if (p[i] != q[i]){
if (p[i] < q[i]){
for (int j = 1 ; j <= n ; ++ j)
printf("%d ", p[j]) ; puts("") ;
return 0 ;
}
else {
for (int j = 1 ; j <= n ; ++ j)
printf("%d ", q[j]) ; puts("") ;
return 0 ;
}
}
for (int j = 1 ; j <= n ; ++ j)
printf("%d ", p[j]) ; puts("") ;
return 0 ;
}

$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$ 即可。