牛客春招刷题训练营-2025.4.28题解
1 活动地址： 牛客春招刷题训练营 - 编程打卡活动
简单题 小美的因子查询
存在某个因子是偶数等价于
有一个因子是
。
直接判断 能否被
整除。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int x;
cin >> x;
cout << (x % 2 ? "NO" : "YES") << '\n';
}
return 0;
}
中等题 跳台阶扩展问题
递归解法：
为跳上
级台阶的方案数。
不难得到
#include <bits/stdc++.h>
using namespace std;
int f(int n) {
if(n == 0) return 1;
int res = 0;
for(int i = 0; i <= n - 1; i++)
res += f(i);
return res;
}
int main() {
int n;
cin >> n;
cout << f(n) << '\n';
return 0;
}
更优的解法：
列出前几项：。
猜测：。
证：。
所以从第 项开始就是等比数列。
注意 。
所以直接输出 。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
cout << (1 << (n - 1)) << '\n';
}
困难题 能量项链
又双叒叕是区间dp。
设 是合并了
之间合并了所有珠子的能量值。这个区间合并后的珠子的头标记是
，尾标记是
，注意是左闭右开区间，还有
可能小于
，是因为区间跨越了
下标，是由
和
这两段拼起来的。
仍然是按长度从短到长枚举， 从
枚举到
。
枚举区间端点时，因为这是一个环，所以访问数组下标时需要对 取模，即
。
枚举断点 ，表示
和
合并了，
的取值应属于
，再取模
。
因为dp表示的区间是左闭右开区间，转移方程：
。
注意转移过程中不要取模！long long 足够存下最大值。
最后输出 的最大值。
fun fact：本题答案不用对 取模也能通过……
#include <bits/stdc++.h>
using namespace std;
long long dp[202][202];
long long a[202];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n; i++) {
int l = i, r2 = i + len;
for (int j2 = i + 1; j2 < r_; j2++) {
int r = r2 % n;
int j = j2 % n;
dp[l][r] = max(dp[l][r % n], dp[l][j] + dp[j][r] + a[l] * a[j] * a[r]);
}
}
}
long long ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ans = max(ans, dp[i][j]);
}
}
cout << ans % 1000000007 << '\n';
return 0;
}
