Practice.

A. Indirect Sort

题意

给定一个排列 ，定义操作如下：

1. 选择三个下标 ，满足 ；

2. 若 ，将 替换为 ，否则将 和 交换。

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

思路

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

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

时间复杂度：

对应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

题意

给定一个二进制字符串，对于它的连续子串，统计 的个数为 ，那么代价 满足：

1. ，如果 并且 ；

2. ，如果 并且 ；

3. ，如果 并且 。

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

思路

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

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

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

时间复杂度：

对应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

题意

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

思路

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

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

那么，我们来考虑 的情况。

不难发现，若我们遍历到了 ，满足 ，那么我们只需选择 和 进行操作，即可在将其余位的操作抵消的前提下，将 变为 了。

当然，右边界 要求 ，若第一位有 ，那么我们考虑对 和 进行操作，从而将整个 取反。

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

时间复杂度：

对应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';
        }
    }
}

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