CodeStar2023年春第5周周赛普及进阶组-JZTXT

T1：分段求平均数

本题难度中等，划分型DP问题。用 dp[i] 表示前 \(i\) 个数最少划分成几段，对 \(j = 1, 2, \cdots, i-1\) 判断从 \(a_j\) 到 \(a_i\) 划分成一段时，平均数是否为整数，如果是整数，就更新 \(dp[i] = \max(dp[i], dp[j-1]+1)\)

初始值: \(dp[i] = i\)

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    vector<int> s(n+1);
    rep(i, n) s[i+1] = s[i]+a[i];
    
    vector<int> dp(n+1);
    rep(i, n+1) dp[i] = i;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            if ((s[i]-s[j-1])%(i-j+1) == 0) {
                dp[i] = min(dp[i], dp[j-1]+1);
            }
        }
    }
    
    cout << dp[n] << '\n';
    
    return 0;
}

T2：余数的余数

本题难度较大，\(n \leqslant 10\) 直接枚举所有 \(a\) 的全排列即可。