# A

# 题目大意

给你一个长度为 $n$ 的二进制字符串 $s$ ，你需要做的是，对于第 $i$ 个字符，进行反转（ $0$ 变 $1$ ， $1$ 变 $0$ ），问，所有翻之后的字符串， $1$ 的总数是

# 数据范围

$t$ 组数据， $1 \le t \le 1000$
字符串长度 $n$ ， $1 \le n \le 10$

# 题解

暴力

C++

void solve () {
    cin >> n >> s;

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        // reverse i th
        for (int j = 0; j < n; j++) {
            if (j == i)
                cnt += (s[j] - '0' == 1 ? 0 : 1);
            else
                cnt += s[j] - '0';
        }
    }

    cout << cnt << endl;
}

# B

# 题目大意

给你一个长度为 $n$ 的排列（包括 $0$ 到 $n-1$ 的所有整数）和一个长度为 $n$ 的条状单元格
你需要在 $i$ 单元格内，填入 $MEX(p_1,p_2,...,p_i)$

$MEX(p_1,p_2,...,p_i)$ 代表 $p_1,p_2,...,p_i$ 中的第一个不出现的非负整数

现在给你一个最喜欢的数 $x$ ，问 $x$ 最多出现次数是？

# 数据范围

$t$ 组数据， $1 \le t \le 4000$
$1 \le n \le 2 \times 10^5$
$0 \le x \le n$

# 题解

构造题，只需要

把 $x$ 放在最后一个
小于 $x$ 的放最前面

大于

x

的放中间

C++

void solve () {
    cin >> n >> x;

    if (x >= n) {
        for (int i = 0; i <= n - 1; i++)
            cout << i << " ";
        cout << endl;
        return;
    }
    else {
        for (int i = 0; i < x; i++)
            cout << i << " ";
        for (int i = x + 1; i < n; i++)
            cout << i << " ";
        cout << x << endl;
    }
}

# C

# 题目大意

对于 $a_1,...,a_n$ 和 $b_1,...,b_n$ ，如果存在一个整数 $x$ ，使得对 $1 \le i \le n$ ，满足 $a_i+b_i=x$ ， $a$ 和 $b$ 就是 互补的
现在问题是， $b$ 数组丢失了一些元素（丢失的元素用 $-1$ 表示）
你需要计算，能够有多少不同的 $b$ ， $b$ 需要满足

$a$ 和 $b$ 是互补的
所有丢失元素都用不大于 $k$ 的非负整数代替

# 数据范围

$t$ 组数据， $1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le k \le 10^9$

# 题解

数据范围是 $2e5$
数据范围是 $2e5$
数据范围是 $2e5$

C++

void solve() {
    res = 1e18;
    int maxx = 0, minn = 1e18;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i], maxx = max(maxx, a[i]), minn = min(minn, a[i]);
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    for (int i = 1; i <= n; i++)
        if (a[i] != -1 && b[i] != -1) {
            if (res != 1e18 && res != a[i] + b[i]) {
                cout << 0 << endl;
                return;
            }
            res = a[i] + b[i];
        }

    if (res == 1e18) {
        cout << (k - maxx + minn + 1) << endl;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (a[i] > res) {
            cout << 0 << endl;
            return;
        }
        
        if (b[i] == -1) {
            if (res - a[i] > k) {
                cout << 0 << endl;
                return;
            }
        }
    }

    cout << 1 << endl;
}

# D

# 题目大意

给你 $n$ 朵花，第 $i$ 朵花的魅力程度是 $a_i$
你现在要收集 $m$ 朵花，你从 $a_1$ 走到 $a_n$ ，在收集的花中，第 $i$ 朵花的魅力程度至少是 $b_i$
你可能收集不到 $m$ 朵，所以你现在有一个魔法，在开始手机之前，你可以选取任意整数 $k$ ，在任意地方种出一朵魅力程度为 $k$ 的新花（你至多只能施展一次魔法）
你现在需要确定这样一个最小整数 $k$ （如果操作后能摘到 $m$ 朵花）

如果不操作就能得到，输出 $m$
如果不管怎么操作都得不到，则输出 $0$

# 数据范围

$t$ 组数据， $1 \le t \le 10^4$
$1 \le m \le n \le1 2 \times 10^5$

# 题解

先跑一遍前缀和后缀统计

pre[i] 表示前 $i$ 个里，最多能摘到多少个
suf[i] 表示从 $i$ 到 $n$ 个里，最多能摘到多少个
如果 pre[n] >= m ，代表不需要操作就可以摘到，那么输出 $0$

否则，扫一遍 $1 \to n$
对于第 $i$ 个点，我已经匹配了 pre[i] 个，也就是说，还差 m - pre[i] 个，我现在肯定不满足能全部摘到，但是我可以使用魔法
也就是说，如果在剩下的部分，如果我能摘到 m - pre[i] - 1 朵花的话，那么就代表一共可以摘到 $m$ 朵花
即需要插入 b[pre[i] + 1]

C++

void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];

    vector<int> pre(n + 2), suf(n + 2);
    pre[0] = 0, suf[n + 1] = 0;

    for (int i = 1; i <= n; i++) {
        if (pre[i - 1] < m && a[i] >= b[pre[i - 1] + 1])
            pre[i] = pre[i - 1] + 1;
        else
            pre[i] = pre[i - 1];
    }

    for (int i = n; i >= 1; i--) {
        if (suf[i + 1] < m && a[i] >= b[m - suf[i + 1]])
            suf[i] = suf[i + 1] + 1;
        else
            suf[i] = suf[i + 1];
    }

    if (pre[n] >= m) {
        cout << 0 << endl;
        return;
    }

    int res = 1e18;
    for (int i = 0; i <= n; i++)
        if (suf[i + 1] == m - pre[i] - 1)
            res = min(res, b[pre[i] + 1]);

    cout << (res == 1e18 ? -1 : res) << endl;
}

前缀和暴力 Div3 构造

# A

# 题目大意

# 数据范围

# 题解

# B

# 题目大意

# 数据范围

# 题解

# C

# 题目大意

# 数据范围

# 题解

# D

# 题目大意

# 数据范围

# 题解

连接分解

01背包