暑期cspj模拟赛7

T1

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 检查字符串s是否以prefix为前缀
bool isPrefix(const string& s, const string& prefix) {
    if (s.length() < prefix.length()) {
        return false;
    }
    for (int i = 0; i < prefix.length(); ++i) {
        if (s[i] != prefix[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    freopen("prefix.in", "r", stdin);
    freopen("prefix.out", "w", stdout);

    string target;
    int n;
    
    // 读取目标字符串
    cin >> target;
    // 读取字符串数量
    cin >> n;
    
    vector<string> candidates;
    
    // 读取所有字符串并筛选出符合条件的
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        if (isPrefix(s, target)) {
            candidates.push_back(s);
        }
    }
    
    // 按字典序排序
    sort(candidates.begin(), candidates.end());
    
    // 输出字典序最小的字符串
    cout << candidates[0] << endl;
    
    return 0;
}

T2

一定是一只左右牵右手 所以最大的左手 牵最大的 右手 以此类推

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

int n;
int L[100010];
int R[100010];

int main() {
    freopen("seat.in", "r", stdin);
    freopen("seat.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> L[i] >> R[i];
	}

	sort(L + 1, L + n + 1);
	sort(R + 1, R + n + 1);

	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += max(L[i], R[i]);
	}
	cout << ans  + n << endl;

}

T3

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

const int N = 305;

int n, a, b, c;
int s[N];
long long dp[N][N];

// 区间DP求解消除游戏
long long solve() {
    for (int len = 1; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            
            // 情况1：单独消除s[l]
            dp[l][r] = dp[l+1][r] + a;
            
            // 情况2：与右边相同颜色的球一起消除
            for (int k = l + 1; k <= r; ++k) {
                if (s[k] == s[l]) {
                    // 消除s[l]和s[k]之间的区间，然后一起消除s[l]和s[k]
                    long long val = 0;
                    
                    // 计算左右两边的值
                    long long left_val = (l + 1 <= k - 1) ? dp[l+1][k-1] : 0;
                    long long right_val = (k + 1 <= r) ? dp[k+1][r] : 0;
                    
                    // 2个一起消除
                    if (k == l + 1) {
                        val = right_val + b;
                    } else {
                        val = left_val + right_val + b;
                    }
                    dp[l][r] = max(dp[l][r], val);
                    
                    // 3个一起消除的情况
                    for (int m = l + 1; m < k; ++m) {
                        if (s[m] == s[l]) {
                            long long val3 = 0;
                            if (l + 1 <= m - 1) val3 += dp[l+1][m-1];
                            if (m + 1 <= k - 1) val3 += dp[m+1][k-1];
                            if (k + 1 <= r) val3 += dp[k+1][r];
                            val3 += c;
                            dp[l][r] = max(dp[l][r], val3);
                        }
                    }
                }
            }
        }
    }
    
    return dp[1][n];
}

int main() {

    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);

    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
    }
    
    long long ans = solve();
    printf("%lld\n", ans);
    
    return 0;
}

T4

先考虑 每一个 a>b对，只要算出a之前小于b的个数 和b之后 大于a的个数，两者相乘累加即可

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

const int N = 5005;

int n, a[N];
long long ans;
short les[N][N];
short gre[N][N];

int main() {

    freopen("quater.in", "r", stdin);
    freopen("quater.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }


    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            les[i][j] = les[i - 1][j];
            if (a[i] < j) {
                les[i][j]++;
            }
        }
    }

    for (int i = n; i >= 1; --i) {
        for (int j = 1; j <= n; ++j) {
            gre[i][j] = gre[i + 1][j];
            if (a[i] > j) {
                gre[i][j]++;
            }
        }
    }


    for (int i = 2; i <= n; ++i) {
        for (int j = i+1; j < n; ++j) {
            if (a[i] > a[j]) {
                ans += 1LL*les[i-1][a[j]] * gre[j+1][a[i]];
            }
        }
    }

    printf("%lld\n", ans);

    return 0;
}