OI 中一些构造方法

· · 个人记录

构造沙漠。

不只是构造题，还包括一些和构造有关的题目。

之后遇到别的方法还会继续更。

其实就是瞎写。

上下界构造

方法简述

一些题目要求构造方案让某个东西“最小”或“最大”，有些情况答案刚好就是理论的上下界。然后根据这些边界的求解办法不难得出构造。

例题

① [CF1667C] Half Queen Cover

就是放一些能覆盖一行一列一斜线的皇后使得棋盘的每个格子能被覆盖。

假设它的理论下界为 k。由于删掉一行一列之后被覆盖的主对角线任然是连续的，所以把被覆盖的行和列删掉，剩下一些格子构成 (n-k)\times(n-k) 的正方形，则这些格子都需要被斜线所覆盖。

由于这个剩下的正方形共有 2(n-k)-1 条对角线，所以就要有 k\ge 2(n-k)-1。因此理论下界为 \left\lceil\dfrac{2n-1}{3}\right\rceil。

这个下界要求行与列不重复。考虑 n\equiv2\pmod3 的情况，这时斜线也不重复。这种情况就是把它大概划分成九宫格，然后在左上角和中间格子的副对角线摆上皇后就好了。

然后对于另外两个余数就在右下角补上一两个皇后。

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,k1,k2;
int main(){
    scanf("%d",&n);
    k=(n*2+1)/3;
    printf("%d\n",k);
    k1=(n-2)/3; k2=(n+1)/3;
    for(int i=1;i<=k1;i+=1){
        printf("%d %d\n",i,k1-i+1);
    }
    for(int i=1;i<=k2;i+=1){
        printf("%d %d\n",k1+i,k1+k2-i+1);
    }
    for(int i=1;i<=k-k1-k2;i+=1){
        printf("%d %d\n",n-i+1,n-i+1);
    }
    return 0;
}

② [CF1666E] Even Split

一条线段上面有 n 个点，然你分成 n 段使得每段恰好有一个点，最小化长度的极差。

不难通过二分查找得出最大的最小值 L 和最小的最大值 R，然后极差的理论下界就是 R-L。

构造的话先从左往右确定每个划分点的范围，即

\left\{ \begin{aligned} &l_i=\max(a_i,l_{i-1}+L)\\ &r_i=\min(a_{i+1},r_{i-1}+R) \end{aligned} \right.

不难证明 l_i<r_i，然后从右往左确定每个划分点就好了，先后后一个划分点的范围是比前一个划分点要紧的，所以一定存在一种方案。

评测记录

配对

方法简述

比方说一些填数问题，就能将一些数两两配对放在一些同样被两两配对的位置。

例题

① [CF1670E] Hemose on the Tree

有一棵 n=2^p 的树，选一个根然后要在所有点和边不重复填上 1 到 2^{p+1}-1 的整数，最小化所有点和边到跟的路径上所有值的异或和最大值。

其实也用到了『上下界构造』，它的下界是 2^p，因为总有一些位置使得二进制的第 p 位是 1。

如果第 p 位为 1 的话其它位就要是 0。按照能把其它位消掉的原则我们把 (i,i+2^p) 分为一组，余下一个 2^p 作为根。根其实是随便取的，然后其它点和连接父亲的边被分为一组，填入同一组的数，具体填法看当前第 p 位是不是 1，其实和深度奇偶性有关。

#include<iostream>
#include<cstdio>
using namespace std;
int t,p,n;
int ansv[300005],anse[300005];
int tot,to[600005],nxt[600005],va[600005],lst[300005];
void add(int x,int y,int z){
    to[++tot]=y;
    nxt[tot]=lst[x];
    lst[x]=tot;
    va[tot]=z;
    return;
}
void dfs(int x,int fa,int now){
    int y,z;
    for(int i=lst[x];i;i=nxt[i]){
        if((y=to[i])==fa) continue;
        z=va[i];
        if(now) ansv[y]=z,anse[z]=z+n;
        else ansv[y]=z+n,anse[z]=z;
        dfs(y,x,now^1);
    }
    return;
}
void solve(){
    int x,y;
    scanf("%d",&p); n=(1<<p); tot=0;
    for(int i=1;i<=n;i+=1) lst[i]=0;
    for(int i=1;i<n;i+=1){
        scanf("%d%d",&x,&y);
        add(x,y,i); add(y,x,i);
    }
    ansv[1]=n; dfs(1,0,1);
    printf("1\n");
    for(int i=1;i<=n;i+=1) printf("%d ",ansv[i]);
    printf("\n");
    for(int i=1;i<n;i+=1) printf("%d ",anse[i]);
    printf("\n");
    return;
}
int main(){
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}

简化条件

方法简述

就是限制条件比较多，又或者是一个限制条件中涉及到的量比较多比较麻烦的题目，有时候有些条件是满足另一些条件后自动满足的，然后就可以少考虑一些条件。

例题

① [CF1734E] Rectangular Congruence

就是给一个 n\times n 的矩阵，其中 n 是质数，要你填入 0 到 n-1 的整数，其中主对角线已经填好，要对于 r_1\not=r_2,c_1\not=c_2 满足 a_{r_1,c_1}+a_{r_2,c_2}\not\equiv a_{r_1,c_2}+a_{r_2,c_1}\pmod n。

作为限制条件的四元组共有 \mathcal O(n^4) 个，就连 SPJ 都不可能一个个检查，所以肯定有很多是没用的。

条件其实就是限制子矩阵的四个角，移一下项就是 a+d-b-c\not\equiv0\pmod n，令左边那一坨是子矩阵的价值。考虑下面相邻的一个子矩阵价值是 c+f-d-e，然后把它们相加合并一下就是 a+f-b-e，也就是拼起来大矩阵的价值。

由于最小的矩阵是 2\times2 的，所以一行一列只有 n-1 个最小的矩阵。由于 n 是质数，所以由最小矩阵拼接起来的大矩阵大小一定不是 n 的倍数。

所以只要限制每个 2\times2 的矩阵价值同时为 1 到 n-1 的某一个数就行了，这样大矩阵的价值也一定不为 0。

剩下就只要确定第一行然后其他位置就唯一了。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[355][355];
int add(int x,int y){
    if((x+=y)>=n) x-=n;
    return x;
}
int sub(int x,int y){
    if((x-=y)<0) x+=n;
    return x;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i+=1) scanf("%d",&a[i][i]);
    for(int i=2;i<=n;i+=1){
        for(int j=i-1;j>=1;j-=1){
            a[i][j]=sub(sub(add(a[i-1][j],a[i][j+1]),1),a[i-1][j+1]);
        }
        for(int j=i+1;j<=n;j+=1){
            a[i][j]=sub(add(add(a[i-1][j],a[i][j-1]),1),a[i-1][j-1]);
        }
    }
    for(int i=1;i<=n;i+=1){
        for(int j=1;j<=n;j+=1){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

② [CF1615D] X(or)-mas Tree

给一棵树和一些限制条件，每个限制条件限制两个点路径上所有权值异或和中 \texttt1 个数的奇偶性，其中有一些边权已经确定，询问存不存在构造方案并给出构造。

这个限制条件太麻烦了，考虑把它简化掉。观察异或之后的 popcount 是如何改变的，可以发现 popcount 改变的奇偶性恰好就是新异或上的数的 popcount 的奇偶性。所以只要关注边权 popcount 的奇偶性就好了，每条边权变为 0 或 1，限制条件变为路径的异或和是 0 还是 1。

这个条件涉及到的变量还是比较多的，根据树上路径问题的经典套路，设 d_x 表示从 x 到根路径异或和的奇偶性，然后根据 d_x\oplus d_y 的奇偶性来构造就好了。可以用带权并查集来维护。

评测记录

分答案讨论

方法简述

有时候，答案的可能范围很小。不同于『上下界构造』，答案不一定刚好是上下界，因此做法是排除法式地检查每个答案。

例题

① [CF1689E] ANDfinity

两个元素连边当且仅当他们按位与的结果不为零，一次操作能让一个元素 \pm1，构造出最少操作数使得所有元素联通。

首先要把 0 都变成 1，因此 0 的个数就是下界。如果仍然不连通，考虑所有数中 lowbit 最大的数，如果只有一个，减去 1 之后最后几位都会变成 1，就能保证这个数与其它数之间都有连边；如果有多个，再取另外一个加一，这样也能保证联通。因此上界最多只会大 2。

如果本来就连通答案就是下界；否则枚举变哪个数然后检查连通性；再不然答案就是上界。判断数的连通性可以转化为判断二进制位的连通性。

评测记录

② [CF1659E] AND-MEX Walk

给一张图，如果一条非简单路径（可以经过重复点边）经过的边权为 w_1,w_2,\dots,w_k，那么它的权值定义为 {\rm mex}\big(\{w_1,w_1\&w_2,\dots,w_1\&w_2\&\dots\&w_k\}\big)，然后多次询问两点 u,v 之间所有非简单路径的最小权值。

根据按位与的性质，不难发现集合中 1 和 2 不能同时出现，所以答案上界为 2。

如果答案为 0，就意味着存在一条路径使得上面所有边权按位与的结果不为 0，用并查集维护每一位按位与结果为 1 的连通块。

如果答案为 1（当然首先不能为 0），存在起点的一个连通块要么能把第 0 位磨掉，要么是往外走一步同时能把第 0 位和当前位磨掉，维护多点东西就好了。

其它情况一定是 2 的。

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,q,t=30;
int x,y,z;
int fa[30][100005];
int o[30][100005];
int tag[30][100005],vi[30][100005];
int find(int c,int x){
    return fa[c][x]==x?x:fa[c][x]=find(c,fa[c][x]);
}
void merge(int c,int x,int y,int z){
    x=find(c,x); y=find(c,y);
    fa[c][x]=y;
    o[c][y]&=(o[c][x]&z);
    return;
}
int query(int x,int y){
    for(int i=0;i<t;i+=1){
        if(find(i,x)==find(i,y)) return 0;
    }
    for(int i=1;i<t;i+=1){
        y=find(i,x);
        if(!o[i][y]||tag[i][y]) return 1;
    }
    return 2;
}
int main(){
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i+=1){
        for(int j=0;j<t;j+=1){
            fa[j][i]=i;
            o[j][i]=1;
        }
    }
    for(int i=1;i<=m;i+=1){
        scanf("%d%d%d",&x,&y,&z);
        for(int j=0;j<t;j+=1){
            if(z>>j&1) merge(j,x,y,z&1);
            else if(!(z&1)) vi[j][x]=vi[j][y]=1;
        }
    }
    for(int i=1;i<=n;i+=1){
        for(int j=0;j<t;j+=1){
            if(vi[j][i]) tag[j][find(j,i)]=1;
        }
    }
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&x,&y);
        printf("%d\n",query(x,y));
    }
    return 0;
}

反向构造

方法简述

正着来不好想的题目就要反着想，大概就是构造出原问题的补集。

例题

① [CF1610E] AmShZ and G.O.A.T.

一个序列被称作毒瘤的当且仅当小于平均值的数的个数小于大于平均值的数的个数。要删掉尽可能少的数使得不存在子序列是毒瘤的。

根据『简化条件』的方法，先看看这个毒瘤序列有什么性质，它能不能被更小的毒瘤序列表示。手动模拟可以发现任意长度的毒瘤序列一定可以删剩一个长度为 3 的毒瘤序列。

考虑如何证明。采用反证法假设不存在，设最小值、次大值、最大值分别为 x,y,z。首先一定有 y\le\dfrac{x+z}{2}，然后为了满足平均值两边数的个数的大小关系，必须要在 [x,y] 里面有一个数 w 把平均值拉到小于 y 的位置，然后再在平均值右边放一个数。这时候平均值到 y 一定会远于平均值到 w，所以新放的数一定能和 w,y 组成毒瘤数列。

所以只要保证不存在任何长度为 3 的毒瘤数列就好了。

但是如果考虑删除什么数是不好想的，因此要考虑保留什么数。首先确定最小值，等于最小值的位置全部都要选，然后再选一个严格次小值。根据贪心，这个严格次小值要尽可能小，接着再选后面的数，在满足条件的前提下也要尽量小。不难发现，每次新增一个数极差就会翻倍，所以最多也只有 \mathcal O(\log V) 个数。

所以枚举最小值后每次暴力用二分查找，最后取一个保留个数最大值就好了，复杂度 \mathcal O(n\log n\log V)。

#include<iostream>
#include<cstdio>
#define inf 1145141919
using namespace std;
int t,n,ans;
int a[200005];
int find(int l,int lmt){
    int r=n+1,mid;
    while(l<r){
        mid=l+r>>1;
        if(a[mid]>=lmt) r=mid;
        else l=mid+1;
    }
    return l;
}
int check(int x,int res){
    int now=x+1;
    if(now<=n) res+=1;
    while((now=find(now+1,2*a[now]-a[x]))<=n) res+=1;
    return res;
}
void solve(){
    scanf("%d",&n); ans=inf;
    for(int i=1;i<=n;i+=1) scanf("%d",&a[i]);
    a[n+1]=inf;
    for(int i=1,j=0;i<=n;i=j+1){
        while(a[i]==a[j+1]) j+=1;
        ans=min(ans,n-check(j,j-i+1));
    }
    printf("%d\n",ans);
    return;
}
int main(){
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}

分组构造

方法简述

如果可以将要构造的东西分成若干组后，使得每组之间的构造方法互不影响，那就可以分开来构造。

例题

① [CF1628C] Grid Xor

本质上就是选一些能格子使得所有格子被覆盖奇数次，一个格子能覆盖上下左右四格，不包括自己。

这类棋盘问题很经典的套路就是黑白染色，然后发现白色的格子只能影响到黑色格，反之亦然，所以按照横纵坐标之和的奇偶性分类。

考虑与主对角线平行的同色斜线，在白色格子上放棋子会影响到旁边两条斜线，因此放棋子的白色斜线中间还要隔着一条白色斜线，同一条斜线上的相邻两个棋子中间也要隔着一个棋子，这样每个黑色格子都恰好被覆盖一次。对于黑色同理。

具体放法有其实有很多种，代码展示的是其中一种放法。

#include<iostream>
#include<cstdio>
using namespace std;
int t,n,ans,a,x,y;
void solve(){
    scanf("%d",&n); ans=0;
    for(int i=1;i<=n;i+=1){
        for(int j=1;j<=n;j+=1){
            scanf("%d",&a);
            if((i+j)&1){
                x=(i&3); y=(j&3);
                if(i>=j){
                    if(x==2&&y==1) ans^=a;
                    if(x==0&&y==3) ans^=a;
                }
                else{
                    if(x==1&&y==0) ans^=a;
                    if(x==3&&y==2) ans^=a;
                }
            }
            else{
                x=((n-i+1)&3); y=(j&3);
                if(n-i+1>=j){
                    if(x==2&&y==1) ans^=a;
                    if(x==0&&y==3) ans^=a;
                }
                else{
                    if(x==1&&y==0) ans^=a;
                    if(x==3&&y==2) ans^=a;
                }
            }
        }
    }
    printf("%d\n",ans);
}
int main(){
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}

② [CF1607H] Banquet Preparations 2

给出若干三元组 (a_i,b_i,m_i)，可以在 a_i,b_i 中总共减去 m_i 获得二元组 (a'_i,b'_i) 使得 a'_i,b'_i\ge0，构造一种使二元组的种类最少的方案。

考虑怎样的三元组才有可能得到相同的二元组，很显然是最后总和 a_i+b_i-m_i 相同的。因此可以按照最后的总和分成若干组，这样每一组互不影响，并且同一组只要保证 a'_i 相同就行了。

事实上，每个 a'_i 都有一个变化的范围 [l_i,r_i]，然后问题就是选最少的点使得每个区间都覆盖至少一个点。

按照 r_i 从小到大排序，如果当前区间还没有覆盖之前的任何一个点，那么新开一个点在 r_i 处一定是最优的；否则不开新点，因为这样一定不会更劣。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,ans,now;
int d[200005][2];
struct tri{
    int id,a,b,m;
}p[200005];
int val(tri x){
    return x.a+x.b-x.m;
}
int ri(tri x){
    int a=x.a,b=x.b,m=x.m;
    if(b>=m) return a;
    else return a-(m-b);
}
bool operator<(tri x,tri y){
    if(val(x)==val(y)){
        return ri(x)<ri(y);
    }
    return val(x)<val(y);
}
void updt(tri x,int y){
    int i=x.id,a=x.a,b=x.b,m=x.m;
    d[i][0]=a-y,d[i][1]=m-(a-y);
    return;
}
void solve(){
    scanf("%d",&n); ans=0;
    for(int i=1;i<=n;i+=1){
        scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].m);
        p[i].id=i;
    }
    sort(p+1,p+n+1);
    for(int l=1,r=0;l<=n;l=r+1){
        while(r<n&&val(p[l])==val(p[r+1])) r+=1;
        ans+=1; now=ri(p[l]); updt(p[l],now);
        for(int i=l+1;i<=r;i+=1){
            if(p[i].a-p[i].m>now){
                ans+=1; now=ri(p[i]);
            }
            updt(p[i],now);
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=n;i+=1){
        printf("%d %d\n",d[i][0],d[i][1]);
    }
    return;
}
int main(){
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}

Thanks~