小白月赛87

A 小苯的石子游戏

Alice 和 Bob 依次任意拿走一个石头如果 Alice 拿到的石子总数严格大于 Bob 所拿到的石子总数

Alice win ,or Bob win

void solve() {
    int n;cin >> n;vector<int> a(n);for (auto& i : a)cin >> i;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0;i < n;i++) {
        if (i % 2)cnt1 += a[i];
        else cnt2 += a[i];
    }
    if (cnt1 == cnt2)cout << "Bob\n";
    else cout << "Alice\n";
}

B 小苯的排序疑惑

现在小苯想知道能否通过执行最多一次操作(sort(a[l,r])使得数组 a 按非降序排列。

void solve() {
    int n;cin >> n;vector<int> a(n);
    for (auto& i : a)cin >> i;
    vector<int> b(a);
    sort(a.begin(), a.end());

    int cnt1 = 0, cnt2 = 0;

    for (int i = 0;i < n - 1;i++) {
        if (b[i] != a[i])break;
        else cnt1++;
    }
    for (int i = n - 1;i >= 0;i--) {
        if (b[i] != a[i])break;
        else cnt2++;
    }

    if (cnt1 + cnt2) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

C/D 小苯的 IDE 括号问题（easy）（hard）

输入一个字符串， I 代表光标，操作： backspace|delete||<-|-> 输出操作后的序列
`

void solve() {
    int n, k;cin >> n >> k;
    string a;cin >> a;
    int pos;
    for (int i = 0;i < a.size();i++) {
        if (a[i] == 'I')
            pos = i;
    }
    while (k--) {
        string op;cin >> op;
        if (op == "backspace") {
            if (pos >= 1 && pos + 1 < a.size() && a[pos - 1] == '(' && a[pos + 1] == ')') {
                a.erase(a.begin() + pos + 1);
                a.erase(a.begin() + pos - 1);pos--;
            } else {
                //如果前面还有字符的话
                if (pos >= 1)
                    a.erase(a.begin() + pos - 1), pos--;
            }
        } else if (op == "delete") {
            //如果后面还有字符的话
            if (pos + 1 < a.size())
                a.erase(a.begin() + pos + 1);
        } else if (op == "<-") {//后面两个条件->(hard)
            if (pos >= 1)//如果前面还有字符
                swap(a[pos - 1], a[pos]), pos--;
        } else {
            //如果后面还有字符
            if (pos + 1 < a.size())
                swap(a[pos + 1], a[pos]), pos++;
        }
    }
    cout << a << '\n';
}

E 小苯的数组构造

给出一个数组 $a$，现在给 $a_i$ 每一项加上 $b_i$，使得 is_sorted(a) 输出满足 (maxb-minb) 最小的 $b$ 数组。


如图，后面的 $a_i$ 没有满足 sorted ，只需要补前一个最高的数即可满足，虚线框即为 $b_i$ 大小，其余的为 $0$. 最小方差即为 $!is\mathrm{\_}sorted(max(a)-min(a))$

void solve() {
    int n;cin >> n;vector<ll> a(n), b(n);for (auto& i : a)cin >> i;
    ll now = a[0];
    for (int i = 1;i < n;i++) {
        now = max(now, a[i]);
        b[i] = now - a[i];
    }

    for (auto i : b)cout << i << " ";
}

F 小苯的数组切分

给出一个数组 $a$，选择一个区间 $[l,r](1<l\le r<n)$，分为三段，分别在各段内相互做 $\oplus ,|,\mathrm{\&}$ 运算，输出三段结果之和的最大值。

对于 $\mathrm{\&}$ 运算，只会越来越小，所以，$r=n-1$,即最后一段只有一个 $a_n$

对于 $\oplus ,|$ 运算，可以先预处理一下.

void solve() {
    int n;cin >> n;vector<ll> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        b[i] = b[i - 1] ^ a[i];
    }

    ll ans = 0, c = 0;
    for (int i = n - 1;i >= 1;i--) {
        ans = max(ans, a[n] + b[i] + c);c |= a[i];
    }
    cout << ans << '\n';
}

G 小苯的逆序对

给出一个长度为 $n$ 的排列，求出多少逆序对满足互素$(gcd(a_i,a_j)=1(i<j,a_i>a_j))$

Solution

用树状数组求逆序对，求数组中互质个数(容斥原理)

相关题目：

逆序对 : 求数组逆序对个数：(归并，树状数组)

GCD SUM：求 $\sum _{i=1}^n\sum _{j=1}^{n}gcd(i,j)(n\le {10}^5)$

void solve() {
    ll n;cin >> n;
    ll ans = 0;
    vector<ll> f(n + 1);
    for (int i = n;i >= 1;i--) {
        f[i] = n / i * (n / i);
        for (int j = i << 1 ;j <= n;j += i) {
            f[i] -= f[j];
        }
        ans += f[i] * i;
    }
    cout << ans << '\n';
}

Problem - F - Codeforces：求给定数组所有子序列中 $gcd(\text{subsequence})=1$ 的个数 $(\mathrm{mod}{10}^9+7)$

(待更 $\dots$)

G_哔哩哔哩_bilibili