专栏文章

CF558C Amr and Chemistry BFS解

MMisaka2298
CF558C题解参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@minotlb5
此快照首次捕获于
2025/12/02 05:55
3 个月前
此快照最后确认于
2025/12/02 05:55
3 个月前
查看原文
发现没人写 BFS,于是写了。
感谢 wenmingge 的教学，答题思路是他的，但是不知道他是怎么实现的。
在我的博客中阅读
题目链接 (Luogu)

题意

给你 nn 个正整数，可以将任意一个数字 xx 变换为 2x2x 或 ⌊x2⌋\lfloor \frac{x}{2}\rfloor，一次变换记为一次操作，现要求进行若干次操作使得所有 nn 个数字相等，输出最小操作次数。
更形式化的题面
给你一个长度为 n(1≤n≤105)n(1\le n \le 10^5) 的数列 AA，其中任意 Ai(1≤i≤n)A_i(1\le i \le n) 满足 1≤Ai≤1051 \le A_i \le 10^5，对于任意 AiA_i 可执行以下操作：
  • Ai=Ai×2A_i = A_i \times 2
  • Ai=⌊Ai2⌋A_i = \lfloor \frac{A_i}{2}\rfloor
求找到一个正整数 t≥1t \ge 1，使得对数列 AA 进行 tt 次操作后满足任意 Ai=Aj(1≤i,j≤n)A_i = A_j(1 \le i,j \le n) 且最小化 tt。

寻思

注意到操作对每个数字所带来的新状态数量都是 log⁡n\log_{n} 级别的（因为乘和除的数都是 22），也就是如果我们将每个数字的所有可能出现的状态搜索出来，那么每次搜索的复杂度都应该是 O(log⁡n)O(\log_{n}) 级别。
又注意到：nn 的范围只有 1≤n≤1051\le n \le10^5,这样只要我们对每个数字做一遍 O(log⁡n)O(\log_{n}) 的 BFS，之后 O(n)O(n) 统计答案即可。
这样，剩下的问题就只是如何把 BFS 限制到 O(log⁡n)O(\log_{n}) 级别了。

做法总结

对每个数（下文称为原始数字）做 BFS，搜索出来他们可能扩展出来的所有数字，记录所有原始数字到这一个数字的最小操作数。
搜索时还要记录 cntcnt 数组为“每个数字可以被多少个原始数字扩展到”。
搜完后扫一遍 cntcnt 数组，只有满足 cnti=ncnt_i = n 的 ii 才考虑，也就是这个数要能被所有的原始数字扩展到才可能成为答案。
然后就是最关键的问题：如何把 BFS 限制到 O(log⁡n)O(\log_{n})？
BFS 时判重有两种写法：
  • 记录距离数组，以 distidist_i 是否有值来判断。
  • 记录访问数组，以 visivis_i 是否为正来判断。
但是很可惜，我们要做 nn 遍 BFS。而要实现上面的做法要么在每次 BFS 时都清空相关数组，要么开 nn 个相关数组来供每次 BFS 使用。
而前者的时间复杂度是 O(n)O(n)，后者的空间复杂度是 O(n2)O(n^2)，这都是我们不可接受的。
所以这里给出一种做法：时间戳判重。
以记录访问数组的方式判重，把访问数组开成整型，在每次 BFS 时给一个唯一的编号，在搜到一个新的数字时不再判断“是否为真”，而是“访问编号是否为当前的编号”，记录同理。这样就可以规避每次 BFS 时都清空访问数组，将每次 BFS 的时间复杂度控制在 O(log⁡n)O(\log_{n})。
时间复杂度O(nlog⁡n)O(n\log_{n})，空间复杂度O(n)O(n)。
其中时间复杂度中 log⁡\log 上的那个 nn 一定为 maxnmaxn，不受输入 nn 的大小影响。

码

CPP
// 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;
}

垃圾话

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

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...