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

UnionRE · 2026-04-23 14:02:04 · 题解

由于同学之前出过弱化版，并且做过这个题的弱化版的弱化版，所以很容易想到使用二进制构造。

不过观察数据范围发现很难满足这个巨大的 p。于是考虑优化。

思考能够构造所有正整数的序列并且增长比较快的数列的其中一个就是斐波那契数列。可以参考此处。其中告诉我们可以用贪心的方法构造。

我们把 i-1 与 i 和 i-2 与 i 连接即可。

最后通过 i\to 24 的边是否启用来构造即可。

这样构造的最大数很好计算。

由 f_{i+2}=f_{i+1}+f_i，可知构造最大数为：

不过这样边数还是多了，66 条。

于是考虑删去 1\to 24 这个边。即禁用 f_1=1。不过还有 f_2=1，于是最大构造数只会减少 1。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int maxn=24;
int f[maxn];
void init(){
    f[1]=f[2]=1;
    for(int i=3;i<maxn;i++)f[i]=f[i-1]+f[i-2];
}
vector<pair<int,int>> G;
#define add(x,y) G.push_back({x,y});//x<y
signed main(){
    init();
    // freopen("construct.in","r",stdin);
    // freopen("construct.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    int p;
    cin>>p;
    cout<<24<<' ';
    for(int i=3;i<=23;i++){
        add(i-1,i);
        add(i-2,i);
    }
    add(1,2);
    for(int i=2;i<=23;i++){
        add(i,24);
    }
    cout<<G.size()<<endl;
    for(auto [x,y]:G)cout<<x<<' '<<y<<endl;
    for(int i=0;i<=p;i++){
        for(auto [x,y]:G){
            if(y<=23)cout<<1;
        }
        int rem=i;
        bitset<maxn> use;
        use.reset();
        for(int j=23;j>=1;j--){
            if(f[j]<=rem){
                rem-=f[j];
                use[j]=1;
            }
            else use[j]=0;
        }
        for(int j=2;j<=23;j++)cout<<use[j];
        cout<<endl;
    }
    return 0;
}