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

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

题意

给定正整数 \(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';}
}

总结

思维能力还是不行,要多练。

http://www.hskmm.com/?act=detail&tid=30369

相关文章:

  • 新手村程序
  • Android Camera openCamera - 教程
  • 信号与系统
  • 大作业第一阶段验收小组集体加5分 -
  • 业务定义与指标体系搭建
  • Linux使用笔记
  • [Vulhub靶机]W1R3S靶机渗透
  • 基于zynq实现一个边缘识别视频流(预学习HLS篇)
  • 咬鼠
  • 10月13日日记
  • 分享一个知乎高赞回答生成AI指令:让技术人也能写出有深度的回答
  • 实用指南:C语言速成秘籍——循环结构(while、do while、for)和跳转语句(break,continue)
  • 描述https的加密过程
  • CSP-S 2025 提高级模拟赛 Day6 复盘 A.选择方案
  • SSL证书批量申请终极指南:一次搞定所有域名
  • npm install creat-vue命令使用报错解决方法
  • PDF转图片工具:基于PyQt5的完整实现与深度解析 - 详解
  • MongoDB安装及使用
  • 从Gemini Robotics看通用机器人的科技路径
  • 张量的基本操作
  • Windows7 隐藏用户
  • 10 月记录
  • 统计学习方法学习Day01
  • gpt-5-codex vs gpt-5
  • Jenkins Share Library开发入门(一)
  • 第十三篇
  • 虚树
  • 网络安全基础--第五课:跨站脚本攻击XSS - 实践
  • 成员内部类
  • 用 Fortran 进行英文数字验证码识别