构造题经典套路

Arahc 11.0
  2022-10-12 08:00 2022-10-12 08:00 创建   2023-03-16 13:56:42 2023-03-16 13:56:42 更新      4.1k 字  20 分钟  

构造题虽然一般都非常需要思维，但是有些题目还是比较套路的。——不是指的完全就是套路，而是它们有类似的方法。如果能在遇到这个题的时候能快速发现并往这个方向靠的话，应该会有很好的做题效果。

本文的内容很大程度上参考了 2021 国家集训队论文。

鸽巢原理

很多构造题会有要求你构造权值不少于或不超过一个数字的方案。如果我们能找出若干个可行的方案，使得这些方案的权值和为定值，那么不妨考虑在这些方案里面选取最优的进行。

假设有 kk 个可行的构造方案，这些方案的权值和为 nn，则这些方案中权值和最小的方案的权值和 ≤⌊nk⌋\leq\left\lfloor\frac{n}{k}\right\rfloor，权值和最大的方案权值和 ≥⌈nk⌉\geq\left\lceil\frac{n}{k}\right\rceil。

CFgym102900B Mine Swap II

给定两个 n×mn\times m 的扫雷地图。你可以操作不超过 KK 次。每次操作可以把一个图的一个地雷改成空地或把空地改成地雷。

构造一种方案，令两个地图上空地的数字和相等（空地上的数字等于与其八联通的地雷个数）。

n,m≤1000,K≥5×105n,m\leq1000,K\geq 5\times10^5。

题解

注意到数字和实际上相当于相邻的地雷与空地的对数。这意味着：交换地图中每个格子的状态（地雷改成空地，空地改成地雷），数字和是不变的。

于是构造出两种不同的方案：

  1. 将地图 A 暴力修改为地图 B。
  2. 将地图 A 暴力修改为地图 B 的反图。

显然对于任意一个格子，其只会在这两个方案中的恰好一个方案中被修改。两种方案修改的格子数之和为 nmnm，选择代价较小的一种，根据鸽巢原理不难发现操作数符合条件。

CF1450C Errich-Tac-Toe

给定一个三子棋残局，已经放置了 kk 个棋子（棋子颜色为黑或白）。你需要反转不超过 ⌊k3⌋\left\lfloor\frac{k}{3}\right\rfloor 个棋子使得原局面变成平局。一个局面是平局当且仅当不存在横着或竖着的连续三个同色棋子。

n≤300n\leq 300。

题解

对地图三染色，即坐标 (i,j)(i,j) 的格子的颜色设置为 (i+j) mod 3(i+j)\bmod 3。

不难发现对于任意 xx，将 xx 颜色格子上的黑子改成白字，x+1x+1 颜色的格子上的白子改成黑子，就可以使原局面平局。而 xx 有三种颜色都可取。取代价最小的一种即可。

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
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
const int max_n=303;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
inline int reads(){
    char c=getchar();
    while(c!='.' && c!='X' && c!='O') c=getchar();
    if(c=='.') return -1;
    if(c=='X') return 0;
    return 1;
}
inline void print(int x){
    if(x==-1)putchar('.');
    if(x==0) putchar('X');
    if(x==1) putchar('O'); 
}

int n,a[max_n][max_n];

int c[3][2];

bool End;
#define File ""
signed main(){
    // #ifndef ONLINE_JUDGE
    // freopen(File ".in","r",stdin);
    // freopen(File ".out","w",stdout);
    // #endif
    for(int T=read();T;--T){
        n=read();
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                a[i][j]=reads();
                if(a[i][j]==-1) continue;
                ++c[(i+j)%3][a[i][j]];
            }
        int mnp=2,mnx=c[2][0]+c[0][1];
        for(int x=0;x<2;++x) if(c[x][0]+c[x+1][1]<mnx)
            mnx=c[x][0]+c[x+1][1],mnp=x;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) if(a[i][j]!=-1){
                if((i+j)%3==mnp && a[i][j]==0)
                    a[i][j]=1;
                if((i+j)%3==(mnp+1)%3 && a[i][j]==1)
                    a[i][j]=0;
            }
        for(int i=1;i<=n;++i,putchar('\n'))
            for(int j=1;j<=n;++j)
                print(a[i][j]);
    }
    return 0;
}

dfs 树

对于一个图上问题，建立 dfs 树往往是一个重要思路。dfs 树通常会在边定向、找出一些满足特定条件的集合上用到。

一般的构造题我们遇到的都是无向图。无向图的 dfs 树中非树边里只有反祖边一种边。这个性质在解题过程中非常有用。

一般情况下，优先考虑原图是一棵树的情况，可能会使解题更加轻松。

CF1364D Ehab’s Last Corollary

给定一个无向联通图和一个整数 kk，你需要找到如下两个中的任意一个：

  1. 一个大小为 ⌈k2⌉\left\lceil\frac{k}{2}\right\rceil 的独立集。
  2. 一个大小不超过 kk 的简单环。

3≤k≤n≤1053\leq k\leq n\leq 10^5。

题解

先判掉原图是树的情况——按照每个点深度的奇偶性把点集分成两个，取点数多的那个集合（如果多出来了就去掉若干个），不难发现这一定合法。下面我们考虑原图不是一棵树，也就是反祖边一定存在的情况。

跑出原图的一个 dfs 树，对于每个返祖边 (u,v)(u,v)，若 ∣depu−depv∣≤k\left|dep_u-dep_v\right|\leq k，则这条返祖边和两点在树上形成的路径共同构成了一个长度不超过 kk 的简单环。

若不存在，则说明 dfs 树的深度至少为 kk，且对于任意一对深度差在 [2,k)[2,k) 的点都没有反祖边连接。取深度最大的点和其 2,4,6,⋯ ,2⌈k2⌉−22,4,6,\cdots,2\left\lceil\frac{k}{2}\right\rceil-2 级祖先即可。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
const int max_n=200005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
struct graph{
    int ct,hd[max_n],to[max_n<<1],nx[max_n<<1];
    graph(){ct=1;}
    inline void add(int u,int v){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
    }
}e;
int cnt;
struct Edge{
    int u,v;
    Edge(int U=0,int V=0):u(U),v(V){}
}g[max_n];

int n,m,K;

bool vis[max_n];
int fa[max_n],dep[max_n];

inline void dfs(int u,int Fa=0){
    vis[u]=1;
    fa[u]=e.to[Fa];
    dep[u]=dep[fa[u]]+1;
    for(int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(i==Fa) continue;
        if(vis[v]){
            ++cnt;
            g[cnt]=Edge(u,v);
            continue;
        }
        dfs(v,i^1);
    }
}

vector<int> Cir,A[2];

bool End;
#define File ""
signed main(){
    // #ifndef ONLINE_JUDGE
    // freopen(File ".in","r",stdin);
    // freopen(File ".out","w",stdout);
    // #endif
    n=read(),m=read(),K=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        e.add(u,v),e.add(v,u);
    }
    dfs(1);
    for(int i=1;i<=cnt;++i){
        if(dep[g[i].u]<dep[g[i].v]) swap(g[i].u,g[i].v);
        int u=g[i].u,v=g[i].v;
        if(dep[u]-dep[v]<K){
            puts("2");
            while(u!=v){
                Cir.emplace_back(u);
                u=fa[u];
            }
            Cir.emplace_back(v);
            write(Cir.size()),putchar('\n');
            for(auto v:Cir) write(v),putchar(' ');
            return 0;
        }
    }
    puts("1");
    K=(K+1)>>1;
    if(m==n-1){
        for(int i=1;i<=n;++i)
            A[dep[i]&1].emplace_back(i);
        int op=(A[1].size()>A[0].size());
        for(int i=0,up=min((int)A[op].size(),K);i<up;++i)
            write(A[op][i]),putchar(' ');
        return 0;
    }
    int x=max_element(dep+1,dep+1+n)-dep;
    for(int i=0;i<(K<<1);++i,x=fa[x]) if(!(i&1))
        write(x),putchar(' ');
    return 0;
}

LOJ3176 景点划分

给定一个无向联通图和三个正整数 a,b,ca,b,c，满足 a+b+c=na+b+c=n，你需要将每个点划分为三个大小分别为 a,b,ca,b,c 的点集，使得其中至少有两个点集内部是联通的。或判定无解。

n≤105n\leq 10^5。

题解

设 a≤b≤ca\leq b\leq c，我们构造的联通集合为 A,B，另一个为 C。

优先考虑原图是树的情况，把重心拿出来判定是否有不小于 aa 的子树即可。因为若所有子树大小都比 aa 小，则 A,B 两个集合都需要覆盖到重心，这显然不合法。

然后推广到一般图，建立 dfs 树，找到 dfs 树的重心 xx。若 xx 本身就存在不小于 aa 的子树就可以直接做了，否则考虑利用返祖边。

设 xx 的父亲所在的子树为 TT，xx 的儿子对应的子树为 S1,S2,⋯S_1,S_2,\cdots，从小到大加入有反祖边的 SiS_i，直到 TT 和加入的 SiS_i 的总大小不少于 aa 即可。若全部加入则无解，若加入成功则和树的情况类似在剩下的点里扩展出一个 bb 即可，这个 bb 是一定能找到的。因为此时 aa 对应的的连通块大小不超过 2a2a，而 2a+b≤n2a+b\leq 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Begin;
const int max_n=200005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
struct graph{
    int ct,hd[max_n],to[max_n<<1],nx[max_n<<1];
    graph(){ct=1;}
    inline void add(int u,int v){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
    }
}e;
int cnt;
struct Edge{
    int u,v;
    Edge(int U=0,int V=0):u(U),v(V){}
}g[max_n];
bool isrf[max_n<<1];

int n,m,A,B,C;
struct Node{
    int x,id;
    Node(int X=0,int ID=0):x(X),id(ID){}
    bool operator < (const Node &b) const{
        Node a=*this;
        return a.x<b.x;
    }
}a[3];

int ans[max_n];

bool vis[max_n];
vector<int> son[max_n];
int sz[max_n],dep[max_n],fa[max_n],zx;

inline void dfs1(int u,int Fa=0){
    vis[u]=1;
    fa[u]=e.to[Fa],dep[u]=dep[fa[u]]+1,sz[u]=1;
    for(int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(i==Fa) continue;
        if(vis[v]){
            ++cnt;
            g[cnt]=Edge(u,v);
            isrf[i]=isrf[i^1]=1;
            continue;
        }
        son[u].emplace_back(v);
        dfs1(v,i^1);
        sz[u]+=sz[v];
    }
    if(sz[u]>=(n>>1)){
        bool ok=1;
        for(auto v:son[u]) if(sz[v]>(n>>1)){
            ok=0;
            break;
        }
        if(ok) zx=u;
    }
}

int col[max_n];
bool cup[max_n];

inline void dfs2(int u,int cl){
    col[u]=cl;
    for(auto v:son[u])
        dfs2(v,cl);
}

inline bool cmp(int i,int j){return sz[i]<sz[j];}

inline void NoSolution(){
    for(int i=1;i<=n;++i)
        putchar('0'),putchar(' ');
}
int Lim,Cnt;
bool vit[max_n];
inline void dfs3(int u,int id){
    ans[u]=id,vit[u]=1;
    ++Cnt;
    if(Cnt==Lim) return;
    for(int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(vit[v]) continue;
        dfs3(v,id);
        if(Cnt==Lim) return;
    }
}
inline void dfs4(int u,int id){
    ans[u]=id,vit[u]=1;
    ++Cnt;
    if(Cnt==Lim) return;
    for(int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(vit[v] || isrf[i]) continue;
        dfs4(v,id);
        if(Cnt==Lim) return;
    }
}

inline void TreeSol(int v){
    fill(ans+1,ans+1+n,a[2].id);
    vit[zx]=1;
    Cnt=0,Lim=A;
    dfs4(v,a[0].id);
    Cnt=0,Lim=B;
    dfs3(zx,a[1].id);
    for(int i=1;i<=n;++i)
        write(ans[i]),putchar(' ');
}

bool cho[max_n];

inline void dfs5(int u,int id){
    ans[u]=id,vit[u]=1;
    ++Cnt;
    if(Cnt==Lim) return;
    for(int i=e.hd[u];i;i=e.nx[i]){
        int v=e.to[i];
        if(vit[v] || (col[v]<0 && col[v]==-1) || (col[v]>=0 && !cho[col[v]])) continue;
        dfs5(v,id);
        if(Cnt==Lim) return;
    }
}

inline void Normal(int v){
    fill(ans+1,ans+1+n,a[2].id);
    Cnt=0,Lim=A;
    dfs5(v,a[0].id);
    Cnt=0,Lim=B;
    dfs3(zx,a[1].id);
    for(int i=1;i<=n;++i)
        write(ans[i]),putchar(' ');
}

bool End;
#define File ""
signed main(){
    // #ifndef ONLINE_JUDGE
    // freopen(File ".in","r",stdin);
    // freopen(File ".out","w",stdout);
    // #endif
    n=read(),m=read(),A=read(),B=read(),C=read();
    a[0]=Node(A,1),a[1]=Node(B,2),a[2]=Node(C,3);sort(a,a+3);A=a[0].x,B=a[1].x,C=a[2].x;
    for(int i=1;i<=m;++i){
        int u=read()+1,v=read()+1;
        e.add(u,v),e.add(v,u);
    }
    dfs1(1);
    fill(col+1,col+1+n,-3);
    col[zx]=-1;
    for(int x=fa[zx];x;x=fa[x]) col[x]=-2;
    sort(son[zx].begin(),son[zx].end(),cmp);
    for(int i=0,up=son[zx].size();i<up;++i)
        dfs2(son[zx][i],i);
    col[zx]=-1;
    for(int i=1;i<=cnt;++i){
        if(dep[g[i].u]<dep[g[i].v]) swap(g[i].u,g[i].v);
        int u=g[i].u,v=g[i].v;
        if(col[u]>=0 && col[v]==-2)
            cup[col[u]]=1;
    }
    if(sz[son[zx].back()]>=A) return TreeSol(son[zx].back()),0;
    if(n-sz[zx]>=A) return TreeSol(fa[zx]),0;
    if(m==n-1) return NoSolution(),0;
    int sm=n-sz[zx];
    for(int i=0,up=son[zx].size();i<up;++i) if(cup[i]){
        sm+=sz[son[zx][i]];
        cho[i]=1;
        if(sm>=A) return Normal(son[zx][i]),0;
    }
    NoSolution();
    return 0;
}

递归与增量

在一部分构造题中，问题的结构拥有很大的相似性。这时候往往意味着我们的构造也具有很大的相似性或周期性。此时我们通过递归构造的方式，在子问题的基础上进行一些调整来得到原问题的构造，通常是不错的选择。

值得注意的是，递归构造可以是一种思想，实际实现的时候，需要考虑算法时间复杂度的问题。

还值得注意的是，有些题目从递归构造的题目不好像的时候，可以考虑增量构造。

CFgym101221A Baggage

在一个长为 4n4n 的纸带上，编号 2n+1∼4n2n+1\sim 4n 的格子上写了 010101⋯\texttt{010101}\cdots 这样的 01 串。每次操作可以平移相邻两个数到相邻两个空格子里。

构造一个操作数最少的操作序列使其变成 111⋯1000⋯0\texttt{111}\cdots\texttt{1000}\cdots\texttt{0}（起始位置任意，中间不能有空位）。

3≤n≤1003\leq n\leq 100。

题解

注意到第一次交换只会减少一对相邻的不同数字个数，随后每次操作最多减少两对。因此我们求出了答案的下界为 nnn。下面我们来考虑如何构造。

进一步手玩小数据发现最终序列在 2n−1∼4n−12n-1\sim 4n-1 的位置上。考虑递归构造。

设 solve(l,r)\rm{solve}(l,r) 为将 [l,r][l,r] 的数还原并放在 [l−2,r−2][l-2,r-2] 的位置上。构造出如下符合条件的方案：

pic-1

不难发现这样构造能达到下界。

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
58
59
60
61
62
#include<bits/stdc++.h>
// #define int long long
using namespace std;
bool Begin;
const int max_n=100005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n;

inline void Move(int i,int j){
    printf("%d to %d\n",i,j);
}

inline void solve(int l,int r){
    int len=r-l+1;
    if(len<=2)
        return;
    else if(len==6){
        Move(l+1,l-2),Move(l+4,l+1),Move(l+2,l-4);
    }
    else if(len==10){
        Move(l+7,l-2),Move(l+2,l+7),Move(l+5,l+2),Move(l-1,l+5),Move(l+8,l-1);
    }
    else if(len==12){
        Move(l+9,l-2),Move(l+6,l+9),Move(l+1,l+6),Move(l+5,l+1),Move(l-1,l+5),Move(l+10,l-1);
    }
    else if(len==14){
        Move(l+7,l-2),Move(l+4,l+7),Move(l+11,l+4),Move(l+2,l+11),Move(l+8,l+2),Move(l-1,l+8),Move(l+12,l-1);
    }
    else{
        Move(r-2,l-2),Move(l+2,r-2);
        solve(l+4,r-4);
        Move(l-1,r-5),Move(r-1,l-1);
    }
}

bool End;
#define File ""
signed main(){
    // #ifndef ONLINE_JUDGE
    // freopen(File ".in","r",stdin);
    // freopen(File ".out","w",stdout);
    // #endif
    // cerr<<"Memory : "<<(&Begin-&End)/1024.0/1024<<"\n";
    n=read();
    if(n==3){
        Move(2,-1),Move(5,2),Move(3,-3);
        return 0;
    }
    solve(1,n<<1);
    return 0;
}

Androgynos"

构造一个 nn 个点的图，使其与自己的补图同构，或判断无解。

n≤1000n\leq1000。

题解

考虑边数一定要是 22 的倍数，不难得到 n=4k+2n=4k+2 或 n=4k+3n=4k+3 的情况无解。

当 n=4,5n=4,5 时，很容易构造出一组合法的图。

然后考虑增量构造，每次增加四个点，注意到 n=4n=4 时一条链就是一个合法的图。于是每次添加一条四个点的链，让链两端的点向原图的每个点连一条边即可。

pic-2

  • 标题: 构造题经典套路
  • 作者: Arahc
  • 创建于 : 2022-10-12 08:00:00
  • 更新于 : 2023-03-16 13:56:42
  • 链接: https://arahc.github.io/2022/10/12/【笔记】构造题经典套路/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
构造题经典套路
  1. 鸽巢原理
  2. dfs 树
  3. 递归与增量