牛客春招刷题训练营-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;
}