Codeforces Round 877 (Div. 2)

传送门：Codeforces Round 877 (Div. 2)

A. Blackboard List

题意：

​ 给定包含两个数字的初始，然后进行 $n-2$ 次操作，每次操作从序列中取出两个数字（不能取同一个），将其差之绝对值加入序列，最终得到一长度为 $n$ 的序列。

​ 现给定最终序列（乱序）， 求最初始数字之一。

题解：

​ 由于新加入数字必为非负数，因此序列中的负数必定是初始数字。

​ 若全为非负数，由于 $|a-b|\leq|a|$ 且 $|a-b|\leq |b|$ ，因此最大数字必为初始数字。

B. Minimize Permutation Subarrays

题意：

​ 给定一 $n$ 的排列。交换两数字的位置，使得交换后序列中，能够成排列的连续子序列数目最少。

题解：

​ $1$ 与 $2$ 之间夹 $n$ ，这样能够使得数目恒为 $1$ ，是为最少。讨论即可

C. No Prime Differences

题意：

​ 将 $nm$ 之内的正整数排成一个 $nm$ 矩阵，使得矩阵中任意两相邻元素差值的绝对值不为素数。

题解：

​ 先考虑 $m\geq 5$ 时，将 $\{0, 1n, 2n, 3n, … (m-1)n\}$ 排成一列。以下是一种合适的构造方法。

​ 设 $p=\lfloor \frac{m-1}{2}\rfloor$ 考虑两个序列

$$\{0, 1*n, 2*n, ...p*n \} \\ \{(p+1)*n, (p+2)*n, ... (m-1)*n\}$$

​ 然后将两序列合成（下面序列的元素依次插入上面序列的空隙）。

​ 若 $m=4$ ，则可构造为 $\{1n, 3n, 0, 2*n\}$

​ 设该序列为 $A$ ，则最终矩阵可构造为 $p_{i, j}=i+A_j$

code：

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> add(m);
    int now = 0;
    for (int i = 0; i < m; i += 2) {
        add[i] = now;
        now += n;
    }
    for (int i = 1; i < m; i += 2) {
        add[i] = now;
        now += n;
    }
    if (m == 4) {
        add[0] = n;
        add[1] = 3 * n;
        add[2] = 0;
        add[3] = 2 * n;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) cout << i + add[j] << ' ';
        cout << endl;
    }
}

D. Bracket Walk

题意：

​ 一括号序列，从最左侧出发可以随意向左右移动（不超边界），最终停在最右侧。途经符号构成一括号序列，若该括号序列合法，则称原序列 walkable 。

​ 现给定一括号序列 $s$ ， $q$ 次单点修改，要求求出每次单点修改后，序列是否 walkable 。

题解：

​ walkable 的必要条件首先是长度 $n$ 为偶数。

​ 其次构造一序列 $A$ ，包含所有的 $i$ ，使得

• $s_i=’)’$ 且 $i$ 为奇数

• $s_i=’(‘$ 且 $i$ 为偶数

  1. 若 $A$ 为空，则显然圆括号序列为 $()$ 重复若干次，必定 walkable。
  2. 若 $A$ 非空，其中最小数字为奇数，则意味着序列开头为 $()()()…())$ ，必定非法
  3. 若 $A$ 非空，其中最大数字为偶数，则意味着序列末尾为 $(()()()$ ，必定非法
  4. 剩余情况， $A$ 中最小数字 $m$ 为偶数， 最大数字 $M$ 为奇数，则 $m, M$ 之间符号数为偶数，其中左右括号奇偶性相同。则在 $m-1,m$ 这两个位置产生足够多的 $((….$ 来消除右侧的 $)$，然后在$M,M+1$ 两个位置产生对应数量的 $))$ 补齐即可。合法。

code：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, q;
    set<int> s;
    string str;
    cin >> n >> q;
    cin >> str;
    auto check = [&str](int p) {
        return ((str[p - 1] == '(') ^ (p & 1));
    };
    for (int i = 1; i <= n; i++) {
        if (check(i)) s.insert(i);
    }
    /*
     * 2 9
     * */
    int pos;
    while (q--) {
        cin >> pos;
        if (n & 1) {
            cout << "NO" << endl;
            continue;
        }
        if (check(pos)) s.erase(pos);
        else s.insert(pos);
        str[pos - 1] = '(' + ')' - str[pos - 1];
        if (s.empty()) cout << "YES" << endl;
        else if ((*s.begin() & 1) || !(*s.rbegin() & 1)) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
}

E. Count Supersequences

题意：

​ 求满足以下条件的 $b$ 序列个数：

• $b$ 序列含 $m$ 个正整数，所有数字均在 $[1,k]$ 内
• $b$ 序列删去若干个数，顺序不变，可以得到 $a$ 序列

题解：

​ 考虑 $dp$

​ $f[i][j]$ 表示含 $i$ 个正整数删去后可得到长度为 $j$ 的 $a$ 序列前缀的序列数，则有如下转移方程：

$$f[i][j]= \begin{cases} f[i-1][j-1]+(k-1)*f[i-1][j],\ j<n \\ f[i-1][j-1]+k*f[i-1][j], \ j=n \end{cases}$$

​ 发现该转移方程与 $a$ 无关。

​ 因此将 $a$ 序列设为 $n$ 个 $1$ ，然后作差法。

​ 最终答案为：

$$k^m-\sum_{i=0}^{n-1}\binom{m}{i}(k-1)^{m-i}$$

code：

void solve() {
    const long long mod = 1e9 + 7;
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1, x; i <= n; i++) cin >> x;
    auto quick_pow = [&mod](int a, int b) {
        int res = 1;
        for (; b; b >>= 1) {
            if (b & 1) res = 1ll * res * a % mod;
            a = 1ll * a * a % mod;
        }
        return res;
    };
    int ans = quick_pow(k, m);
    int now = 1;
    for (int i = 0; i < n; i++) {
        ans -= 1ll * now * quick_pow(k - 1, m - i) % mod;
        ans %= mod;
        ans += mod;
        ans %= mod;
        now = 1ll * now * (m - (i+1) + 1) % mod;
        now = 1ll * now * quick_pow((i+1), mod - 2) % mod;

    }
    cout << ans << endl;
}