专栏文章

题解:CF558C Amr and Chemistry

CF558C题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miovj4n1
此快照首次捕获于
2025/12/03 01:50
3 个月前
此快照最后确认于
2025/12/03 01:50
3 个月前
查看原文

CF558C Amr and Chemistry

题目分析

观察题目,每次操作都可以将 aia_i 折半或乘 2,模拟这个过程仅需 log2n\log _2 n 次,所以 BFS 完全可以,不用其他题解推荐的 01-Trie 或 dp。

具体思路

对于每一组样例,易得最终答案(数的值)不会超过 1×1051 \times 10^5,所以用 BFS 把每一个数可以得到的所有数记录下来,最后只需遍历一遍,找到最小的次数对应的一个数即可。要注意的是去重,然后 pair 的常数太大,建议用 struct(我因为 pair 套 pairTLE 了好久),时间复杂度 O(nlogn)O(n \log{n})AC 完全没问题

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N],num[N],sum[N],vis[N];
struct node
{
    int v,f,s;
};
void bfs(int s)
{
    queue<node> q;
    q.push({a[s],-1,0});
    while(!q.empty())
	{
        int u=q.front().v,f=q.front().f,t=q.front().s;
		q.pop();
        if(u==f || u>N || vis[u]==s) continue;
        vis[u]=s;
        num[u]++;
        sum[u]+=t;
        q.push({u*2,u,t+1});
        q.push({u/2,u,t+1});
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
	{
        cin>>a[i];
        bfs(i);
    }
    int ans=INT_MAX;
    for(int i=1;i<N;i++)
	{
        if(num[i]==n) 
			ans=min(ans,sum[i]); 
    }
    cout<<ans<<"\n";
    return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...