构造杂题选讲

· · 算法·理论

观察性质类

\text{\textcolor{03A89E}{CF2218F}}

我们先考虑什么样的情况下无解，方便构造。

:::info[x>y 时] 你会发现在一颗子树中有一个大小为偶数的子树就必定有一个对应大小为奇数的子树，所以 x>y 时无解。 :::

:::info[(x+y+1)\bmod 2 > x] 树的大小与条件冲突。 ::: 然后就没有其他无解情况了，这种讨论比其他的方法还是简洁一点。

接下来我们最容易想到的构造就是菊花图了。

我们从菊花图开始，有 x+y-(x+y+1)\bmod 2 个子树大小为奇数的子树，然后你将每个子树大小为 1 的节点扔到另外一个下面即可，这样做子树大小为奇数的节点个数会减 1，一直减到为 y 即可。

:::info[代码]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,y;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        cin>>x>>y;
        ll mn=(x+y+1)%2;
        if(mn>x||x>(x+y)/2){cout<<"NO\n";continue;}
        cout<<"YES\n";
        for(int i=1;i<=x-mn;i++){
            cout<<1<<" "<<i*2<<"\n";
            cout<<i*2<<" "<<i*2+1<<"\n";
        }
        for(int i=(x-mn)*2+2;i<=x+y;i++){
            cout<<1<<" "<<i<<"\n";
        }
    }
    return 0;
}

:::

\text{\textcolor{AA00AA}{CF1427D}}

link

纯构造。

观察到你将一个数放在该数 +1 的前面一定可以在有限步数中满足条件。

我们对每一步进行构造：

不妨我们放最末尾不满足 a_i=i 的一个数，令其下标为 t，找到 a_t+1 在数组中的下标，令其下标为 d，易证 d<t。

构造如下：

d=1 otherwise
t=n n-1，1 d-1，n-d，1
otherwise t-1，1，n-t d-1，t-d，1，n-t

可以用逆序对证明步数最坏是 O(n^2) 的，考虑优化。

注意到对于序列 5\ 6\ 3\ 4\ 1\ 2，此时 t=6=n\ d=3，使用操作序列 2\ 3\ 1，我们的策略会让 2 和 3 粘到一起，变成 2\ 3\ 4\ 1\ 5\ 6。

但是这样显然是不优的，把 1 和 2 拆开了，应该把 1\ 2 一起搬到前面去。

所以考虑找出一个最大的数 dr，使得 i\in[d,dr)，有 a_i=a_{i+1}-1。

我们将整个区间一起搬走就可以不拆开原来就优秀的子段。

然后就每一步的构造变成了这样：

d=1 otherwise
t=n dr，n-dr d-1，dr-d+1，n-dr
otherwise dr，t-dr，n-t d-1，dr-d+1，t-dr，n-t

因为每次都不会破坏原来满足的 a_i=a_{i+1}-1，所以操作次数最多 n-1 次，满足题意。 :::info[代码]

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define db double
#define pb push_back
using namespace std;
ll n,a[60],b[60],cnt;
vector<ll>ans[60];
inline void ch(ll x){
    ll now=0,k=n;
    for(int i:ans[x]){
        ll r=now+i;
        for(int j=now+1;j<=r;j++)b[n-now-i+(j-now)]=a[j];
        now+=i;
    }for(int i=1;i<=n;i++)a[i]=b[i];
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    if(n==1){cout<<0;return 0;}
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        ll fl=0,fd=0;
        for(int j=n;j>=1;j--)if(a[j]!=j){fl=j;break;}
        if(!fl)break;
        cnt++;
        if(fl==n){
            for(int j=1;j<=n-1;j++)if(a[j]==a[n]+1){fd=j;break;}
            ll fdr=fd;
            while(a[fdr+1]==a[fdr]+1)fdr++;            
            if(fd==1){ans[cnt].pb(fdr);ans[cnt].pb(n-fdr);}
            else{
                ans[cnt].pb(fd-1);
                ans[cnt].pb(fdr-fd+1);
                ans[cnt].pb(n-fdr);
            }
        }else{
            for(int j=1;j<=fl-1;j++)if(a[j]==a[fl]+1){fd=j;break;}
            ll fdr=fd;
            while(a[fdr+1]==a[fdr]+1)fdr++;
            if(fd==1){ans[cnt].pb(fdr);ans[cnt].pb(fl-fdr);ans[cnt].pb(n-fl);}
            else{
                ans[cnt].pb(fd-1);
                ans[cnt].pb(fdr-fd+1);
                ans[cnt].pb(fl-fdr);
                ans[cnt].pb(n-fl);
            }
        }ch(cnt);
        // for(int i=1;i<=n;i++)cout<<a[i]<<" ";
        // cout<<"\n";
    }
    cout<<cnt<<"\n";
    for(int i=1;i<=cnt;i++){
        cout<<ans[i].size()<<" ";
        for(int j:ans[i])cout<<j<<" ";
        cout<<"\n";
    }
    return 0;
}

:::

\text{\textcolor{FF8C00}{CF1438D}}

link

不知道为什么有 *2200。

注意到每次操作后数列 异或和不变（这个性质异或题常考），最终序列的异或和是可以算出来的。

如果 2\mid n，那么最终异或和应当为 0，否则肯定无解。

如果 2\nmid n，那么最终异或和为最终相同的那个数。

我们对方案给出构造：

此时对于 $2\nmid n$ 的序列，一定满足 $\forall i\in[1,n-3],2\nmid i$ 有 $a_i=a_{i+1}$，且 $a_n=a_{n-1}=a_{n-2}$。 对于 $2\nmid n$ 的序列，由于异或和等于 $0$，所以前面 $n-1$ 个数异或起来等于 $a_n$。 所以每次进行操作后都会将前缀异或和放入最后操作的一个数中。 那么所有操作操作完之后满足 $\forall i\in[1,n-1],2\nmid i$ 有 $a_i=a_{i+1}$。 这样的话我们再将前面两两相等的数与 $n$ 操作即可。 即 $\forall i\in[1,n-3],2\nmid i$，对 $i$、$i+1$、$n$ 进行操作。 代码很短： :::info[代码] ```cpp #include<bits/stdc++.h> #define ll long long #define pii pair<ll,ll> #define db double using namespace std; const ll mx=1e5+5; ll n,a[mx],sum; inline void pt(){//构造方案 cout<<"YES\n"; cout<<n-2<<"\n"; for(int i=1;i+2<=n;i+=2){ cout<<i<<" "<<i+1<<" "<<i+2<<"\n"; }for(int i=1;i+2<n;i+=2){ cout<<i<<" "<<i+1<<" "<<n<<"\n"; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;i<=n;i++)cin>>a[i],sum^=a[i]; if(n%2==0&&sum!=0){cout<<"NO";return 0;}//无解 pt(); return 0; } ``` ::: ### $\text{\textcolor{FF0000}{CF1427E}}

link

我们先观察一下题目性质，对于加法，我们可以使用龟速乘（即将乘数分解成二进制然后只用加法算乘法，思想和快速幂相似）模拟乘法，消耗操作次数 O(\log V)。

我们从结果考虑过程，操作到最后的一步一定是形如 2t\oplus (2t+1) 的形式，即先需要存在两个数 c，d，使得：

c-d=1

你觉不觉得这个式子有点眼熟？

:::info[眼熟]

(ax)-(-by)=1

就是 exgcd 的形式，方程有解当且仅当 \gcd(a,b)=1。 :::

观察出这个性质后我们需要通过乘法和异或构造出一对 a,b，满足 \gcd(a,b)=1。

设 x 的二进制最高位 2^k，则 (x,2^kx \oplus x) 是满足 \gcd(x,2^kx \oplus x)=\gcd(x,(2^k+1)x-2^{k+1})=\gcd(x,2^{k+1})=1 的一对数。

带入 a=2^kx\oplus x，b=x，用 exgcd 解出方程的一组解 (X,Y)，然后将 a 乘上 X，b 乘上 Y 即可。

但是对于 aX=2t-1，bY=2t 不满足条件的情况，需要依次加上 x。

然后就做完了。

:::info[代码]

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define db double
#define pb push_back
using namespace std;
const ll mx=1005;
ll n,k=-1,cnt,now;
vector<ll>v[mx];
inline ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return a;}
    ll res=exgcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-(a/b)*y;
    return res;
}
inline void gg(ll x,ll y){
    ll cc=-1,yy=y;
    while(yy){yy>>=1;cc++;}
    yy=x;
    for(ll i=0;i<cc;i++){
        v[++cnt].pb(yy);
        v[cnt].pb(yy);
        v[cnt].pb(1ll);
        yy<<=1ll;
    }
    ll sum=yy;
    for(ll i=0;i<cc;i++){
        if(!(y&(1ll<<i)))continue;
        else 
        v[++cnt].pb(sum);
        v[cnt].pb((x<<i));
        v[cnt].pb(1ll);
        sum+=(x<<i);
    }
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    ll x=n;now=n;
    while(x){x/=2;k++;}
    while(k){
        v[++cnt].pb(now);
        v[cnt].pb(now);
        v[cnt].pb(1);
        now<<=1ll;
        k--;
    }v[++cnt].pb(now);v[cnt].pb(n);v[cnt].pb(2);
    ll a=(now^n),b=-n,y=0;x=0;
    exgcd(a,b,x,y);
    gg(abs(b),abs(y));
    gg(abs(a),abs(x));

    ll q=abs(b*y),p=abs(a*x);
    if(min(q,p)%2==1){
        v[++cnt].pb(q);v[cnt].pb(n);v[cnt].pb(1);
        v[++cnt].pb(p);v[cnt].pb(n);v[cnt].pb(1);
        p+=n;q+=n;
    }v[++cnt].pb(p);v[cnt].pb(q);v[cnt].pb(2);
    cout<<cnt<<"\n";
    for(int i=1;i<=cnt;i++){
        if(v[i][2]==1)cout<<v[i][0]<<" + "<<v[i][1]<<'\n';
        else cout<<v[i][0]<<" ^ "<<v[i][1]<<'\n';
    }
    return 0;
}

:::

脑电波类

\text{\textcolor{0000CC}{CF1758D}}

link

看上去简单，想起来难，纯脑电波。

因为要构造 n 个数，那么你的构造要和 n 强相关，我们考虑让 \max_{i=1}^na_i-\min_{i=1}^na_i=kn=\sqrt{sum}。

对于 2\mid n，构造相对简单，考虑让 \sqrt{sum}=n，输出 \frac{n}{2},\frac{n}{2}+1,\frac{n}{2}+2,\dots,n-2,n-1,n+1,n+2,\dots,\frac{3n}{2}-2,\frac{3n}{2}-1,\frac{3n}{2} 即可。

对于 2\nmid n，我们发现让中位数大小为 n 实现不了，考虑让中位数为 4n，\sqrt{sum}=2n，输出 4n,2n,6n,2n+1,6n-1,\dots,2n+\frac{n-1}{2},6n-\frac{n-1}{2} 满足条件。

只输出的题的代码就不放了。

\text{\textcolor{AA00AA}{CF1207E}}

link

看上去难，想起来简单，纯脑电波。

注意到 2^{14}=(2^7)^2，然而 2^6<100<2^7，所以我们基于此考虑。

考虑输出 1 到 100，可以获得 x 的二进制下的 8 到 14 位。

考虑输出 128 的 1 倍到 100 倍，可以获得 x 的二进制下的 1 到 7 位。

加起来输出即可。

这种题的代码应该更不用放了。

\text{\textcolor{000000}{Gym-104337E}}

link

这题我尝试用一般思考的历程来写题解：

:::info[think 1] 对于 30 的矩阵大小限制和 10^9 的路径数据范围，我们很容易联想到 2^{30}>10^9。 :::

:::info[think 2] 我们也就很容易给出一种基于 2 的幂次的构造：

1 1 0 0 0 0
1 1 1 0 0 0
0 1 1 1 0 0
0 0 1 1 1 0
0 0 0 1 1 1
0 0 0 0 1 1

然后路径数量是这样：

1 1 0 0 0 0
1 2 2 0 0 0
0 2 4 4 0 0
0 0 4 8 8 0
0 0 0 8 16 16
0 0 0 0 16 32

现在的问题是：我们该怎么将路径数传到终点？

显然，如果你基于图中的方法添加 1 肯定会有路径的交叉，难以构造。

所以我们只能将其分开：

1 1 0 0 0 0 0 0
1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0
0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1

这时候需要的列数为 2\log_2 V=60，不满足题意。 ::: 那咋办？ :::info[hint 1] 基于进制的思想一定是要保留的，不过是要做出一点修改。 :::

:::info[hint 2]

1 1 1 
1 2 3
1 3 6

:::

::::info[solution] 我们基于 3\times 3 的全 1 矩阵进行构造。

由于这个矩阵的路径数为 6，用同样的方法构造只需要 \lceil2\log_6V\rceil=24 行和列。

然后我们将最后一行和最后一列设成全 1，然后从路径数为 6^k 的格子中连出若干条全 1 的路径通向最后一行和最后一列，将路径数传给终点，最后在传递过程中乘上当前位上的系数即可。

如图：

:::info[代码]

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define db double
using namespace std;
ll n,a[35][35];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=12;i++){
        for(int k=1;k<=3;k++)
            for(int l=1;l<=3;l++)
                a[i*2-2+k][i*2-2+l]=1;
    }
    for(int i=1;i<=30;i++)a[30][i]=a[i][30]=1;
    ll cnt=0;
    while(n){
        cnt++;
        ll k=n%6;n/=6;
        if(!k)continue;
        if(cnt%2){
            for(int i=cnt*2+2;i<=29;i++)a[i][cnt*2-1]=1;
            if(k==2)a[29][cnt*2]=1;
            if(k==3)a[29][cnt*2]=a[28][cnt*2]=1;
            if(k==4)a[29][cnt*2-1]=0,a[29][cnt*2]=a[29][cnt*2+1]=a[28][cnt*2]=a[27][cnt*2]=1;
            if(k==5)a[29][cnt*2]=a[29][cnt*2+1]=a[28][cnt*2]=1;
        }else{
            for(int i=cnt*2+2;i<=29;i++)a[cnt*2-1][i]=1;
            if(k==2)a[cnt*2][29]=1;
            if(k==3)a[cnt*2][29]=a[cnt*2][28]=1;
            if(k==4)a[cnt*2-1][29]=0,a[cnt*2][29]=a[cnt*2+1][29]=a[cnt*2][28]=a[cnt*2][27]=1;
            if(k==5)a[cnt*2][29]=a[cnt*2+1][29]=a[cnt*2][28]=1;
        }
    }
    cout<<30<<"\n";
    for(int i=1;i<=30;i++){
        for(int j=1;j<=30;j++)cout<<a[i][j]<<' ';
        cout<<'\n';
    }
    return 0;
}

:::

::::

习题：

CF1311E，注意观察深度性质。

CF1098C，即 CF1311E 加强版，做完 CF1311E 后再做。

CF1392E，二进制刻画构造。