CodeForces Round #829 (div.2) A~C2

A. Technical Support

题意：

给定一个只包含 Q, A 的字符串，问每个 Q(问题) 能否匹配所有 A(回答)。

思路：

一个 Q 可以对应多个 A，可以允许 A 没有对应的 Q，即允许在 A 之前没有 Q.

代码如下：

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

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

    int q = 0, a = 0;
    for (int i = 0; i < n; i++){
        if (s[i] == 'Q') q++;
        else {
            if (q != 0) q--;
        }
    }

    if (q == 0) cout << "Yes" << endl;
    else cout << "No" << 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
33
34

---

B. Kevin and Permutation

题意：

给定一个 n ，要求构造一个长度为 n 的排列，使得 $k=mi{n}_{i=1}^{n-1}|a_{i+1}-a_i|$ 最大。

思路：

因为要使得相邻两个数之差最大，最大值肯定不超过 n / 2.

将原来 n 个数的升序排列分成前半边和后半边的两个数组，再将其交叉合并为一个数组即可。

如果 n 为奇数，则将数字 n 加在数组的最前面即可。

代码如下：

#include 
using namespace std;
const int N = 1010;

int a[N], b[N];

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

    int m = n / 2;
    for (int i = 1; i <= m; i++){
        a[i] = i;
        b[i] = i + m;
    }

    if (n % 2) cout << n << ' ';
    for (int i = 1; i <= m; i++){
        cout << b[i] << ' ' << a[i] << ' ';
    }
    cout << 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
33
34

---

C1. Make Nonzero Sum (eazy version)

题意：

给定一个长度为 n 的只包含 -1, 1 的数组，规定将这个数组划分成若干个不同的区间。

要求区间中所有元素的交替和为 0. 例如：a₁ - a₂ + a₃ - a₄ + … = 0. 保证第一个数是加，第二个数是减，第三个数是加，以此类推交替相加减，最后总和为0。

若满足条件则输出各区间的左右端点，否则输出 -1.

思路：

分析之后可以发现，如果数字为奇数个，那么无论如何都配对不成功；如果为偶数个，则一定可以成功，因为题目对分成的段数没有要求，所以可以分为两两一对：若同号，则可以划分为一组，和为 0；若异号，则划为两组，两组之和为 0 。

代码如下：

#include 
#define ll long long
#define PII pair<int, int>
using namespace std;
const int N = 2e5 + 10;

int a[N];

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

    for (int i = 1; i <= n; i++) cin >> a[i];

    //个数为奇数，那必然不可能
    if (n % 2){
        cout << -1 << endl;
        return;
    }

    vector<PII> v;
    for (int i = 1; i <= n; i += 2)
    {
        if (a[i] * a[i + 1] > 0){
            v.push_back({i, i + 1});
        }
        else {
            v.push_back({i, i});
            v.push_back({i + 1, i + 1});
        }
    }

    sort(v.begin(), v.end());
    cout << v.size() << endl;
    for (auto [x, y] : v){
        cout << x << ' ' << y << 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

---

C2. Make Nonzero Sum (hard version)

题意：

与上题一样，不同的是该题中数组包含 0，最后仍然是判断区间和是否能为 0.

思路：

在上一题的基础上进一步判断，两两一对共有四种可能，即 1, 1 , 1, -1, -1, -1, -1, 1 。

先计算出所有数字之和，如果和为 0，则不需要操作，每个数字都可以是单独的区间；如果和大于 0，说明数字 1 过多，需要消除一些 1，可以将 1 放在每个区间的第二位使其变成 -1，整体之和就会 -2 ；类似地，如果和小于0，则将 -1 放在每个区间地第二位使其变成 1，整体之和就会 +2 。其余部分再作为单个区间输出即可。

代码如下：

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

int a[N];

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

    int sum = 0;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
    }

    int f = 1;  //标记总数之和是否大于0
    if (sum < 0) f = 0;

    //判断总和是否为奇数
    if (sum % 2){
        cout << -1 << endl;
        return;
    }

    int m = abs(sum / 2);
    cout << n - m << endl;
    int h = 0; //用来判断每个区间
    for (int i = 1; i <= n; i++){
        if (f){
            if (a[i + 1] == 1 && i + 1 <= n && h != m){
                cout << i << ' ' << i + 1 << endl;
                i++;
                h++;
            }
            else {
                cout << i << ' ' << i << endl;
            }
        }
        else {
            if (a[i + 1] == -1 && i + 1 <= n && h != m){
                cout << i << ' ' << i + 1 << endl;
                i++;
                h++;
            }
            else {
                cout << i << ' ' << i << 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

---