# Codeforces Round 1122 (Div. 3)

比赛链接:https://codeforces.com/contest/2266

## A. Good Contest

> **time limit per test: 1 second / memory limit per test: 256 megabytes**
> input: standard input / output: standard output
>
> The next programming contest has three problems and `n` participants.
> Problem `1` is easy, problem `2` is medium, and problem `3` is hard.
> A participant is called weak if they did not solve all three problems.
> Unfortunately, the scoreboard was lost. The only remaining information is an array `a` of length `3`, where `a_i` is the number of participants who solved problem `i`.
> Among all scoreboards consistent with this information, find the minimum possible number of weak participants.
>
> **Input**
> The first line contains an integer `t` (`1 <= t <= 3000`) — the number of test cases.
> The first line of each test case contains an integer `n` (`1 <= n <= 9`) — the number of participants.
> The second line of each test case contains three integers `a_1, a_2, a_3` (`0 <= a_i <= n`), where `a_i` is the number of participants who solved problem `i`.
>
> **Output**
> For each test case, print a single integer — the minimum possible number of weak participants.

题意大概是有三道题,有n个学生去写,如果一个学生没有全部写对就算`weak participants`,要求这个`weak participants`人数的最小值

令`p = 三道题中被写出最少的题的次数`

容易得到`n - p`就是答案

因为最多有`p`个人全对,那么剩下的必然不可能全对,`n - p`就是最大值

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> a(3);
        cin >> a[0] >> a[1] >> a[2];
        cout << n - min({a[0], a[1], a[2]}) << '\n';
    }
}
```

## B. Three Piles

> **time limit per test: 1 second / memory limit per test: 256 megabytes**
> input: standard input / output: standard output
>
> Alice and Bob are playing a game with three piles of stones. Initially, Alice has `a` stones, Bob has `b` stones, and the third pile contains `c` stones.
> Alice and Bob take turns, with Alice going first. On each turn, the current player may take any number of stones from the third pile, possibly zero, and add them to their own pile.
> If both players take zero stones on two consecutive turns, the game ends.
> Let `A` and `B` be the final numbers of stones Alice and Bob have, respectively. The score of the game is `|A - B|`.
> Alice wants to maximize the score, while Bob wants to minimize it. Assuming both players play optimally, find the final score.
>
> **Input**
> The first line contains an integer `t` (`1 <= t <= 10^4`) — the number of test cases.
> Each test case contains three integers `a`, `b`, and `c` (`0 <= a, b, c <= 10^9`) — the initial numbers of stones Alice has, Bob has, and the third pile has, respectively.
>
> **Output**
> For each test case, output one integer — the final score if both players play optimally.
> It is important to use a `64`-bit integer type, such as `long long` in C++.

题目翻译一下大概是这样的:

爱丽丝和鲍勃正在玩一个涉及三堆石头的游戏.最初,爱丽丝有`a`个石头,鲍勃有`b`个石头,第三堆中有`c`个石头

爱丽丝和鲍勃轮流行动,由爱丽丝先手.每轮,当前玩家可以从第三堆中取任意数量的石头(包括零个),并将它们加入自己的堆中

如果双方在连续两轮中都未取石头,游戏结束

设`A`和`B`分别表示爱丽丝和鲍勃最终拥有的石头数量.游戏得分是`|A - B|`

爱丽丝希望将得分最大化,而鲍勃希望将得分最小化.假设双方都采取最优策略,求最终得分

第三堆是双方唯一的石头来源,所以自己的石头只会越加越多,设爱丽丝一共取了`x`个,答案只可能在`x`的两个端点上产生.

1. 全取(`x = c`):第三堆空了,Bob只能取`0`,分数只能为`|a + c - b|`
2. 全不取(`x = 0`):若`a <= b`,Bob多取只会拉大差距,所以他会取`0`个,得到`|a - b|`;若`a > b`,Bob会减小差距,但此时`a - b < a + c - b`,即`|a - b|`本来就小于另一端,不影响答案

中间取法都会被Bob抵消到不超过这两端,所以答案就是两端取大:

`ans = max(|a - b|, |a - b + c|)`

> 代码里第二项写`c + a - b`没套`abs`,因为它为负时必定小于`|a - b|`

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        long long a, b, c;
        cin >> a >> b >> c;
        long long ans = max(llabs(a - b), c + a - b);
        cout << ans << '\n';
    }
}
```

## C. AND, OR, Sort!

> **time limit per test: 2 seconds / memory limit per test: 256 megabytes**
> input: standard input / output: standard output
>
> You are given a binary string `s` of length `n`.
> You may perform the following operation any number of times (possibly zero):
> choose an integer `i` (`1 <= i <= n`), and replace `s_i` with either the bitwise AND or the bitwise OR of `s_1, s_2, ..., s_i`.
> Note that the bitwise AND or the bitwise OR of a single element is equal to the element itself.
> Your goal is to make `s` sorted in non-decreasing order (that is `s_1 <= s_2 <= ... <= s_n`).
> Find the minimum number of operations required to sort `s` in non-decreasing order.
>
> **Input**
> The first line contains a single integer `t` (`1 <= t <= 10^4`) — the number of test cases.
> The first line of each test case contains a single integer `n` (`2 <= n <= 2*10^5`) — the length of the binary string `s`.
> The second line of each test case contains the binary string `s` of length `n`. Each character of `s` is either `0` or `1`.
> It is guaranteed that the sum of `n` over all test cases does not exceed `2*10^5`.
>
> **Output**
> For each test case, print a single integer — the minimum number of operations required to sort `s` in non-decreasing order.

这道题给了两种操作,一种是`AND`一种是`OR`

要求把一个二进制字符串变成非递减排序的(也就是递增排序),答案格式会是`00000...11111`这样的,从中间某个地方开始后面全是`1`前面全是`0`

`AND`能把第`i`位变成前`i`位的AND:只要前`i`位里有`0`就能把这一位改成`0`.因为第一位就是`0`,所以任何`1`都能变`0`(变变你的)

对称地,`OR`能把第`i`位变成前`i`位的OR:只有前`i`位里出现过`1`,才能把这一位的`0`变成`1`

> 一次操作只改一位,先做`OR`再做`AND`互不干扰,所以代价就等于需要改的位数

当第一个位是`1`时,前缀的AND和OR恒为`1`,也就是`1`永远变不回`0`,最终必定全是`1`,操作次数就是`0`的个数`zeros`

方便起见我们用`zeros`表示`0`的个数

不妨设答案在`p`处分界,前`p`个字符全是`0`,后`n - p`个字符全是`1`

那么就有`ans = ones(p) + ( zeros - zeros(p) )`,前一项是把前`p`位的`1`改成`0`,后一项是把后段的`0`改成`1`

不妨令`bal = ones(p) - zeros(p)`,那么`ans = zeros + bal`,只要枚举`p = 0, 1, ..., n`取`bal`的最小值(`p = 0`时`bal = 0`,所以代码里`m`初值取`0`)

`ans = zeros + min(bal(p))`

```cpp
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int zeros = 0;
        for (char ch : s)
            if (ch == '0')
                zeros++;
        if (s[0] == '1')
        {
            cout << zeros << '\n';
        }
        else
        {
            int bal = 0, m = 0;
            for (char ch : s)
            {
                bal += (ch == '1') ? 1 : -1;
                m = min(m, bal);
            }
            cout << zeros + m << '\n';
        }
    }
}
```

## D. Falling Concrete

> **time limit per test: 2 seconds / memory limit per test: 256 megabytes**
> input: standard input / output: standard output
>
> Vihaan is repairing a road consisting of `n` sections. The height of the `i`-th section is `a_i`.
> He has a forklift which can move road sections. In one operation, Vihaan chooses two indices `i` and `j` (`1 <= i < j <= n`), picks up the `j`-th section, and moves it backwards to position `i`.
> As the section is carried backwards, one unit of concrete falls from it onto each section it passes over. Then, the carried section is inserted at position `i`.
> More formally, the subarray `[a_i, a_{i+1}, ..., a_{j-1}, a_j]` is replaced with `[a_j - (j - i), a_i + 1, a_{i+1} + 1, ..., a_{j-1} + 1]`.
> A part of the road is called flat if it is a contiguous segment of sections with equal heights.
> Vihaan may perform any number of operations, possibly zero.
> Find the maximum possible length of a flat part of the road.
>
> **Input**
> The first line contains an integer `t` (`1 <= t <= 10^4`) — the number of test cases.
> The first line of each test case contains an integer `n` (`1 <= n <= 2*10^5`) — the number of sections of the road.
> The second line contains `n` integers `a_1, a_2, ..., a_n` (`n <= a_i <= 10^9`) — the initial heights of the sections.
> It is guaranteed that the sum of `n` over all test cases does not exceed `2*10^5`.
> It can be shown that under the given constraints, the height of every section remains positive after any sequence of operations.
>
> **Output**
> For each test case, print a single integer — the maximum possible length of a flat part of the road.

令`v[i] = a_i - i`,一次操作恰好等价于把`v`的区间循环右移

因为操作后第`i`位是`a_j - (j - i)`,减掉下标正好是`v[j]`;后面每一位都`+1`而下标也`+1`,`v`的值不变,只是整体后挪一格.也就是说,操作只是把`v[j]`搬到`v[i]`(虽然位置变了,但是差值没变)

当`j = i + 1`时,就变成了交换相邻两个值,可以得到`v`是可以重排的

一段等高`h`(第`l`位到第`r`位)意味着`v[l] = h - l, v[l+1] = h - l - 1, ...`,也就是`v`里的一串连续整数

所以答案就是`v`的不同值中最长的连续整数链长度:算出所有`v[i]`,排序去重后扫一遍相邻差恰为`1`的最长连续段就能得到答案

```cpp
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<long long> v(n);
        for (int i = 0; i < n; i++)
        {
            long long x;
            cin >> x;
            v[i] = x - i;
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        int m = 1, cur = 1;
        for (int i = 1; i < v.size(); i++)
        {
            cur = (v[i] == v[i - 1] + 1) ? cur + 1 : 1;
            m = max(m, cur);
        }
        cout << m << '\n';
    }
}
```