Practice.

A. Technical Support

题意

给定一个由 \(Q, A\) 组成的字符串，对于所有 \(Q\)，判断在下一次 \(Q\) 出现或遍历到结束前，是否有至少一个 \(A\) 与之对应。

思路

如题，配对即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = LONG_LONG_MAX, mod = 998244353;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int cnt = 0;
        for(char e : s) {
            cnt += e == 'Q' ? 1 : -1;
            if(cnt < 0) cnt = 0;
        }
        cout << (cnt == 0 ? "Yes\n" : "No\n");
    }
}

别看错题（（

B. Kevin and Permutation

题意

给定整数 \(n\)，构建一个 \(n\) 的排列，使相邻数的差值的最小值最大。

思路

想要尽量让差值最大，那么我们只有相间地输出，或者说，若我们按 \(\frac{n}{2} + i, i\) 的规律输出，就可以让所有差值尽量相等。

可以贪心地认为上述的思路是正确的，解法不唯一。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = LONG_LONG_MAX, mod = 998244353;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n;
        cin >> n;
        for(int i=1;i<=n/2;i++){
            cout << n / 2 + i << ' ' << i << ' ';
        }
        if(n % 2 == 1) cout << n;
        cout << '\n';
    }
}

找规律+乱贪.jpg

C1. Make Nonzero Sum (easy version)

详见C2，区别是C1给定的数组没有0

C2. Make Nonzero Sum (hard version)

题意

给定一个由 \(-1, 0, 1\) 构成的数组，将数组分为任意若干段，相邻两段的左段右边界和右段左边界相差 \(1\)。输出是否存在一种分段，将所有段相间赋上运算符号 \(+, -, +, - ,...\) 后，所有段的运算总和为 \(0\)。若存在，输出方案。

思路

首先，我们不考虑运算符号的时候，将所有数加起来会得到一个结果 \(ans\)，若 \(ans = 0\)，那么我们只需将所有单个元素单独成段就可以无视运算符号了。否则，因为考虑到加减是一样的，我们不妨来考虑 \(ans > 0\) 的情况：

显然，若要让 \(ans\) 减小，我们就只能让某一个 \(1\) 和左相邻的数组合为一段，那么，整个 \(ans\) 将会减少 \(2\)。可以发现，我们无法将 \(ans\) 减少奇数值，所以我们可以先判断 \(ans\) 的奇偶性。在运算的时候，需要变号的时候，变号的数一定但也只要让这个数位于某一段的偶数下标，所以，我们只需找两个相邻数，其中第一个数不需要变号，第二个数需要变号，那么将这两个数作为一段即可。

所以我们只需将 \(1\) 全部找出，判断能找出多少对上述相邻数，和 \(ans / 2\) 比较即可。

有趣的是，这种解法不用考虑是否包含 \(0\)。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = LONG_LONG_MAX, mod = 998244353;

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    while(q --){
        int n;
        cin >> n;
        int ans = 0;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            ans += a[i];
        }
        if(abs(ans) % 2 == 1) cout << -1 << '\n';
        else{
            int r = 0;
            vector<pii> out;
            int left = ans / 2;
            if(left != 0) {
                int x = left / abs(left);
                r = 1;
                for (int i = 1; i < n; i++) {
                    if (a[i + 1] == x) {
                        out.emplace_back(i, i + 1);
                        r = i + 1;
                        i++;
                        left -= x;
                        if (left == 0) break;
                    } else {
                        out.emplace_back(i, i);
                        r = i;
                    }
                }
            }
            for(int i=r+1;i<=n;i++) out.emplace_back(i, i);
            if(left != 0) cout << -1 << '\n';
            else{
                cout << out.size() << '\n';
                for(auto e : out) cout << e.first << ' ' << e.second << '\n';
            }
        }
    }
}

想了半天不小心把两个难度一起做了（（