Practice.

A. Indirect Sort

题意

给定一个排列 \(a\)，定义操作如下：

选择三个下标 \(i, j, k\)，满足 \(1 \leq i < j < k \leq n\)；
若 \(a_i > a_k\)，将 \(a_i\) 替换为 \(a_i + a_j\)，否则将 \(a_j\) 和 \(a_k\) 交换。

输出是否可以将排列变为一个不递减序列。

思路

显然，当第一位不为 \(1\) 的时候，第一位无法减小，而由于 \(1\) 在序列的后面，所以一定存在一个递减的组合，而操作无法将选定的递减组合变为递增，所以无解。

相反地，当第一位为 \(1\) 时，我们只需选 \(i = 1\)，那么每次均可实现交换，从而交换成为一个不递减序列。

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

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        int a, tmp;
        cin >> a;
        for(int i=1;i<n;i++) cin >> tmp;
        cout << (a == 1 ? "YES\n" : "No\n");
    }
}

怎么会是呢，怎么想了那么久呢？

B. Maximum Substring

题意

给定一个二进制字符串，对于它的连续子串，统计 \(0, 1\) 的个数为 \(x, y\)，那么代价 \(t\) 满足：

\(x \cdot y\)，如果 \(x > 0\) 并且 \(y > 0\)；
\(x ^ 2\)，如果 \(x > 0\) 并且 \(y = 0\)；
\(y ^ 2\)，如果 \(x = 0\) 并且 \(y > 0\)。

输出所有子串中最大的代价。

思路

显然，若我们想让代价最大，那么我们希望子串中 \(0\) 或 \(1\) 的个数尽量多，如果个数差不多，那么考虑两者的乘积。

所以，我们不妨找出所有连续相等的子串，然后计算个数的平方，记录该条件的最大值。

而假设不满足上述条件，那么我们就希望 \(x\) 和 \(y\) 的值足够大，也就是原字符串对应的代价。

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

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int num = 0;
        for(char e : s)
            if(e == '1') num ++;
        int cnt = 0, pre = 0;
        for(int i=0;i<n;i++){
            if(s[i] == s[pre]) continue;
            else{
                cnt = max(cnt, i - pre);
                pre = i;
            }
        }
        cnt = max(cnt, n - pre);
        cout << max(cnt * cnt, num * (n - num)) << '\n';
    }
}

简单思维题

C. Complementary XOR

题意

给定两个长度相等的二进制字符串 \(a, b\)，定义操作为选择一段连续的区间，并将区间内的 \(a\) 字符串的值取反，将区间外的 \(b\) 字符串的值取反。输出一种操作数低于 \(n + 5\) 的流程，使两个字符串所有位都变为 \(0\)。

思路

显然，若 \(a\) 与 \(b\) 异或值为 \(0\) 或者两者相等的时候才有解，否则考虑到操作的对称性，我们无法将它们变为 \(0\)。

其次，若 \(a\) 与 \(b\) 异或值为 \(0\)，那么我们只需选择整个区间进行一次操作，即可将 \(a\) 变为 \(b\)。

那么，我们来考虑 \(a = b\) 的情况。

不难发现，若我们遍历到了 \(a_i\)，满足 \(a_i = 1\)，那么我们只需选择 \([1, i]\) 和 \([1, i - 1]\) 进行操作，即可在将其余位的操作抵消的前提下，将 \(1\) 变为 \(0\) 了。

当然，右边界 \(i - 1\) 要求 \(i \geq 2\)，若第一位有 \(1\)，那么我们考虑对 \([1, 1]\) 和 \([2, n]\) 进行操作，从而将整个 \(a\) 取反。

按照上述输出，我们将会得到最多 \(2n + 1\) 个操作，要使其降低一倍，我们不妨留意异或的性质，在同一个区间内进行两次操作后操作是无效的。所以，我们只需统计操作数的奇偶性，从而避免无效操作。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

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

const int N = 2e5 + 10;

int cnt[N];

signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t, n;
    cin >> t;
    vector<pii> ans;
    while(t --){
        ans.clear();
        cin >> n;
        for(int i=0;i<n;i++) cnt[i] = 0;
        string a, b;
        cin >> a >> b;
        bool ok = true;
        for(int i=0;i<n;i++){
            if(a[i] != ('1' - b[i] + '0')){
                ok = false;
                break;
            }
        }
        if(a != b && !ok){
            cout << "NO\n";
        }else{
            cout << "YES\n";
            if(a != b){
                ans.emplace_back(1, n);
                a = b;
            }
            for(int i=0;i<n;i++){
                if(a[i] == '1'){
                    if(i == 0){
                        ans.emplace_back(1, n);
                        ans.emplace_back(2, n);
                    }else{
                        cnt[i] ++;
                        cnt[i - 1] ++;
                    }
                }
            }
            for(int i=0;i<n;i++){
                if(cnt[i] % 2 == 1) ans.emplace_back(1, i + 1);
            }
            cout << ans.size() << '\n';
            for(auto x : ans) cout << x.first << ' ' << x.second << '\n';
        }
    }
}

构造题有时候想到就感觉很妙啊（（