Contestant'. Rank 1872. Rating -13.

罚时吃饱了

A. Blackboard List

题意

有一块黑板，初始状态下只有两个数字。

定义操作为任选黑板上的两个数字，将两者的差的绝对值写到黑板上。

现在，给定打乱顺序后的黑板上的数字序列，输出其中任意一个初始状态的数字。

思路

首先，因为我们写上去的数字一定是非负数，所以如果序列中有负数，那直接输出。

否则，那么不会出现正数减负数的情况，也就是说，我们写上去的数一定是小于初始状态下的最大数字的。

因此，如果序列都是非负数，最大值就是答案。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

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

void solve() {
    int n;
    cin >> n;
    int mx = 0;
    bool f = false;
    while(n --){
        int x;
        cin >> x;
        if(x < 0 && !f){
            f = true;
            cout << x << '\n';
        }else mx = max(mx, x);
    }
    if(!f) cout << mx << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

签到变得不签了（

B. Minimize Permutation Subarrays

题意

给定一个 \(n\) 的排列，定义操作为选择两个数，并将其互换位置（可以是同两个数换位置）。

输出一个方案，使最后所有连续子序列中排列的个数最少。

思路

首先，如果要让排列尽量少，那么我们考虑将 \(1\ 2\) 分的尽可能开，或者将 \(1\ n\) 尽可能靠近。

上述操作等价于将 \(n\) 放入 \(1\ 2\) 之间。

显然，如果满足上述操作，我们就可以贪心地认为个数最少了。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

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

void solve() {
    int n;
    cin >> n;
    vector<int> ind(n + 1);
    for(int i=1;i<=n;i++) {
        int cur;
        cin >> cur;
        ind[cur] = i;
    }
    if(ind[1] > ind[2]) swap(ind[1], ind[2]);
    if(ind[n] < ind[1]) cout << ind[1] << ' ' << ind[n] << '\n';
    else if(ind[n] > ind[1] && ind[n] < ind[2]) cout << "1 1\n";
    else cout << ind[2] << ' ' << ind[n] << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

贪错了两次，但刚好都是答案的其中一部分

C. No Prime Differences

题意

给定矩阵的大小 \(n \times m\)，构造一个矩阵，满足所有相邻的两个数的差的绝对值都不是质数。

思路

首先，如果 \(n\) 是偶数，那么我们直接按顺序 从左到右 从上到下放入即可，最后横向差 \(1\)，纵向差偶数。

如果 \(m\) 是偶数，我们按顺序 从上到下 从左到右放入，最后横向差偶数，纵向差 \(1\)。

否则，也就是 \(n\) 和 \(m\) 都是奇数的时候，我们考虑下面的构造：

首先，我们尽可能让横向的差值为 \(1\)，因而我们会想到下面的构造方法：

\(\begin{matrix}1&2&3&4&5\\7&8&9&10&?\end{matrix}\)

很有趣，我们将 \(?\) 的位置放上跳过的 \(6\)，恰好是满足条件的。

那么，扩大我们的打表吧：

\(\begin{matrix}1&2&3&4&5\\7&8&9&10&6\\13&14&15&11&12\\19&20&16&17&18\\...\end{matrix}\)

不难发现均满足条件。

因此，如上方式即可得到答案。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

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

void solve() {
    int n, m;
    cin >> n >> m;
    if(n % 2 == 1 && m % 2 == 1) {
        vector<vector<int>> ans(n + 1, vector<int>(m + 1));
        for (int j = 1; j <= m; j++) ans[1][j] = j;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                ans[i][j] = ans[i - 1][j] + ((ans[i - 1][j] == (i - 1) * m) ? 1 : m + 1);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) cout << ans[i][j] << ' ';
            cout << '\n';
        }
    }else if(m % 2 == 0){
        int now = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cout << now ++ << ' ';
            }
            cout << '\n';
        }
    }else{
        int now = 1;
        vector<vector<int>> ans(n + 1, vector<int>(m + 1));
        for(int j=1;j<=m;j++){
            for(int i=1;i<=n;i++){
                ans[i][j] = now ++;
            }
            cout << '\n';
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) cout << ans[i][j] << ' ';
            cout << '\n';
        }
    }
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

一直在想 \(4 \times 4\) 为单位的规律，属实是被之前的构造题束缚思路了（

D. Bracket Walk

题意

给定一个由括号组成的字符串，定义操作为在某一位向左或向右移动一格（两个端点只能向内走）。

定义起点为 \(1\)，终点为 \(n\)，在每个格子可以经过任意次的条件下，得到行走路径。

将路径用每一位上的括号表征，可得到一串新的括号组成的字符串，如果这个字符串中的所有括号均被配对，那么即有解。

给定 \(q\) 个累积询问，每个询问给出一个下标，输出将这个下标对应的括号"取反"后，是否有解。

思路

首先，显然括号需要两两配对，并且在后退 \(x\) 格后我们仍需走 \(x\) 格回到最初开始后退的那个点，所以总步数一定是偶数。

或者换句话说，如果给定字符串长度为奇数，直接输出 \(NO\)。

其次，在后退并复位的过程中，我们不难发现，针对 () 的后退是毫无意义的，有意义的只有 (( 和 ))。

那么，我们只需维护连续相同的括号即可。

考虑下面的 \(set\) 维护：

给定下面的两个条件：

奇数位 \(i\) 对应的字符为 )
偶数位 \(i\) 对应的字符为 (

我们将满足任意一个条件的下标 \(i\) 记录下来，存入 \(set\) \(A\) 中。

结论是：如果 \(A\) 为空，或者 \(A\) 中的最小元素为偶数且最大元素为奇数，那么就是有解。

下面给出证明：

如果 \(A\) 为空，那么字符串就是 ()()()()...，显然有解；
如果 \(A\) 中的最小元素为奇数，那么字符串会变成类似 ()()())... 的形式，此时，显然前面没有多余的 ( 与之配对，也没有出现 (( 来后退；最大元素为偶数的时候同上，也无法配对；
如果 \(A\) 中的最小元素为偶数且最大元素为奇数，那么我们不难发现，一定会出现 (( 和 ))。因为字符串长度是偶数，所以不可能出现奇数个未配对的括号，因而，我们只需让 (( 和 )) 回退的次数的差值为未配对的括号数的一半即可，此时显然是有解的。

时间复杂度：\(O((n + q) \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

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

void solve() {
    int n ,q;
    cin >> n >> q;
    string s;
    cin >> s;
    s = "#" + s;
    set<int> a;
    for(int i=1;i<=n;i++){
        if(i % 2 == 1 && s[i] == ')') a.emplace(i);
        if(i % 2 == 0 && s[i] == '(') a.emplace(i);
    }
    while(q --){
        int x;
        cin >> x;
        if(a.count(x)) a.erase(x);
        else a.emplace(x);
        if(n % 2 == 1) cout << "NO\n";
        else if(a.empty() || (*a.begin() % 2 == 0 && *a.rbegin() % 2 == 1)) cout << "YES\n";
        else cout << "NO\n";
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

这个做法很有趣（其实赛时想到了一半多了