活動(dòng)地址： 牛客春招刷題訓(xùn)練營(yíng) - 編程打卡活動(dòng)

簡(jiǎn)單題 小美的因子查詢

存在某個(gè)因子是偶數(shù)等價(jià)于 有一個(gè)因子是 。
直接判斷 能否被 整除。

#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;
}

中等題 跳臺(tái)階擴(kuò)展問(wèn)題

遞歸解法：
為跳上 級(jí)臺(tái)階的方案數(shù)。
不難得到

#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;
}

更優(yōu)的解法：
列出前幾項(xiàng)：。
猜測(cè)：。
證：。
所以從第 項(xiàng)開始就是等比數(shù)列。
注意 。
所以直接輸出 。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << (1 << (n - 1)) << '\n';
}

困難題 能量項(xiàng)鏈

又雙叒叕是區(qū)間dp。

設(shè) 是合并了 之間合并了所有珠子的能量值。這個(gè)區(qū)間合并后的珠子的頭標(biāo)記是 ，尾標(biāo)記是 ，注意是左閉右開區(qū)間，還有 可能小于 ，是因?yàn)閰^(qū)間跨越了 下標(biāo)，是由 和 這兩段拼起來(lái)的。
仍然是按長(zhǎng)度從短到長(zhǎng)枚舉， 從 枚舉到 。
枚舉區(qū)間端點(diǎn)時(shí)，因?yàn)檫@是一個(gè)環(huán)，所以訪問(wèn)數(shù)組下標(biāo)時(shí)需要對(duì) 取模，即 。
枚舉斷點(diǎn) ，表示 和 合并了， 的取值應(yīng)屬于 ，再取模 。
因?yàn)閐p表示的區(qū)間是左閉右開區(qū)間，轉(zhuǎn)移方程：
。
注意轉(zhuǎn)移過(guò)程中不要取模！long long 足夠存下最大值。
最后輸出 的最大值。
fun fact：本題答案不用對(duì) 取模也能通過(guò)……

#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;
}