1927(923div3)

A. Make it White

只需要计算两边连续的白色，涂中间的即可。

void solve() {
    int n;
    string a;
    cin >> n >> a;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0;i < a.size();i++) {
        if (a[i] != 'W')break;
        else cnt1++;
    }
    for (int i = a.size() - 1;i >= 0;i--) {
        if (a[i] != 'W')break;
        else cnt2++;
    }
    cout << n - cnt1 - cnt2 << '\n';
}

B. Following the String

波利卡普丢失了由小写拉丁字母组成的长度为 \(n\) 的字符串 \(s\) ，但他仍然保留着它的痕迹。

字符串 \(s\) 的踪迹是一个由 \(n\) 个整数组成的数组 \(a\) ，其中 \(a_i\) 是 \(s_i=s_j\) 的索引 \(j\) （ \(j < i\) ）的个数。例如，字符串 abracadabra 的踪迹是数组 [ \(0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4\) ]。

给定一个字符串的踪迹，从中找出个字符串 \(s\) 。字符串 \(s\) 应该只由小写字母 \(a-z\) 组成。

tmp.first 记录下 某数字 的个数，tmp.second 记录该数组中所有等于 某数字 的下标

对于每个 tmp. second (这时每个下标的字母是不同的)，只需要从 a 开始一直枚举即可。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<char> s(n);
    vector<pair<int, list<int>>> tmp(n);
    for (int i = 0;i < n;i++) {
        cin >> a[i];
        tmp[a[i]].first++;
        tmp[a[i]].second.push_back(i);
    }
    
    for (auto [x, y] : tmp) {
        char ch = 'a';
        for (auto z : y) {
            s[z] = ch++;
        }
    }
    for (auto x : s)cout << x;
    cout << '\n';
}

C. Choose the Different Ones!

是否能从 \(a,b\) 数组中各选 \(\frac{k}{2}\) 个数字使得刚好能组成 \(1-k\)

如果 \(1-k\) 中某数字没有，就肯定不可能，如果 \(1-k\) 都有，且 \(a,b\) 中都至少涉及到了一半的数字，则可以，否则不可能。

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    set<int> a, b;
    for (int i = 0;i < n;i++) {
        int x;cin >> x;
        a.insert(x);
    }
    for (int i = 0;i < m;i++) {
        int x;cin >> x;
        b.insert(x);
    }
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1;i <= k;i++) {
        if (a.count(i))cnt1++;
        if (b.count(i))cnt2++;
        if (!a.count(i) && !b.count(i)) {
            cout << "no\n";return;
        }
    }
    if (cnt1 >= k / 2 && cnt2 >= k / 2) {
        cout << "yes\n";
    } else {
        cout << "no\n";
    }
}

D. Find the Different Ones!

对于一个 \(a\) 数组，有 \(q\) 次询问：

对于每次询问 \([l,r]\),观察 \([l,r]\) 中是否存在两个数字不同

若存在，输出这两个下标，若不存在输出 -1 -1

只需要计算出 \(a_{i}\) 右边第一个和 \(a_{i}\) 不同的下标即可。

若 \(a_{i}\) 右边没有与 \(a_{i}\) 相同的，则不存在
若 \(a_{i}\) 右边有与 \(a_{i}\) 相同的，但是超出了 \(r\)，则不存在
否则，存在

void solve() {
    int n, q;
    cin >> n;
    vector<int> a(n);
    vector<int> left(n), right(n);

    for (int i = 0;i < n;i++) {
        cin >> a[i];
    }
    // left[0] = -1;//a[i]左边第一个和a[i]不同的下标
    // for (int i = 1;i < n;i++) {
    //     if (a[i] == a[i - 1]) {
    //         left[i] = left[i - 1];
    //     } else {
    //         left[i] = i - 1;
    //     }
    // }
    right[n - 1] = -1;
    for (int i = n - 2;i >= 0;i--) {
        if (a[i] == a[i + 1]) {
            right[i] = right[i + 1];
        } else {
            right[i] = i + 1;
        }
    }

    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        if (right[l] != -1 && right[l] <= r) {
            cout << l + 1 << " " << right[l] + 1 << '\n';
        } else {
            cout << "-1 -1\n";
        }
    }
    cout << '\n';
}

E. Klever Permutation

给你两个整数 \(n\) 和 \(k\) ( \(k \le n\) )，其中 \(k\) 是偶数。

你的任务是构造一个长度为 \(n\) 的 \(k\) 级排列。(k-level)

如果在所有长度为 \(k\) 的连续线段的总和中（其中正好有 \(n - k + 1\) 个线段），那么这个排列就叫做 \(k\) 级排列。(其中正好有 \(n - k + 1\) 个），任意两个和相差不超过 \(1\) ，那么这个排列就叫做 \(k\) 级排列。

\(k\) 级序列，首先构造一个长度为 \(n - k + 1\) 的数组 \(s\) ，其中 \(s_i=\sum_{j=i}^{i+k-1} p_j\) ，即 \(i\) /th 元素等于 \(p_i, p_{i+1}, \dots, p_{i+k-1}\) 的和。

有： \(\max(s) - \min(s) \le 1\) .

找出长度为 \(n\) 的任意个 \(k\) 级排列。

Solution

Jiangly

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    int cnt = 0;
    for (int i = 0;i < k;i++) {
        if (i % 2 == 0) {
            for (int j = i;j < n;j += k) {
                a[j] = ++cnt;
            }
        } else {
            for (int j = (n - 1) - (n - 1 - i) % k;j >= 0;j-=k) {
                a[j] = ++cnt;
            }
        }
    }
    for (auto x : a) {
        cout << x << " ";
    }
    cout << '\n';
}

FXJFXJ