2000(966div3)

A. Primary Task

德米特里在黑板上写下了 $t$ 个整数，这很好。他肯定自己丢失了其中一个重要的整数 $n$ ，这就不好了。

整数 $n$ 的形式是 $10^{x}$ ( $x \geq 2$ )，其中符号" ^ "表示指数化。出错了，德米特里在写重要整数时漏掉了符号" ^ "。例如，他应该写 $105$ 而不是整数 $10^{5}$ ，应该写 $10^{19}$ 而不是 $1019$ 。

德米特里想知道黑板上的整数哪些可能是重要整数，哪些不可能。

void solve() {
    string s;cin >> s;
    if (s.size() <= 2) {
        cout << "NO\n";return;
    }
    if (s[0] == '1' && s[1] == '0') {
        if (s[2] != '0') {
            if (s.size() == 3 && s[2] == '1') {
                cout << "NO\n";
            } else {
                cout << "YES\n";
            }
        } else {
            cout << "NO\n";
        }
    } else {
        cout << "NO\n";
    }
}

B. Seating in a Bus

在伯兰，一辆公共汽车由一排 $n$ 个座位组成，座位号从 $1$ 到 $n$ 。乘客上车时请务必遵守这些规则：

如果车上没有空座位，乘客可以坐在任何空座位上；
否则，乘客应坐在至少有一个邻座空闲的座位上。换句话说，只有当 $i - 1$ 或 $i + 1$ 中至少有一个座位有人时，乘客才能坐在索引为 $i$ （ $1 \leq i \leq n$ ）的座位上。

今天有 $n$ 位乘客上车。数组 $a$ 按时间顺序记录了他们的座位号。也就是说， $a_{1}$ 包含第一位乘客的座位号， $a_{2}$ - 第二位乘客的座位号，以此类推。

您知道数组 $a$ 的内容。确定是否所有乘客都遵循了建议。

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), mp(n + 10);
    for (int i = 1;i <= n;i++)cin >> a[i];
    mp[a[1]] = 1;
    for (int i = 2;i <= n;i++) {
        if (mp[a[i] + 1] || mp[a[i] - 1]) {
            mp[a[i]] = 1;
        } else {
            cout << "NO\n";return;
        }
    }
    cout << "YES\n";
}

C. Numeric String Template

克里斯蒂娜有一个由 $n$ 个整数组成的数组 $a$ ，称为模板。她还有 $m$ 个字符串，每个字符串都只由小写拉丁字母组成。这些字符串的编号从 $1$ 到 $m$ 。她想检查哪些字符串与模板匹配。

如果同时满足以下所有条件，则认为字符串 $s$ 与模板匹配：

字符串 $s$ 的长度等于数组 $a$ 中的元素个数。
来自 $a$ 的相同数字对应于来自 $s$ 的相同符号。因此，如果 $a_{i} = a_{j}$ ，那么 $s_{i} = s_{j}$ 为（ $1 \leq i, j \leq n$ ）。
来自 $s$ 的相同符号对应于来自 $a$ 的相同数字。因此，如果是 $s_{i} = s_{j}$ ，那么 $a_{i} = a_{j}$ 为（ $1 \leq i, j \leq n$ ）。

换句话说，字符串中的字符与数组中的元素必须一一对应。

乍一看是 $O (n^{2})$ 的，其实种类超过 26 种就不可能了，所以计算量是很少的

void solve() {
    int n;cin >> n;
    set<int>st;
    map<int, vector<int>>mp;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x, st.insert(x), mp[x].push_back(i);
    }
    vector<int> bt;
    for (auto [x, y] : mp) {
        bt.push_back(*y.begin());
    }

    int m;cin >> m;
    while (m--) {
        string s;cin >> s;
        if (s.size() != n || st.size() > 26) {
            cout << "NO\n";continue;
        }
        s = ' ' + s;
        int ok = 1;
        for (auto [x, y] : mp) {
            set<char>ss;
            for (auto z : y) {
                ss.insert(s[z]);
            }
            if (ss.size() != 1) {
                ok = 0;
            }
        }
        set<char>ss;
        for (auto t : bt) {
            ss.insert(s[t]);
        }
        if (ss.size() != bt.size()) {
            ok = 0;
        }

        if (ok) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

D. Right Left Wrong

弗拉德发现了一个由 $n$ 个单元格组成的长条，从左到右的编号为 $1$ 到 $n$ 。在第 $i$ 个单元格中，有一个正整数 $a_{i}$

其中所有 $s_{i}$ 都是 "L "或 "R"。

弗拉德邀请您尝试进行任意数量（可能为零）的运算，以获得尽可能高的分数。

在一次操作中，您可以选择两个索引 $l$ 和 $r$ ( $1 \leq l < r \leq n$ )，使得 $s_{l}$ = 'L'， $s_{r}$ = 'R'，然后执行以下操作：

将 $a_{l} + a_{l + 1} + \dots + a_{r - 1} + a_{r}$ 分数添加到当前分数中；
将所有 $l \leq i \leq r$ 的 $s_{i}$ 替换为'.'，这意味着您不能再选择这些索引。

最大得分是多少？

贪心的做，每次都尽量选最多即可。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
    string s;cin >> s;s = ' ' + s;
    vector<int> l, r;
    for (int i = 1;i <= n;i++) {
        if (s[i] == 'L')l.push_back(i);
    }
    for (int i = n;i >= 1;i--) {
        if (s[i] == 'R')r.push_back(i);
    }
    while (l.size() > r.size()) {
        l.pop_back();
    }
    while (r.size() > l.size()) {
        r.pop_back();
    }
    int ans = 0;
    for (int i = l.size() - 1;i >= 0;i--) {
        if (l[i] < r[i]) {
            ans += a[r[i]] - a[l[i] - 1];
        }
    }
    cout << ans << '\n';
}

E. Photoshoot for Gorillas

你非常喜欢大猩猩，所以决定为它们组织一次摄影活动。大猩猩生活在丛林中。丛林是由 $n$ 行和 $m$ 列组成的网格。 $w$ 只大猩猩同意参加拍摄，索引为 $i$ ( $1 \leq i \leq w$ ) 的大猩猩身高为 $a_{i}$ 。您希望将所有大猩猩放入网格的单元格中，使得每个单元格中的大猩猩数量不超过 1 只。

该排列的奇观等于边长为 $k$ 的所有子方格的奇观之和。

一个子方格的奇观等于该子方格中大猩猩的高度之和。

从所有合适的排列中，选择最大的排列。

Solution

其实就是计算每个单元格分别能够被计算几次，我这里想得太复杂了... 以后思维需要清晰一些

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define int long long
void solve() {
    int n, m, k;cin >> n >> m >> k;
    int w;cin >> w;
    vector<int> a(w);
    for (int i = 0;i < w;i++)cin >> a[i];
    vector<int> f;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            int res = (min(i, n - k) - max(0ll, i - k + 1) + 1) * (min(j, m - k) - max(0ll, j - k + 1) + 1);
            f.push_back(res);
        }
    }
    sort(a.rbegin(), a.rend());
    sort(f.rbegin(), f.rend());
    int ans = 0;
    for (int i = 0;i < w;i++) {
        ans += a[i] * f[i];
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
}

F. Color Rows and Columns

你们有 $n$ 个矩形，其中 $i$ 个矩形的宽度为 $a_{i}$ ，高度为 $b_{i}$ 。

您可以无限次地执行以下操作：选择一个矩形和其中的一个单元格，然后为其着色。

每次为任意一行或任意一列完全着色，你都可以获得 $1$ 分。您的任务是用尽可能少的操作获得至少 $k$ 分。

Solution

$d p_{i, j}$ 代表前 $i$ 个格子得到 $j$ 分所需的最少操作数

$d p_{i, j + k} = min (d p_{i, j + k}, d p_{i - 1, k})$ 代表的是本来在这之前得到了 $k$ 分，然后在对第 $i$ 个矩形进行操作，假设得到 $j$ 分，在这其中得到最小值。

对于一个矩形的操作方式是：看行和列，先得到行列小的那个分，这时相当于行/列这时减少了 1 ，再继续操作

void solve() {
    int n, tar;cin >> n >> tar;
    vector<vector<int>> dp(n + 1, vector<int>(tar + 1, 1e9));
    dp[0][0] = 0;

    for (int i = 1;i <= n;i++) {
        int x, y;cin >> x >> y;int xy = x + y;
        int cost = 0;
        for (int j = 0;j <= xy;j++) {
            for (int k = 0;k + j <= tar;k++) {
                dp[i][j + k] = min(dp[i][j + k], dp[i - 1][k] + cost);
            }
            if (j < xy) {
                if (x >= y) {
                    x--;cost += y;
                } else {
                    y--;cost += x;
                }
            }
        }
    }
    if (dp[n][tar] == 1e9)dp[n][tar] = -1;
    cout << dp[n][tar] << '\n';
}