1930(div1+div2)

A. Maximise The Score

2×n 个粉笔,2人依次选择两个粉笔 score=min(a1,a2),求能得到的最大分数

#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

构造一个数组,满足 aiaj or ai+1aj+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 次:

  1. 选择一个索引 i ,使得 1i|a| .
  2. 插入 ai+i 插入 S
  3. a 中删除 ai 。注意, ai 右边所有元素的索引将减少 1

注意, n 操作后, a 将为空。

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

求 Stack 字典序最大的 b

Solution

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

由题目给出的样例,可以知道,肯定不会有数字和别的重合,不然不可能是字典序最大,因此答案数组的大小一定是 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';
}