Practice.

A. Mainak and Array

题意

给定一个序列 \(a\)，定义操作为选定一个连续字符列，并将其旋转任意次，输出恰好进行一次操作后 \(a_n - a_1\) 的最大值。

思路

首先，如果选定整个序列作为旋转序列，那么显然对于两个相邻的数，前者减后者就可以作为执行操作后的 \(a_n - a_1\)，取最大值即可。

其次，我们可以固定头或者尾，如果固定头，我们就可以旋转除头以外的其他元素，将最大值旋转到 \(a_n\)，反之同理，最后再取最大值即可。

时间复杂度：\(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 = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    int mn = inf, mx = -inf;
    for(int i=0;i<n;i++) {
        cin >> a[i];
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    int ans = max(a[n - 1] - mn, mx - a[0]);
    for(int i=0;i<n;i++) {
        int pre = (i + n - 1) % n;
        ans = max(ans, a[pre] - a[i]);
    }
    cout << ans << '\n';
}

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

我测，怎么错这么多

B. Mainak and Interesting Sequence

题意

定义若一个序列满足对于任意 \(a_i\)，严格小于 \(a_i\) 的所有数的异或值都为 \(0\)，那么这个序列是有趣的。

现在，给定序列的总和以及序列的长度，构造一个序列满足序列有趣。

思路

首先，两个相同的数异或以后为 \(0\)，那么我们不妨构造一个序列，满足包含偶数个较小的数和若干个较大的数。

或者更简单地，我们直接塞上偶数个 \(1\) 即可。

那么，我们对长度进行分讨，如果长度为奇数，那么我们直接塞上 \(n - 1\) 个 \(1\)，最后放上 \(m - n + 1\) 即可；

如果长度为偶数，那么我们在前面塞上 \(n - 2\) 个 \(1\)，最后放上两个 \(\frac{m - n + 2}{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 = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n, m;
    cin >> n >> m;
    if(n > m || (n % 2 == 0 && m % 2 == 1)){
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
    if(n % 2 == 1){
        for(int i=0;i<n-1;i++) cout << 1 << ' ';
        cout << m - n + 1 << '\n';
    }else{
        for(int i=0;i<n-2;i++) cout << 1 << ' ';
        cout << (m - n + 2) / 2 << ' ' << (m - n + 2) / 2 << '\n';
    }
}

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

乱猜即可（但我怎么猜错那么多次啊啊啊啊

C. Jatayu's Balanced Bracket Sequence

题意

题目绕死了，直接给出简化版：

给定一个满足语法规则的括号字符串，输出不同的括号的个数。

此处不同代表其开始符 "\((\)" 前面没有 "\()\)"。

思路

如题，遍历即可。

时间复杂度：\(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 = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    string s;
    cin >> n >> s;
    int now = 0;
    for(int i=0;i<s.size();i++){
        if(s[i] == '(' && (i == 0 || s[i - 1] == '(')) now ++;
    }
    cout << now << '\n';
}

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

你就说你有没有在考阅读理解罢（半恼