（注：题解中的代码只给出了核心逻辑部分）

A. 小苯的石子游戏

考点：贪心

题意：两个人玩游戏轮流从一个有序数组中取数字并加到自己的数字中，判断先手取的最终数字是否能严格大于后手。

由于数组已经有序，因此从后往前直接贪心取就行，每个人一定都取当前数组中最大的一个。

代码

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    } 
    // sort(a.begin() + 1, a.end()); // 题目已经保证a有序，可以不写这句
    int s1 = 0, s2 = 0;
    int f = 0;
    for(int i = n; i; i--) {
        if(!f) s1 += a[i];
        else s2 += a[i];
        f ^= 1;
    }
    if(s1 > s2) {
        cout << "Alice" << endl;
    }
    else {
        cout << "Bob" << endl;
    }
}

B. 小苯的排序异或

考点：贪心，排序

题意：给定一个数组，选择一段长度小于数组长度的区间进行排序，问能否操作一次后使得数组有序。

贪心考虑，区间长度要严格小于 ，恰好选 的长度一定是最优的。而 的区间长度只对应了 2 种情况：
和
因此分类讨论，只要两种情况有一种合法即可，也就是：
1. 到 的所有数都大于等于
2. 到 的所有数都小于等于

代码

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int mn = 1e10, mx = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(i > 1) mn = min(mn, a[i]);
        if(i < n) mx = max(mx, a[i]);
    }
    if(mn >= a[1] || mx <= a[n]) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

C, D. 小苯的IDE括号操作

考点：栈，双指针，模拟

题意：给定括号串，其中恰好出现一个 "I" 字符表示鼠标光标。处理 q 次操作，包括两种删除和两种移动（easy只有删除），删除和移动操作的规则和牛客在线IDE相同，求最终括号串的样子。

我们只需要用栈模拟即可，开两个栈分别正序存储光标左侧的所有字符，以及倒序存储光标右侧的所有字符。

对于 操作，左栈 一定 ，那只要左栈栈顶为 “(”，且同时右栈栈顶为 “)”，则右栈也需要 pop。

对于 操作，直接右栈 即可。

对于 两种移动 操作，我们只需要将一个栈的栈顶移动到另一个栈的栈顶，就相当于完成了移动操作。

注意以上处理所涉及的 操作均需判栈是否为空。

对于，我们还可以使用分别走向左右两端的双指针进行模拟，其过程和栈模拟都是类似的。

easy代码（双指针）：

void solve() {
    int n, q;
    string s;
    cin >> n >> q >> s;
    int k = s.find('I');
    int l = k - 1, r = k + 1;
    while(q -- ) {
        string t;
        cin >> t;
        if(t == "backspace") {
            if(l >= 0) {
                if(s[l] == '(' && r < n && s[r] == ')') r ++ ;
                l -- ;
            }
        }
        else {
            if(r < n) r ++ ;
        }
    }
    for(int i = 0; i <= l; i++) cout << s[i];
    cout << 'I';
    for(int i = r; i < n; i++) cout << s[i];
    cout << endl;
}

hard 代码（栈）：

void solve() {
    string s;
    int n, q;
    cin >> n >> q >> s;
    int k = s.find('I');
    vector<char> a, b;
    for(int i = 0; i < k; i++) {
        a.emplace_back(s[i]);
    }
    for(int i = k + 1; i < n; i++) {
        b.emplace_back(s[i]);
    }
    reverse(b.begin(), b.end());
    while(q -- ) {
        string t;
        cin >> t;
        if(t == "delete") {
            if(b.size()) b.pop_back();
        }
        else if(t == "backspace") {
            if(a.size()) {
                if(a.back() == '(' && b.size() && b.back() == ')') {
                    b.pop_back();
                }
                a.pop_back();
            }
        }
        else if(t == "<-") {
            if(a.size()) {
                b.emplace_back(a.back());
                a.pop_back();
            }
        }
        else {
            if(b.size()) {
                a.emplace_back(b.back());
                b.pop_back();
            }
        }
    }
    for(int i = 0; i < a.size(); i++) {
        cout << a[i];
    }
    cout << "I";
    for(int i = b.size() - 1; ~i; i--) {
        cout << b[i];
    }
}

同时，本题也可以使用双向链表通过，但过程相对栈模拟复杂很多，以下给出某验题同学代码：

hard 代码（双向链表）：

author：Kidulthood

int main() {
    scanf("%d%d%s", &n, &k, s + 1);
    for(int i = 1; i <= n; i ++) {
        if(s[i] == '(') a[i] = -1;
        else if(s[i] == ')') a[i] = 1;
        else a[i] = 0, now = i;
    }
    for(int i = 1; i < n; i ++) R[i] = i + 1;
    for(int i = 2; i <= n; i ++) L[i] = i - 1;
    for(int i = 1; i <= k; i ++) {
        scanf("%s", op + 1);
        if(op[1] == 'b') {
            if(a[L[now]] == -1 && a[R[now]] == 1) {
                int l = L[L[now]], r = R[R[now]];
                R[L[L[now]]] = now; L[R[R[now]]] = now;
                L[now] = l; R[now] = r;
            }
            else {
                if(L[now]) {
                    int l = L[L[now]];
                    R[l] = now; L[now] = l;
                }
            }
        }
        else if(op[1] == 'd') {
            if(R[now]) {
                int r = R[R[now]]; L[r] = now; R[now] = r;
            }
        }
        else if(op[1] == '<') {
            if(L[now]) swap(a[now], a[L[now]]), now = L[now];
        }
        else if(R[now]) swap(a[now], a[R[now]]), now = R[now];
    }
    while(L[now]) now = L[now];
    while(now) {
        if(a[now] == -1) printf("(");
        else if(a[now] == 0) printf("I");
        else printf(")");
        now = R[now];
    }
    return 0;
}

E. 小苯的数组构造

考点：思维，构造，贪心

题意：给定长为 的一个数组 ，要求构造一个长为 的数组 ，满足 + 是单调不降的，且 的极差最小。

首先容易想到，如果没有极差的限制，那将非常容易构造，因为此时 数组可以尽可能地递增使 对其的影响忽略不计。因此容易再想到，答案具备单调性，很大的极差一定满足，那肯定存在一个最小的极差满足条件。
考虑到 的前缀最大值数组，只要将 变为 即 的前缀最值就是最优的。

我们将 的前缀最大值数组记为 ，则 的最大值就是本题的最小极差，即“每一项前面的最大值和该项的差值”的最大值，我们将其记为 。上述提到了答案具有单调性，我们只需证明 不能作为本题的答案即可，而这个证明十分显然，我们记 对应的前缀最大值的下标为 ，当前下标为 ，则有：。

此时如果我们设置 的极差为 ，则 的值最大只有 。

我们记 + ，则：
而这个式子在最优情况下，应该等于：，因此 不满足单调不降。

因此答案最少也得选择 。

代码

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int mx = a[1];
    vector<int> ans(n + 1);
    for(int i = 2; i <= n; i++) {
        int now = max(0LL, mx - a[i]);
        ans[i] = now;
        mx = max(mx, a[i]);
    }
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }
}

F.小苯的数组切分

考点：位运算，贪心

题意：给定长为 的数组 ，要求将数组分为非空的三段，段内分别做：异或，按位或，按位与。后结果相加求和，使结果最大，求最大和。

考虑位运算性质， 操作越做越大， 操作越做越小。因此我们直接取第三段区间为 这个点一定最优，接着枚举前两段区间的分割点即可。

分割点我们记为 和 ，为什么这样一定最优？
假设最终 不取在 的位置，如同本题的样例解释一样，那么我们容易发现，如果此时将 右移，第二段区间的值内部在做 运算，因此数字越多结果一定越大。相应的，第三段区间在做 运算，因此数字越少结果一定越大。
因此结果一定不会更差，所以我们直接取 一定最优，接着枚举 即可。

代码

void solve() {
    int n;
    cin >> n;
    n -- ;
    vector<int> a(n + 1), s(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] ^ a[i];
    }
    int ans;
    cin >> ans;
    int p = a[n];
    int sum = 0;
    for(int i = n - 1; i; i--) {
        sum = max(sum, p + s[i]);
        p |= a[i];
    }
    cout << ans + sum << endl;
}

G.小苯的逆序对

考点：莫比乌斯反演，容斥，树状数组，dp

题意：给定长为 的排列，求有多少个排列值互素的逆序对。

我们可以定义 表示：“所有的 可以是 的倍数的数字们组成的数组”的逆序对数，假设我们已经有了这个 数组，那么我们如何将倍数的值转为其值本身，则只需要从大到小枚举 ，并执行：，执行了这一步后， 就转为了：“所有的 可以等于 的数”组成数组的逆序对个数。那么显然 就是我们要求的答案。

接下来考虑，我们如何获得一开始的 数组呢，也就是：“所有的 可以是 的倍数的数字们组成的数组”的逆序对数。我们只需枚举 ，然后对所有是 的倍数的数字们组成的数组求逆序对即可，实现上我们可以开一个二维，其中 存了所有排列值是 的倍数的排列值，按原排列的下标顺序存。
举个例子：如果排列是：，则 ，。
接着我们只需要对所有的 都求一遍逆序对，就得到了初始的 。而一个数组内求逆序对这一过程我们可以使用树状数组做到 的时间复杂度，其中 是数组长度。

得到初始的 后再做上述的容斥，我们就解决了本问题。

代码

class BIT {
public:
    BIT(int size) : size_(size), tree_(size + 1, 0) {}
 
    void update(int index, int delta) {
        for (int i = index + 1; i <= size_; i += (i & -i)) {
            tree_[i] += delta;
        }
    }
 
    int query(int index) {
        int sum = 0;
        for (int i = index + 1; i > 0; i -= (i & -i)) {
            sum += tree_[i];
        }
        return sum;
    }
 
    int queryRange(int left, int right) {
        return query(right) - query(left - 1);
    }
 
private:
    int size_;
    vector<int> tree_;
};
 
vector<vector<int>> d(202020);
void init() {
    int n = 2e5;
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j += i) {
            d[j].emplace_back(i);
        }
    }
}
 
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for(int i = 1, x; i <= n; i++) {
        cin >> x;
        for(auto & fac : d[x]) {
            g[fac].emplace_back(x);
        }
    } // 处理完这一步，g 就是上文提到的二维 vector
    vector<int> dp(n + 1);
    for(int i = 1; i <= n / 2; i++) { // 读者可以思考这里为什么只枚举到 n/2，而不是 n
        int sz = n / i;
        BIT b(sz + 1);
        for(int j = g[i].size() - 1; ~j; j--) {
            int now = g[i][j] / i;
            dp[i] += b.query(now - 1);
            b.update(now, 1);
        }
    }
    for(int i = n / 2; i; i--) {
        for(int j = i + i; j <= n; j += i) {
            dp[i] -= dp[j];
        }
    }
    cout << dp[1] << endl;
}
 
/*
 

 
*/
 
signed main () {
//     init(minp, primes, m); // primes
    init();
    int t = 1;
    // cin >> t;
//     getchar();
    while(t -- ) {
        solve();
    }
    return 0;
}

当然本题也可以通过预处理莫比乌斯函数 后再做容斥的方式通过，和上文给出的做法本质完全相同，这里不再赘述。