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

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

Easy 循环求和

简要题意

求 。

Solution

欲求题式，只需求：

Code

void R()
{
	auto f=[&](i64 n)->i64
	{
		return n&1?n-n/2:-n/2;
	};

	i64 l,r;
	cin>>l>>r;
	cout<<f(r)-f(l-1)<<'\n';
	return;
}

Medium 小美走公路

简要题意

给一个正权边构成的环，求给定两点间最短路。

Solution

记边权和为 ，不妨设 ，答案为 。

Code

void R()
{
	int n;
	cin>>n;
	vector<i64> a(n+1);
	for (int i=1;i<=n;i++)
		cin>>a[i];
	partial_sum(a.begin(),a.end(),a.begin());
	
	int x,y;
	cin>>x>>y;
	i64 d=a[max(x,y)-1]-a[min(x,y)-1];
	cout<<min(d,a.back()-d);
	return;
}

Hard 游游的除2操作

简要题意

给定一个数组，每次操作可以将一个数变为它自身除以 下取整。求令数组内各数相同需要的最小操作次数。

Solution

用 multiset 维护，一直取最大的操作至最大的与最小的相等。

Code

void R()
{
	int n,ans=0;
	cin>>n;
	multiset<int> s;
	while (n--)
	{
		int x;
		cin>>x;
		s.insert(x);
	}
	while (*s.begin()!=*s.rbegin())
	{
		ans++;
		s.insert(*s.rbegin()/2);
		s.erase(prev(s.end()));
	}
	cout<<ans;
	return;
}