CF-1935-div2

A. Entertainment in MAC

给你一个字符串 $s$ 和一个偶整数 $n$ 。你可以对它进行两种运算：

1. 将反向字符串 $s$ 添加到字符串 $s$ 的末尾
2. 将当前字符串 $s$ 倒转

需要确定在进行精确的 $n$ 操作后，可以得到的字典序·最小的 ${}^{†}$ 字符串。

void solve() {
    int n;cin >> n;string s;cin >> s;
    for (int i = 0;i < s.size() / 2;i++) {
        if (s[i] < s[s.size() - 1 - i]) {
            cout << s << '\n';return;
        } else if (s[i] == s[s.size() - 1 - i]) {
            continue;
        } else {
            string ss = s;
            reverse(s.begin(), s.end());
            cout << s << ss << '\n';return;
        }
    }
    cout << s << '\n';
}

或·：

std::cout << std::min(s, s + ss) << "\n";

B. Informatics in MAC

有一个长度为 $n$ 的数组 $a$ ，你想把它分成 $k(k>1)$ 个子段 ${}^{†}$ ，使每个子段上的 ${\mathrm{MEX}}^{‡}$ 都等于相同的整数。

请帮助 Nyam-Nyam 找到合适的除法，若无解，则输出-1

数组中的 ${}^{‡}\mathrm{MEX}$ 是不属于该数组的最小自然数。

900 ms 卡着过的

void solve() {
    int n;cin >> n;vector<int> a(n + 1), num(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];num[a[i]]++;
    }
    int m = 0;bool ok = false;
    for (int i = 0;i < n;i++) {
        if (!num[i]) {
            ok = true;
            m = i;break;
        }
    }
    if (!ok) {
        cout << "-1\n";return;
    }
    //在前面一部分找到0-(m-1)即可
    int end = 0;
    vector<int> p(n + 1, 0);

    for (int i = 1;i <= n;i++) {
        p[a[i]]++;
        bool ok = true;
        for (int j = 0;j < m;j++) {
            if (!p[j]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            end = i;break;
        }
    }
    vector<int> p1(n + 1, 0);

    if (end) {
        for (int i = end + 1;i <= n;i++) {
            p1[a[i]]++;
        }
        for (int j = 0;j < m;j++) {
            if (!p1[j]) {
                cout << "-1\n";return;
            }
        }
        cout << "2\n1 " << end << "\n" << end + 1 << " " << n << "\n";return;
    }
    cout << "-1\n";
}

应该对前缀和后缀进行预处理，看是否满足前面部分和后面部分都含有 $0-(m-1)$

void solve() {
    int n;cin >> n;vector<int> a(n + 1), pre(n + 1), suf(n + 1), cnt(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int x = 0;
    for (int i = 1;i <= n;i++) {
        cnt[a[i]]++;
        while (cnt[x]) {
            x++;
        }
        pre[i] = x;
    }
    x = 0;
    cnt.assign(n, 0);
    for (int i = n;i >= 1;i--) {
        cnt[a[i]]++;
        while (cnt[x]) {
            x++;
        }
        suf[i] = x;
    }

    for (int i = 1;i < n;i++) {
        if (pre[i] == suf[i + 1]) {
            cout << "2\n1 " << i << "\n" << i + 1 << " " << n << "\n";return;
        }
    }
    cout << "-1\n";
}

C. Messenger in MAC

从 $n$ 个 $a_i,b_i$ 中选择 $k$ 个下标，要求 $\sum _{i=1}^k{a}_{p_i}+\sum _{i=1}^{k-1}|b_{p_i}-b_{p_{i+1}}|\le l$，求 $k$ 的最大值。若没有满足要求的情况，则输出 0

Solution

贪心/DP

void solve() {
    int n, l;cin >> n >> l;
    vector<pair<int, int>> a(n);
    for (int i = 0;i < n;i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end(), [&](auto x, auto y) {
        return x.second < y.second;
        });
    int ans = 0;
    for (int i = 0;i < n;i++) {
        multiset <int> s;
        int curr = 0;
        for (int j = i;j < n;j++) {
            s.insert(a[j].first);curr += a[j].first;
            while (s.size() && a[j].second - a[i].second + curr > l) {
                int maxa = *s.rbegin();
                curr -= maxa;
                // s.extract(maxa);
                if (s.find(maxa) != s.end()) {//和上面的函数等价
                    s.erase(s.find(maxa));
                }
            }
            ans = max(ans, (int)s.size());
        }
    }
    cout << ans << '\n';
}

DP (待更 $\dots$)

D. Exam in MAC

给出一个长度为 $n$ 的数组 $s$，求 $x,y(x\le y)$ (满足 $x+y,y-x$ 都不是数组中的元素, $0\le x,y\le c$)的对数

Solution

容斥原理/组合数学

主要是要往这个方面想，想到了就很简单了。

官方题解：

用容斥原理：$\mathrm{cnt}(x,y)-\mathrm{cnt}(x,y:x+y\in s)-\mathrm{cnt}(x,y:y-x\in s)+\mathrm{cnt}(x,y:x+y,y-x\in s)$。

$x,y$ 的总对数数量是 $\frac{(c+1)\cdot (c+2)}{2}$。

$x,y:x+y\in s$。遍历和值 $s_i$，假设 $x+y=s_i$，则对于 $0\le x\le \lfloor \frac{s_i}{2}\rfloor$ 会有一个对应的 $y$，因此具有这样的和的对的数量是 $\lfloor \frac{s_i}{2}\rfloor +1$。

$x,y:y-x\in s$。遍历差值 $s_i$，假设 $y-x=s_i$，则对于 $s_i\le y\le c$ 会有一个对应的 $x$，因此具有这样的差的对的数量是 $c-s_i+1$。

$x,y:x+y,y-x\in s$。假设 $x+y=s_i$，$y-x=s_j$，则 $x=\frac{s_i-s_j}{2}$，$y=\frac{s_i+s_j}{2}$。当奇偶性相同时就可以计入答案。 让我们计算 $s$ 中偶数和奇数的数量——分别为 $even$ 和 $odd$。因此，这样的对的数量是 $\frac{even\cdot (even+1)}{2}+\frac{odd\cdot (odd+1)}{2}$。

#define int long long
void solve() {
    int n, c;cin >> n >> c;
    vector<int> a(n);
    for (int i = 0;i < n;i++) {
        cin >> a[i];
    }
    int cnt = (c + 2) * (c + 1) / 2, odd = 0;
    for (int i = 0;i < n;i++) {
        cnt -= a[i] / 2 + 1;
        cnt -= c - a[i] + 1;
        if (a[i] % 2)odd++;
    }
    int even = n - odd;
    cnt += (odd + 1) * odd / 2 + (even + 1) * even / 2;
    cout << cnt << '\n';
}

E. Distance Learning Courses in MAC

总共有 $n$ 门课程可供选择。对于第 $i$ 门远程学习课程，学生可以获得的成绩范围是 $x_i$ 到 $y_i$。

第 $j$ 个学生只能选择编号为 $l_j$ 到 $r_j$ 的课程.

远程学习课程的创建者决定以一种特殊的方式确定最终成绩。假设第 $j$ 个学生获得了远程学习课程的成绩 $c_{l_j},c_{l_j+1},\dots ,c_{r_j}$。那么他们的最终成绩将等于 $c_{l_j}$ $|$ $c_{l_j+1}$ $|$ $\dots$ $|$ $c_{r_j}$

输出 $q$ 个整数，其中第 $j$ 个整数是第 $j$ 个学生可以达到的最高最终成绩。

Solution

#algo/ds/线段树

线段树/位运算

让我们解决当 $x=0$ 时的问题。然后我们将从最高位到最低位迭代比特，并尝试将它们包含在答案中。假设我们正在迭代比特 $i$，那么如果在 $y$ 个数字中该比特出现了 $c$ 次，就会有几种情况：

• $c=0$ - 这个比特不能包含在答案中
• $c=1$ - 这个比特将包含在答案中，我们加上它
• $c>1$ - 一种特殊情况，因为对于一个比特出现在其中的数字，我们可以设置它，并对于另一个数字，我们可以设置所有比特 $j<i$。

因此，如果我们遇到一些比特 $i$ 出现了多次，那么所有比特 $j\le i$ 也将被包含在答案中。现在让我们解决原始问题，为此我们取一对 $(x_i,y_i)$ 并找到按位最大的公共前缀 - 让它成为数字 $w$。很明显，从 $w$ 起的所有比特都将包含在答案中，然后我们产生一个新的对 $(x_i^{\prime },y_i^{\prime })=(x_i-w,y_i-w)$，并记住数字 $w_i$。现在注意到 $y_i^{\prime }-1\ge x_i^{\prime }$。为什么我们需要这个事实呢？请记住，在某个比特出现多次的情况下，我们会将它和所有更小的比特都加入答案中。为此，我们会在这个位置设置一个等于 $2^i-1$ 的数字 (和其他比 $i$ 大的比特)，但是如果 $y_i^{\prime }-1\ge x_i^{\prime }$，那么我们总是可以添加所有这样的比特。

因此，对于请求 $j$ 的解决算法如下：

• 对于所有 $l_j\le i\le r_j$，取所有 $w_i$ 的按位或，记为数字 $W$
• 迭代比特 $i$ 并类似于 $x=0$ 的情况考虑相同的情况，但是对于数组 $y^{\prime }$。同时，考虑比特出现在 $W$ 中。

这种解决方案可以使用每个比特的前缀和在 $O(n\cdot \log n)$ 内实现。还可以使用线段树解决这个问题，因此可以处理修改请求。