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

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

Easy 小美的因子查询

简要题意

给一个正数 ，问其是否有偶因子。

Solution

正数有偶因子等价于为偶数。

Code

void R()
{
	int n;
	cin>>n;
	cout<<((n&1)?"NO":"YES")<<'\n';
	return;
}

Medium 跳台阶扩展问题

简要题意

一只青蛙每次可以向上跳任意（正整数）层台阶，求跳到第 层台阶的方案数。

Solution

记 为第 层方案数，有转移：

不难发现 。

Code

void R()
{
	int n;
	cin>>n;
	cout<<(1<<n-1);
	return;
}

Hard 能量项链

简要题意

给一个长度为 的循环数组，反复执行下面的操作 次：

任选一个数 ，记其前后的数分别为 ，获得 的得分，并将 从数组中删去。

求得分的最大值。

Solution

先介绍一个处理环的技巧：把数组复制一遍，考虑每个 长子数组的答案，相当于考虑环的答案。

设 表示为子数组 的最大得分，有转移：

即为答案。

Code

void R()
{
	constexpr int P=1e9+7;
	int n;
	cin>>n;
	vector<i64> a(n);
	vector<vector<i64>> dp(n*2,vector<i64>(n*2,-1));
	for (i64 &x:a) cin>>x;
	a.insert(a.end(),a.begin(),a.end());
	
	auto dfs=[&](auto &self,int l,int r)->i64
	{
		if (l+1>=r) return 0;
		if (dp[l][r]!=-1) return dp[l][r];
		for (int i=l+1;i<r;i++)
			dp[l][r]=max(dp[l][r],self(self,l,i)+a[l]*a[i]*a[r]+self(self,i,r));
		return dp[l][r];
	};

	i64 ans=0;
	for (int i=0;i<n;i++)
		ans=max(ans,dfs(dfs,i,n+i));
	cout<<ans%P;
	return;
}