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

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

Easy 小红的魔法药剂

简要题意

有 种药剂，可以花费 元买一支红色的第 种药剂。每种蓝色药剂可以由某其它两种的红色药剂配成，求得到 种药剂（红蓝皆可）至少需要多少钱。

Solution

每种药剂价格相当于自身红色药剂价格与两种用于合成它的红色药剂价格的最小值，求和即为答案。

Code

void R()
{
	int n,ans=0;
	cin>>n;
	vector<int> a(n);
	for (int &x:a) cin>>x;
	for (int i=0;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		x--,y--;
		ans+=min(a[i],a[x]+a[y]);
	}
	cout<<ans;
	return;
}

Medium 游游的字母翻倍

简要题意

给一个字符串与若干次操作。每次操作会选定一个区间，在区间内字符串的每个字母之后插入一个与其相同的字母，求最终串。

Solution

操作次数很少，暴力 insert() 即可。

Code

void R()
{
	int n,q;
	string s;
	cin>>n>>q>>s;
	while (q--)
	{
		int l,r;
		cin>>l>>r;
		l--,r--;
		for (int i=r;i>=l;i--)
			s.insert(i,1,s[i]);
	}
	cout<<s;
	return;
}

Hard 游游的数值距离

简要题意

找一对不含 的正整数 ，使 最小。

Solution

因为阶乘增长快，我们枚举 。

固定 之后，可以发现题式是关于 的凸函数，我们直接试取 ，特判一下等于 的情况即可。

Code

void R()
{
	i64 fac[14]={1};
	for (int i=1;i<14;i++)
		fac[i]=fac[i-1]*i;
	i64 n,ans1=1,ans2=1;
	cin>>n;

	for (i64 x=3;x<14;x++)
	{
		i64 t1=floorDiv(n,fac[x]-1),t2=ceilDiv(n,fac[x]-1);
		if (t1==2) t1--;
		if (t2==2) t2++;
		if (abs((fac[x]-1)*t1-n)<abs((fac[ans1]-1)*ans2-n))
			ans1=x,ans2=t1;
		if (abs((fac[x]-1)*t2-n)<abs((fac[ans1]-1)*ans2-n))
			ans1=x,ans2=t2;
	}
	cout<<ans1<<' '<<ans2;
	return;
}