“蔚来杯“2022牛客暑期多校训练营2 G、J、K

J

本质是个线性回归方程，高考数学概率期望题常考，要自己定义x，y坐标

AC代码：

#include 
#define rep(i,a,n) for(int i=a;i
using namespace std;
using LL = long long;
 
void Solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    LL sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum1 += a[i];//y
        sum2 += i;//x
    }
    double cnt1, cnt2;
    cnt1 = 1.0 * sum1 / n;//y
    cnt2 = 1.0 * sum2 / n;//x
    double x = 0.0, y = 0.0;
    for (int i = 1; i <= n; i++) {
        x += (a[i] - cnt1) * (i - cnt2);//y x
        y += (i - cnt2) * (i - cnt2);//x x
    }
    double B = x / y, C;
    C = cnt1 - B * cnt2;
    double ans = 0.0;
    for (int i = 1; i <= n; i++) {
        ans += (B * i + C - a[i]) * (B * i + C - a[i]);
    }
    cout << fixed << setprecision(10) << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    rep (i, 0, T) {
        Solve();
    }
 
    return 0;
}

G

求最长上升子序列和最长下降子序列的最长长度最小，就定义一个长度为n的上取整，可得最长长度最小

AC代码：

#include 
#define rep(i,a,n) for(int i=a;i
using namespace std;
using LL = long long;
 
void Solve() {
    int n;
    cin >> n;
    int len = ceil(sqrt(n));
    int cnt = 0;
    while (cnt + len <= n) {
        cnt += len;
        for (int i = 0, j = cnt; i < len; i++, j--) {
            cout << j << " ";
        }
    }
    if (cnt == n) {
        cout << '\n';
    }
    else {
        for (int i = n; i > cnt; i--) {
            cout << i << " \n"[i == cnt + 1];
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    rep (i, 0, T) {
        Solve();
    }
    
    return 0;
}

K

表示前i位匹配j个且左括号比右括号多k个的方案数

AC代码：

#include 
#define rep(i,a,n) for(int i=a;i
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
 
int n, m, dp[210][210][210];//m->b,n->a
void Solve() {
    cin >> n >> m;
    memset(dp, 0, sizeof(dp));
    string s;
    cin >> s;
    s = ' ' + s + ' ';
    dp[0][0][0] = 1;//empty
    for (int i = 0; i < m; i++) {//b
        for (int j = 0; j <= n; j++) {//a
            for (int k = 0; k <= i; k++) {//cnt->(
                if (!dp[i][j][k]) {//error
                    continue;
                }
                if (s[j + 1] == '(') {//(
                    dp[i + 1][j + 1][k + 1] = (dp[i][j][k] + dp[i + 1][j + 1][k + 1]) % mod;
                }
                else {
                    dp[i + 1][j][k + 1] = (dp[i][j][k] + dp[i + 1][j][k + 1]) % mod;
                }
                if (k) {//)
                    if (s[j + 1] == ')') {
                        dp[i + 1][j + 1][k - 1] = (dp[i][j][k] + dp[i + 1][j + 1][k - 1]) % mod;
                    }
                    else {
                        dp[i + 1][j][k - 1] = (dp[i][j][k] + dp[i + 1][j][k - 1]) % mod;
                    }
                }
            }
        }
    }
    cout << dp[m][n][0] << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    rep (i, 0, T) {
        Solve();
    }
    
    return 0;
}