题解：P16344 [科大国创杯初中组 2026] 构造题

· · 题解

通过二进制拆分，给出一种只用 24 个顶点，64 条边的构造方式。

分析

总共用 n 个节点，d[i] 为从 1 号节点走到 i 号节点的总方法数，若在 i 和 n 之间连一条边，则这条边对答案的贡献就是 d[i]。

考虑对 p 二进制拆分，对于任意 j \in \{0, 1, \dots, \lfloor \log_2(p) \rfloor\}，存在节点 i 使得 d[i] = 2^j，此时 0 到 p 中所有数都可以被表示出来。

Step 1

每 3 个节点组成一个模块一，连边：

此时发现 d[i+2]=2 \times d[i+1]=2 \times d[i]，将多个模块一首尾相连联，每隔 1 个节点d[i]会翻一倍。

像这样构造（把 7 到 9 和 8 到 9 看成一条边，来构造出 2^3），连到最后会发现节点浪费很多，边还剩很多，最多可以构造出 p=4095。

Step 2

类似模块一，将 4 个节点两两连边，构造出模块二，将模块二首尾相连，以 i 为起始点的一个模块中，此时 d[i+3]=2 \times d[i+2]=4 \times d[i+1]=4 \times d[i]， 可以发现到最后节点浪费很多。

类似模块一和模块二，将 5 个节点两两连边，构造出模块三，将模块三首尾相连，以 i 为起始点的一个模块中，此时 d[i+4]=2 \times d[i+3]=4 \times d[i+2]=8 \times d[i+1]=8 \times d[i]， 可以发现到最后边数不够。

Step3

考虑将模块二和模块三混联来平衡节点数和边数，这里给出一种构造方式（构造方式不唯一）：使用 5 个模块二，2 个模块三，对于没连到 24 的边全部保留，对于连到 24 的边通过二进制拆分来判断是否保留。

具体细节看代码。

代码

#include<bits/stdc++.h> 
using namespace std;
int d[100]={1,3,4,5,7,8,9,11,12,14,15,17,18,20,21,22,23};
        //  0 1 2 3 4 5 6 7  8  9  10 11 12 13 14 14 15
        //    表示d[i]条边连到24,上面那行注释为不同d[i]连到24方案数对应的二次幂 ,2^16用2^15+2^14+2^14表示,因为p最大为75000所以2^16+2^13+...完全够用 
int vis[100];
int main() {
     ios::sync_with_stdio(false);  
    cin.tie(0);                 
    cout.tie(0);
    //freopen("construct.in","r",stdin);
    //freopen("construct.out","w",stdout);

     int p;
     cin>>p;
     cout<<24<<" "<<64<<endl;
     for(int i=1;i<=5;i+=4){//模块3 
        int q=i+4;
        for(int j=i;j<=q;j++){
            for(int x=j+1;x<=q;x++){
                cout<<j<<" "<<x<<endl;
             }
         }
     }
     for(int i=9;i<=18;i+=3){//模块2 
        int q=i+3;
        for(int j=i;j<=q;j++){
            for(int x=j+1;x<=q;x++){
                cout<<j<<" "<<x<<endl;
             }
         }
     }
     //连最后一个模块2 
     cout<<21<<" "<<22<<endl;
     cout<<21<<" "<<23<<endl;
     cout<<22<<" "<<23<<endl;
     //连到24的边 
     for(int i=0;i<17;i++){
        cout<<d[i]<<" "<<24<<endl;
     }
     for(int i=0;i<=p;i++){ 
        int t=i;
         if(t>=65536){//特殊处理 2^16用2^15+2^14+2^14表示 
            t-=65536;
            vis[16]=1,vis[15]=1,vis[14]=1;
        }
        if(t>=32768){
           t-=32768;
           vis[16]=1;
        }
        if(t>=16384){
            t-=16384;
            vis[15]=1; 
        }
        for(int j=16384,jj=14;j>=1;j/=2,jj--){
            if(t>=j){
                t-=j;
                vis[jj]=1;
            }
        }
        for(int j=1;j<=47;j++)cout<<1;
        for(int j=0;j<17;j++){
            cout<<vis[j];
            vis[j]=0;   
        }
        cout<<endl;
     }
    return 0;
}