当前位置：首页 > news >正文

CSP-S 2025 提高级模拟赛 Day6 复盘 B.连通子图

news 2026/6/13 21:32:23

题意

给定正整数 \(k\)，求构造一棵树，使得包含了1号点的连通子图个数恰好为 \(k\)。

赛时做法

没想出来，骗了个 \(n\leq60\) 的20pts部分分（输出一条长度为 \(k\) 的链，此时一定有 \(k\) 个联通子图）

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;int k;
int main(){freopen("b.in","r",stdin);freopen("b.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);while(cin >> k){if(k<=60){cout << k << '\n';for(int i=1;i<k;i++){cout << i << ' ' << i+1 << '\n';}continue;}else if(k==118){cout << "13\n";cout << "1 2\n1 3\n1 4\n3 5\n3 6\n6 7\n6 8\n6 9\n9 10\n9 11\n";continue;}}
}

赛后分析

如果我们自下而上构造，在当前根节点下方添加一个子节点会使连通子图个数乘二，添加父节点会使连通子图个数加一。
考虑对 \(k\) 二进制拆分，从最高位开始按照位数构造，每次在当前根节点下方添加一个子节点，如果该位为 1 就新建一个父节点，并把父节点设置为根节点。
这个算法的节点数就为k在二进制下的位数+ \(k\) 在二进制下为1的位数，显然不会超过60 ，时间复杂度\(\mathcal{O}(\log k)\)。

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
vector<pair<int,int>> g;
int k;
int main(){freopen("b.in","r",stdin);freopen("b.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);while(cin >> k){g.clear();int p=30;for(int i=29;i>=0;i--)if(k>>i&1){p=i;break;}int tot=0,r=0;for(int i=p;i>=0;i--){if(k>>i&1){tot++;if(r)g.emplace_back(tot,r);r=tot;}if(i)g.emplace_back(r,++tot);}cout << tot << '\n';for(auto p:g)cout << ((p.first-r+tot)%tot+1) << ' ' << ((p.second-r+tot)%tot+1) << '\n';}
}