CF558C Amr and Chemistry BFS解

· · 题解

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

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

在我的博客中阅读

题目链接 (Luogu)

题意

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

::::info[更形式化的题面] 给你一个长度为 n(1\le n \le 10^5) 的数列 A，其中任意 A_i(1\le i \le n) 满足 1 \le A_i \le 10^5，对于任意 A_i 可执行以下操作：

求找到一个正整数 t \ge 1，使得对数列 A 进行 t 次操作后满足任意 A_i = A_j(1 \le i,j \le n) 且最小化 t。 ::::

寻思

注意到操作对每个数字所带来的新状态数量都是 \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 时判重有两种写法：

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

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

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

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

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

其中时间复杂度中 \log 上的那个 n 一定为 maxn，不受输入 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;
}

垃圾话

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