Codeforces Round 879 (Div. 2)

传送门：Codeforces Round 879 (Div. 2)

难度适中，但菜鸡依旧。

B. Maximum Strength

题意：

​ $[l,r]$ 之间选两个数，使得十进制表示下各个位数的差值绝对值之和最大，位数不同则较小数补前导 $0$ 对齐。

题解：

​ 设 $l$ 和 $r$ 位数分别为 $n$ 和 $m$ ，取的数字为 $x<y$ ，分情况讨论。

• 若 $n<m$ ，则最优情况为 $x$ 取 $m-1$ 个 $9$ , $y$ 保留 $r$ 的最高位，剩余位为 $0$
• 若 $n=m$ ，则除去相同前缀，然后 $y$ 保留最高位，剩余位为 $0$ ， $x$ 保留最高位，剩余位为 $9$ 即可。

code：

void solve() {
    string s1, s2;
    int n, m;
    cin >> s1 >> s2;
    n = s1.length();
    m = s2.length();
    if (n < m) {
        cout << (s2[0] - '0') + (m - 1) * 9 << endl;
    } else {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (s1[i] == s2[i]) continue;
            cout << s2[i] - s1[i] + (n - i - 1) * 9 << endl;
            return;
        }
        cout << 0 << endl;
    }
    return;
}

C. Game with Reversing

题意：

​ 给定两等长串 $S$ 和 $T$ ， Alice 和 Bob 轮流操作。Alice 每次可以替换一个字符，Bob 每次可以翻转一个串， 当两串相同时，停止操作。Alice 希望操作次数尽量少， Bob 希望操作次数尽量多， 求两个人都采取最优策略的情况下，实际游戏操作次数。

题解：

​ 解释起来比较啰嗦，这里简述。

​ 实际上 Bob 每轮操作都是相同的，因此可以假设 Bob 只翻转一个字符串 $T$ 。

​ 对 Alice 来说，则可以有两种选择，将 $S$ 变为 $T$ 或 $rev(T)$ 。二者最小步数都容易 $O(n)$ 求出。 最后根据实际的奇偶性补齐 Bob 的操作数即可。

code：

void solve() {
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        if (s1[i] != s2[i]) ++ans1;
        if (s1[i] != s2[n - i - 1]) ++ans2;
    }
    if (ans1 & 1) ans1 = ans1 * 2 - 1;
    else ans1 = ans1 * 2;
    if (ans2 & 1) ans2 = ans2 * 2;
    else if (ans2 == 0) ans2 = 2;
    else ans2 = ans2 * 2 - 1;
    cout << min(ans1, ans2) << endl;
}

D. Survey in Class

题意：

​ $n$ 位学生，$m$ 个知识点。第 $i$ 个学生学习了 $[l_i, r_i]$ 个知识点。

​ 上课老师提问，每个问题至多提问一次。初始同学分数均为 $0$ ，答对加一分，答错减一分，分数可为负。求最大分差。

题解：

​ 对于线段 $[l_1, r_1]$ 和线段 $[l_2,r_2]$ ，设 $r_1<r_2$ ，则分三种情况讨论：

• $r_1<l_2$ ，则最大差值可以分别来源于两线段整段，即 $max(r_1-l_1+1, r_2-l_2+1)$ ；
• $l_1\leq l_2\leq r_1 \leq r_2$，则最大差值来源于二者分别对交集取补，即 $max(r_2-r_1, l_2-l_1)$ ；
• $l_2\leq l_1 \leq r_1 \leq r_2$ ，包含关系，最大差值来源于长线段对短线段取补，即 $(r_2-l_2+1)-(r_1-l_1+1)$ 。

​ 将每条线段按右端点排序，枚举线段 $[l_2,r_2]$ ， 目标是找出对应的 $[l_1, r_1]$ ， 三种情况分别需要求：

• 右端点小于 $l_2$ 的直线中，$r-l+1$ 的最大值
• 相交直线中， $r$ 的最小值以及 $l$ 的最小值
• 左端点大于等于 $l_2$ 的直线中， $r-l+1$ 的最小值

​ 四个值四棵动态开点线段树维护即可。

code：

#include <bits/stdc++.h>

using namespace std;
#define inf 0x7fffffff
int cnt = 0;
const int N = 4e5 + 5;
int dat[N << 5], lc[N << 5], rc[N << 5];

void update(int &p, int l, int r, int k, int val) {
    if (!p) p = ++cnt, dat[p] = inf;
    if (l == r) return (void) (dat[p] = min(dat[p], val));
    int mid = l + r >> 1;
    if (k <= mid) update(lc[p], l, mid, k, val);
    else update(rc[p], mid + 1, r, k, val);
    dat[p] = inf;
    if (lc[p]) dat[p] = min(dat[p], dat[lc[p]]);
    if (rc[p]) dat[p] = min(dat[p], dat[rc[p]]);
}

inline int query(int p, int l, int r, int u, int v) {
    if (!p) return inf;
    if (u <= l && r <= v) return dat[p];
    int mid = l + r >> 1, res = inf;
    if (u <= mid) res = min(res, query(lc[p], l, mid, u, v));
    if (v > mid) res = min(res, query(rc[p], mid + 1, r, u, v));
    return res;
}

bool cmp(pair<int, int> A, pair<int, int> B) {
    return A.second == B.second ? A.first < B.first : A.second < B.second;
}

void solve() {
#define mp(x, y) make_pair(x, y)
    int t1 = 0, t2 = 0, t3 = 0, t4 = 0;
    int n, m;
    cin >> n >> m;
    vector<pair<int, int> > Stu(n);
    for (int i = 0, l, r; i < n; i++) {
        cin >> l >> r;
        Stu[i] = mp(l, r);
    }
    sort(Stu.begin(), Stu.end(), cmp);
    int ans = 0;
    for (auto stu: Stu) {
        int l = stu.first, r = stu.second;
        int rem;
        rem = -query(t1, 0, m, 0, l - 1);
        if (rem != -inf) ans = max(ans, max(rem << 1, (r - l + 1) << 1));
        update(t1, 0, m, r, l - r - 1);

        rem = query(t2, 0, m, l, r);
        if (rem != inf) ans = max(ans, (r - rem) << 1);
        update(t2, 0, m, r, r);

        rem = query(t3, 0, m, l, r);
        if (rem != inf) ans = max(ans, (l - rem) << 1);
        update(t3, 0, m, r, l);

        rem = query(t4, 0, m, l, r);
        if (rem != inf) ans = max(ans, ((r - l + 1) - rem) << 1);
        update(t4, 0, m, l, r - l + 1);
    }
    cout << ans << endl;
    return;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E. MEX of LCM

题意：

​ 题如其名。给定 $n$ 个数，则对应的有 $C_n^2$ 个连续子序列。求所有子序列数值 $lcm$ 的 $Mex$ 。

题解：

​ 同样是利用好值域。 对于区间 $[l,r]$ ，固定住右端点 $r$ ，则至多还剩下 $r$ 个左端点，对应 $r$ 个区间。这 $r$ 个区间有多少 $lcm$ 值？从 $l=r$ 开始，每次向左添加一个数， $lcm$ 要么不变， 要么至少翻一倍，因此 $lcm$ 值的数目是 $log$ 级别的。因此整个序列所有 $lcm$ 值的数目不超过 $nlogn$ ，迭代求出然后求 $Mex$ 即可。复杂度 $O(nlogn)$

code：

inline long long lcm(long long x, long long y) {
    return x / __gcd(x, y) * y;
}

void solve() {
    int n;
    cin >> n;
    long long inf = 1ll * n * n + 2;
    vector<int> num(n);
    for (int i = 0; i < n; i++) cin >> num[i];
    set<long long> s;	//以r-1为右端点的lcm序列
    set<long long> rem; //以r为右端点的lcm序列
    set<long long> ans;	//所有lcm序列
    for (auto x: num) {
        for (auto y: s) {
            long long p = lcm(y, x);
            if (p <= inf) rem.insert(p);
        }
        rem.insert(x);
        s.clear();
        for (auto y: rem) s.insert(y);
        rem.clear();

        for (auto y: s) ans.insert(y);
    }
    long long now = 1;
    ans.insert(inf);
    for (auto x: ans) {
        if (x != now) {
            cout << now << endl;
            return;
        }
        ++now;
    }
}