牛客春招刷题训练营 - 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;
}
#牛客春招刷题训练营#