1930(div1+div2)

A. Maximise The Score

$2 \times n$ 个粉笔，2人依次选择两个粉笔 $s c o r e = min (a_{1}, a_{2})$ ，求能得到的最大分数

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(2 * n);
    for (int i = 0;i < 2 * n;i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0;i < 2 * n;i += 2) {
        ans += min(a[i], a[i + 1]);
    }
    cout << ans << '\n';
}

B. Permutation Printing

构造一个数组，满足 $a_{i} ∤ a_{j} o r a_{i + 1} ∤ a_{j + 1}$

void solve() {
    int n;cin >> n;
    vector<int> a(n);
    int m = 0;
    for (int i = 0;i < n;i += 2) {
        a[i] = n - m;
        a[i + 1] = 1 + m;m++;
    }
    for (auto i : a)cout << i << " ";cout << '\n';
}

C. Lexicographically Largest

堆栈有一个长度为 $n$ 的数组 $a$ 。他还有一个空集 $S$ 。请注意， $S$ 并***不是一个多集合。

他将进行以下三步操作恰好 $n$ 次：

选择一个索引 $i$ ，使得 $1 \leq i \leq | a |$ .
将 $^{†}$ 插入 $a_{i} + i$ 插入 $S$ 。
从 $a$ 中删除 $a_{i}$ 。注意， $a_{i}$ 右边所有元素的索引将减少 $1$ 。

注意， $n$ 操作后， $a$ 将为空。

现在，Stack 将构造一个新数组 $b$ ，这个数组是 $S$ 按递减顺序排列。形式上， $b$ 是一个大小为 $| S |$ 的数组，其中 $b_{i}$ 是所有 $1 \leq i \leq | S |$ 中 $S$ 的 $i$ 个最大元素。

求 Stack 字典序最大的 $b$ 。

Solution

我的想法是用 map<int, vector<int>> 存储 a[i] + 1 + i 一样的序列，如果各不相同，直接从最后往前面贪心，对于相同的序列就将序列倒过来，都加上最小的序号 (待更 $\dots$ )(看来应该是做不了 $\dots$ )

由题目给出的样例，可以知道，肯定不会有数字和别的重合，不然不可能是字典序最大，因此答案数组的大小一定是 $n$

从最大值到最小值贪心，先得到最大值，如果后面出现两个相等的情况，则将较小的数减一即可。(即将这个数字向前一位后再取走)

void solve() {
    int n;cin >> n;vector<int> a(n), b(n);
    for (int i = 0;i < n;i++) {
        cin >> a[i];a[i] += i + 1;
    }
    sort(a.rbegin(), a.rend());
    cout << a[0] << " ";
    for (int i = 1;i < n;i++) {
        a[i] = min(a[i], a[i - 1] - 1);
        cout << a[i] << " \n"[i == n - 1];
    }
}

D1/D2 Sum over all Substrings

int f(string s) {
    int ans = 0;
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '1') {
            ans++;i += 2;
        }
    }
    return ans;
}
void solve() {
    int n;cin >> n;
    string s;
    cin >> s;
    int sum = 0;
    for (int i = 0; i < n; i++) 
        for (int j = i; j < n; j++) 
            sum += f(s.substr(i, j - i + 1));
    cout << sum << '\n';
}