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

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

Easy 统计每个月兔子的总数

简要题意

求斐波那契数列第 项。

Solution

数据范围很小，直接递推。

Code

void R()
{
	vector<int> f(32);
	f[1]=f[2]=1;
	for (int i=3;i<32;i++)
		f[i]=f[i-1]+f[i-2];

	int n;
	cin>>n;
	cout<<f[n];
	return;
}

Medium 高精度整数加法

简要题意

如题。

Solution

直接模拟，各位相加后处理进位。为了方便进位可以先倒着存。

Code

void R()
{
	constexpr int MAXN=2e5+7;
	string s,t;
	vector<int> a(MAXN);
	cin>>s>>t;
	reverse(s.begin(),s.end());
	reverse(t.begin(),t.end());
	for (int i=0;i<s.size();i++)
		a[i]=s[i]-'0';
	for (int i=0;i<t.size();i++)
		a[i]+=t[i]-'0';
	for (int i=0;i<MAXN;i++)
		if (a[i]>=10)
		{
			a[i+1]+=a[i]/10;
			a[i]%=10;
		}
	while (a.size()>1&&!a.back())
		a.pop_back();
	for (int i=a.size()-1;i>=0;i--)
		cout<<a[i];
	return;
}

Hard 喜欢切数组的红

简要题意

求将一个数组分成三个非空子数组，使得三者内部元素和相等且都含有正数的方案数。

Solution

考虑第一个数组取前 位，第二个数组随后取到第 位，剩下的作为第三个数组。

这个数据范围暴力枚举 肯定是不行的。

先只考虑内部元素和相等的条件，怎么做？

我们预处理前缀和 ，约束相当于：。

于是我们扫一遍 ，维护 之前 的位置数 ，如果 就把答案加上 即可。

加上每个数组都含有正数的条件，怎么做？

记最左正数位置为 ，最右正数位置为 ，新增约束相当于：，以及中间数组含有正数。

我们把之前维护的： 之前 的位置数，换成： 之前 且 上没有/有正数的位置数。

遍历的时候遇到满足前缀和约束的位置先计入没有正数的贡献。遇到正数位置就把没有正数的贡献丢到有正数的贡献里，没有正数的贡献清空。

Code

void R()
{
	int n;
	cin>>n;
	vector<i64> a(n);
	for (i64 &x:a) cin>>x;

	int L=n,R=-1;
	for (int i=0;i<n;i++)
		if (a[i]>0)
		{
			R=i-1;
			L=min(L,i);
		}

	partial_sum(a.begin(),a.end(),a.begin());
	i64 pre=0,tmp=0,ans=0,S=a.back();

	for (int i=0;i<n-1;i++)
	{
		if (a[i]>(i?a[i-1]:0))
			pre+=tmp,tmp=0;
		if (a[i]*3==S*2&&i<=R)
			ans+=pre;
		if (a[i]*3==S&&i>=L)
			tmp++;
	}
	cout<<ans<<'\n';
	return;
}