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

CF558C Amr and Chemistry BFS解

发现没人写 BFS,于是写了。

感谢 wenmingge 的教学,答题思路是他的,但是不知道他是怎么实现的。

题意

给你 \(n\) 个正整数,可以将任意一个数字 \(x\) 变换为 \(2x\)\(\lfloor \frac{x}{2}\rfloor\),一次变换记为一次操作,现要求进行若干次操作使得所有 \(n\) 个数字相等,输出最小操作次数。

寻思

注意到操作对每个数字所带来的新状态数量都是 \(\log_{n}\) 级别的(因为乘和除的数都是 \(2\)),也就是如果我们将每个数字的所有可能出现的状态搜索出来,那么每次搜索的复杂度都应该是 \(O(\log_{n})\) 级别。

又注意到:\(n\) 的范围只有 \(1\le n \le10^5\),这样只要我们对每个数字做一遍 \(O(\log_{n})\) 的 BFS,之后 \(O(n)\) 统计答案即可。

这样,剩下的问题就只是如何把 BFS 限制到\(O(\log_{n})\) 级别了。

做法总结

对每个数(下文称为原始数字)做 BFS,搜索出来他们可能扩展出来的所有数字,记录所有原始数字到这一个数字的最小操作数。

搜索时还要记录 \(cnt\) 数组为“每个数字可以被多少个原始数字扩展到”。

搜完后扫一遍 \(cnt\) 数组,只有满足 \(cnt_i = n\)\(i\) 才考虑,也就是这个数要能被所有的原始数字扩展到才可能成为答案。

然后就是最关键的问题:如何把 BFS 限制到 \(O(\log_{n})\)

BFS 时判重有两种写法:

  • 记录距离数组,以 \(dist_i\) 是否有值来判断。
  • 记录访问数组,以 \(vis_i\) 是否为正来判断。

但是很可惜,我们要做 \(n\) 遍 BFS。而要实现上面的做法要么在每次 BFS 时都清空相关数组,要么开 \(n\) 个相关数组来供每次 BFS 使用。

而前者的时间复杂度是 \(O(n)\),后者的空间复杂度是 \(O(n^2)\),这都是我们不可接受的。

所以这里给出一种做法:时间戳判重

记录访问数组的方式判重,把访问数组开成整型,在每次 BFS 时给一个唯一的编号,在搜到一个新的数字时不再判断“是否为真”,而是“访问编号是否为当前的编号”,记录同理。这样就可以规避每次 BFS 时都清空访问数组,将每次 BFS 的时间复杂度控制在 \(O(\log_{n})\)

时间复杂度\(O(n\log_{n})\),空间复杂度\(O(n)\)

// Problem: CF558C Amr and Chemistry
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF558C
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Time: 2025-10-05 08:44:56#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef pair<int, int> PII;
typedef long long LL;// 觉得应该开就开了int n;
int cnt[maxn];// 记录这个数字能被多少原始数字扩展到
LL a[maxn];
LL dist[maxn];// 所有原始数字(注意)到这一个数字的最小操作数。
int vis[maxn], timestamp;// 访问数组与时间戳void bfs(LL sta)
{queue<PII> q;q.push({sta, 0});timestamp ++;// 给 BFS 一个唯一的编号(时间戳)vis[sta] = timestamp;cnt[sta] ++;while(q.size()){//auto [u, dis] = q.front(); q.pop();auto t = q.front(); q.pop();int u = t.first, dis = t.second;//dis 为当前这个数被当前原始数字扩展的最小操作数for(int i = 0 ; i < 2 ; i ++)// 因为是两个操作{LL ne = u;if(!i) ne *= 2;else ne /= 2;if(ne >= 1 && ne <= maxn && vis[ne] != timestamp)// 用时间戳来判重{vis[ne] = timestamp;dist[ne] += dis + 1;// 注意是 +=, 因为记录的是"所有"原始数字到这一个数字的最小操作数cnt[ne] ++;//ne 可以被这个原始数字搜到q.push({ne, dis+1});}}}
}signed main()
{ios::sync_with_stdio(false); cin.tie(nullptr);cin >> n;for(int i = 1 ; i <= n ; i ++)cin >> a[i];for(int i = 1 ; i <= n ; i ++)bfs(a[i]);LL mn = LLONG_MAX;// 注意!当然你用 INT_MAX 我觉得也不会错就是了。for(int i = 1 ; i < maxn ; i ++)if(cnt[i] == n)// 数字 i 能被所有 n 个数字扩展到mn = min(mn, dist[i]);// 记录最小的操作数cout << mn;
}

垃圾话

第一篇题解,希望你看的开心,有问题欢迎留言。

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

相关文章:

  • Atbash密码和摩斯密码
  • Redis 中如何保证缓存与数据库的内容一致性?
  • Payload CMS:开发者优先的Next.js原生开源解决优秀的方案,重新定义无头内容管理
  • 第一次写博客
  • 07. 自定义组件
  • python语法记录
  • 2025 年储罐厂家推荐最新公司权威排行榜榜单发布,深度解析衬四氟储罐 / 硫酸储罐 / 盐酸储罐工厂选购指南
  • UnicodeEncodeError: locale codec cant encode character \u5e74 in position 2: encoding error
  • 2025 年生物除臭设备厂家最新推荐排行榜:覆盖污水处理厂 / 垃圾中转站等多场景,助力企业精准挑选优质设备
  • 2025 年球墨铸铁管公司:重庆南恩物资全品类管材供应与市政工程适配解决方案解析
  • 2025生物除臭设备厂家最新品牌企业推荐排行榜揭晓:印染厂污水,食品厂污水,污水处理厂,污水泵站,污水站,餐厨垃圾,屠宰场,厨余垃圾生物除臭设备公司推荐
  • 2025 工业加热器选型必看:六大加热器实力厂家深度推荐,覆盖多场景加热设备解决方案
  • YOLO模型部署
  • 从理念到沙盘:用悟空博弈模拟器点亮人机共治的曙光
  • 深入解析:Redis事务详解:原理、使用与注意事项
  • phone num
  • Perplexity发布搜索API,驱动下一代AI应用开发
  • PWN手的成长之路-09-SWPUCTF 2023 秋季新生赛Shellcode
  • 20251005 总结
  • OKR1
  • 2025 年装盒机制造厂 TOP 企业品牌推荐排行榜,自动化 / 喷胶 / 牙膏 / 手机壳 / 3C 数码 / 内外盒 / 面膜 / 电子产品 / 玩具 / 日用品装盒机推荐这十家公司!
  • 英语_阅读_Chinas Spring Festival_待读
  • 2025 年自动包装生产线 TOP 企业品牌推荐排行榜!食品行业 / 日化产品 / 智能化 / 小型 / 多功能集成 / 柔性 / 后道 / 高速自动包装生产线推荐!
  • 题解:AT_arc181_e [ARC181E] Min and Max at the edge
  • 酵母单杂交实验:解密 “转录因子 - DNA 互作” 的核心工具
  • api调用钉钉群机器人发信息 - 规格严格
  • 2025 年氢氧化铝生产厂家 TOP 品牌榜单来袭,阻燃,高白,酸融,导热,超细,微粉级,低粘度,灌封胶用,覆铜板用氢氧化铝公司推荐!
  • 飞算 JavaAI 赋能老工程重构:破旧立新的高效利器
  • P14139 题解
  • AI 自我理解边界