牛客春招刷题训练营 - 2025.5.23 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 小红吃药

简要题意

有 种症状 种药，每种药服用后会先治愈若干种疾病，再带来若干种疾病，现按顺序服用 次药，求每次服药后的疾病数。

Solution

把当且有的疾病 串记作 ，给定药物的治愈/带来疾病 串分别记作 ，则服药后的疾病 串 。

Code

void R()
{
	map<pair<int,int>,bool> vis;
	int X,Y,ans=-1;
	cin>>X>>Y;
	queue<tuple<int,int,int>> q;
	vis[{X,Y}]=1;
	q.push({X,Y,0});
	while (!q.empty())
	{
		auto [x,y,d]=q.front();
		q.pop();
		if (x==y)
		{
			ans=d;
			break;
		}
		if (!vis.count({y,x}))
			vis[{y,x}]=1,q.push({y,x,d+1});
		if (!vis.count({x+y,x-y})&&abs(x+y)<=1000&&abs(x-y)<=1000)
			vis[{x+y,x-y}]=1,q.push({x+y,x-y,d+1});
	}
	cout<<ans;
	return;
}

Medium 小红和小紫的取素因子游戏

简要题意

给定一个数 ，两人轮流将当前数除去自身的一个质因子，求最后一步由谁完成。

Solution

不管怎么选取质因子，每次操作后当前数的质因子个数严格减一，所以直接分解质因数看奇偶性就好了。

Code

void R()
{
	int x,cnt=0;
	cin>>x;
	for (int i=2;i*i<=x;i++)
		while (x%i==0)
		{
			x/=i;
			cnt++;
		}
	if (x!=1) cnt++;
	cout<<(cnt&1?"kou":"yukari")<<'\n';
	return;
}

Hard 小红送外卖

简要题意

给定一张带权无向图，求点 到若干个点的最短路径长度和。

Solution

直接跑一遍 Dijkstra 就好了。

Code

void R()
{
	using pii=pair<int,int>;
	int n,m,q;
	cin>>n>>m>>q;
	vector<vector<pii>> adj(n);
	for (int i=0;i<m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		u--,v--;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}

	vector<int> d(n,1e9),vis(n);
	priority_queue<pii,vector<pii>,greater<pii>> que;
	d[0]=0;
	que.push({0,0});
	while (!que.empty())
	{
		auto [t,u]=que.top();
		que.pop();
		if (vis[u]) continue;
		vis[u]=1;
		for (auto [v,w]:adj[u])
			if (d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				que.push({d[v],v});
			}
	}

	i64 ans=0;
	while (q--)
	{
		int x;
		cin>>x;
		ans+=d[x-1];
	}
	cout<<ans*2;
	return;
}