CodeForces Round #832 (div.2) A~C

A. Two Groups（思维）

题意：

给定一个包含 n 个整数的数组，要求将其分为两组，使得两组数和的绝对值之差最小。

输出最小的绝对值之差。

思路：

将正数和负数分为两组，分别求出和的绝对值，将两个绝对值相减，再求其绝对值即可。

换句话说，整个数组和的绝对值就是答案。

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 2e5 + 10;

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

    ll sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if (x > 0) sum1 += x;
        if (x < 0) sum2 += x;
    }

    cout << abs(sum1 - abs(sum2)) << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

B. BAN BAN（结论）

题意：

给定一个整数 n 。

定义 s(n) 表示把字符串 BAN 连接了 n 次，即 s(1) = “BAN”, s(3) = “BANBANBAN”.

要求选择字符串中的任意两个字符进行交换，保证最后的字符串中不包含子串 BAN 。

输出需要交换的最小次数，和每次交换的位置。

思路：

重点要注意下 子串 的定义：如果一个字符串 $a$ 可以通过删除任意个字符（不要求是连续的）得到字符串 $b$，则称 $b$ 是 $a$ 的子串。

那么我们要保证交换后的字符串中没有 BAN ，即可以考虑将所有的 B 都换到 N 的后面，这样也能保证交换次数最少。

最少交换次数为 n / 2 向上取整。从首尾向中间寻找，每次交换第 $i$ 个 BAN 中的 B 和倒数第 $i$ 个 BAN 中的 N .

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 2e5 + 10;

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

    cout << (n + 1) / 2 << endl;
    for (int i = 1, j = n * 3; i < j; i += 3, j -= 3)
        cout << i << ' ' << j << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

C. Swap Game（博弈论）

题意：

Alice 和 Bob 在一个包含 n 个正整数的数组上玩游戏，Alice 先手。

游戏规定：

1. 在这个玩家的回合中，如果 a[1] = 0 ，则该玩家为输;
2. 否则，玩家可以选择某个 a[i] ($2\le i\le n$) ，然后将 a[1] 的值减一，并交换 a[1] 和 a[i] 。

请确定游戏的赢家。

思路：

先判断 a[1] = 1 的情况：

1. 如果 a[1] = 1 且 1 是数组中最小值，最优状态下先手必定会将 a[1] 变为 0，并换到后面去，后手只需再将这个 a[1] 换回来，则下一步 先手必输。
2. 如果 a[1] != 1 ，就要进一步判断：
   1. 如果数组中最小值是 1，那么先手只需将 1 换到 a[1] 的位置上，变成第一种情况，先后手顺序互换，则 先手必赢。
   2. 如果数组中最小值是 a[1] ，模拟推导一下会发现，情况最终会变成第一种，则 先手必输。
   3. 如果数组中最小值不是 a[1] ，继续推导，将最小值变为 1 后将其换到 a[1] 的位置上，同 2.1 ，则 先手必赢。

综上，只需判断 a[1] 是不是数组的最小值即可。

如果 a[1] 是最小值，则先手必输，否则先手必赢。

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 2e5 + 10;

ll a[N];

void solve()
{
    int n;
    cin >> n;
    
    ll minn = 2e9;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        minn = min(minn, a[i]);
    }

    if (a[1] == minn) cout << "Bob" << endl;
    else cout << "Alice" << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---