Div.2 Round - Codeforces Round #738 (Div. 2) - 《从 -1 开始的算法学习之路》

比赛链接：Here

1559A. Mocha and Math

题意：

给定一个区间，选择区间内的值执行 & 操作使得区间最大值最小化

观察样例发现：令 x = (1 << 30) - 1 后 $Codeforces Round #738 (Div. 2) - 图1$ 答案

证明：

我们假设答案是 x。在它的二进制表示中，只有在所有 $Codeforces Round #738 (Div. 2) - 图2$ 的二进制表示中该位为 $Codeforces Round #738 (Div. 2) - 图3$ 时，该位才会为 $Codeforces Round #738 (Div. 2) - 图4$ 。否则，我们可以使用一个操作使 x 中的该位变为 $Codeforces Round #738 (Div. 2) - 图5$ ，这是一个较小的答案。
所以我们可以初始设置 $Codeforces Round #738 (Div. 2) - 图6$ 或者 $Codeforces Round #738 (Div. 2) - 图7$ 。然后我们对序列进行迭代，使 $Codeforces Round #738 (Div. 2) - 图8$ ，最终 x 是 anwser。

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    int x = (1 << 30) - 1;
    for (int i = 0, a; i < n; ++i) {
        cin >> a;
        x &= a;
    }
    cout << x << "\n";
}

1559B.Mocha and Red and Blue

根据贪心思想，找到第一个非 ? 的下标，然后根据下标位置的值去枚举情况即可

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n; string s;
        cin >> n >> s;
        for (int i = 0; i < n; ++i)
            if (s[i] == '?' and i and s[i - 1] != '?')
                s[i] = 'R' ^ 'B' ^ s[i - 1];
        if (s.back() == '?') s.back() = 'R';
        for (int i = n - 2; i >= 0; --i)
            if (s[i] == '?') s[i] = 'R' ^ 'B' ^ s[i + 1];
        cout << s << "\n";
    }
}

1559C.Mocha and Hiking

路线规律题，

如果 $Codeforces Round #738 (Div. 2) - 图9$ 那么路径肯定有 $Codeforces Round #738 (Div. 2) - 图10$ %5Cto%201%5Cto2%5Cto…%5Cto%20n%5D#card=math&code=%5B%28n%20%2B%201%29%5Cto%201%5Cto2%5Cto…%5Cto%20n%5D&id=FPytq)

如果 $Codeforces Round #738 (Div. 2) - 图11$ 那么路径为 $Codeforces Round #738 (Div. 2) - 图12$ %5D#card=math&code=%5B1%5Cto2%5Cto…%5Cto%20n%5Cto%20%28n%20%2B%201%29%5D&id=Fdw4N)

对于其他情况来说：由于 $Codeforces Round #738 (Div. 2) - 图13$ ，所以肯定存在整数 $Codeforces Round #738 (Div. 2) - 图14$ 使得 $Codeforces Round #738 (Div. 2) - 图15$ ,那么路径为 $Codeforces Round #738 (Div. 2) - 图16$ %5Cto%20(i%20%2B%201)%5Cto%20(i%20%2B%202)%5Cto…%5Cto%20n%5D#card=math&code=%5B1%5Cto%202%5Cto…%5Cto%20i%5Cto%28n%20%2B%201%29%5Cto%20%28i%20%2B%201%29%5Cto%20%28i%20%2B%202%29%5Cto…%5Cto%20n%5D&id=Vwyk1)

具体证明可以参考哈密顿路径

const int N = 1e4 + 10;
int a[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; for (cin >> _; _--;) {
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        int idx = n;
        for (int i = 1; i < n; ++i)
            if (a[i] == 0 and a[i + 1] == 1) {
                idx = i; break;
            }
        if (a[1] == 1) {
            cout << n + 1 << " ";
            for (int i = 1; i <= n; ++i) cout << i << " \n"[i == n];
            continue;
        }
        for (int i = 1; i <= idx; ++i) 
            cout << i << " ";
        cout << n + 1 << " ";
        for (int i = idx + 1; i <= n; ++i) cout << i << " ";
        cout << "\n";
    }
}

1559D1.Mocha and Diana (Easy Version)

D1是一个暴力枚举 + 并查集的裸题，D2就懵逼了，不知道怎么维护

const int N = 2e3 + 10;
int f1[N], f2[N];
int find1(int x) {return f1[x] == x ? x : f1[x] = find1(f1[x]);}
int find2(int x) {return f2[x] == x ? x : f2[x] = find2(f2[x]);}
void merge1(int x, int y) { f1[find1(x)] = find1(y);}
void merge2(int x, int y) { f2[find2(x)] = find2(y);}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    for (int i = 1; i <= n; ++i) f1[i] = f2[i] = i;
    for (int i = 1, u, v; i <= m1; ++i) {
        cin >> u >> v;
        merge1(u, v);
    }
    for (int i = 1, u, v; i <= m2; ++i) {
        cin >> u >> v;
        merge2(u, v);
    }
    cout << min(n - m1 - 1, n - m2 - 1) << "\n";
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (j == i) continue;
            if (find1(i) != find1(j) && find2(i) != find2(j)) {
                f1[find1(i)] = find1(j);
                f2[find2(i)] = find2(j);
                cout << i << " " << j << '\n';
            }
        }
}

1559D2. Mocha and Diana (Hard Version)

struct DSU {
    vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1) {iota(f.begin(), f.end(), 0);}
    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
    bool same(int x, int y) {return find(x) == find(y);}
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) {return siz[find(x)];}
};
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    DSU f1(n), f2(n);
    for (int i = 0, u, v; i < m1; ++i) {
        cin >> u >> v;
        --u, --v;
        f1.merge(u, v);
    }
    for (int i = 0, u, v; i < m2; ++i) {
        cin >> u >> v;
        --u, --v;
        f2.merge(u, v);
    }
    int ans = n - 1 - max(m1, m2);
    cout << ans << "\n";
    vector<int> v1[n], v2[n];
    while (ans > 0) {
        for (int i = 0; i < n; ++i) v1[i].clear(), v2[i].clear();
        for (int i = 0; i < n; ++i) {
            v1[f1.find(i)].push_back(i);
            v2[f2.find(i)].push_back(i);
        }
        int i = 0, j = 0;
        while (1) {
            while (i < n && f1.find(i) != i) i += 1;
            while (j < n && f2.find(j) != j) j += 1;
            if (i == n || j == n) break;
            int a = -1, b = -1, c = -1, d = 0;
            for (auto x : v1[i]) {
                if (!f2.same(x, j)) a = x;
                else c = x;
            }
            for (auto x : v2[j]) {
                if (!f1.same(x, i)) b = x;
                else c = x;
            }
            if (a != -1 && b != -1) {
                cout << a + 1 << " " << b + 1 << "\n";
                f1.merge(a, b);
                f2.merge(b, a);
            } else {
                while (f1.same(d, i) || f2.same(d, j)) d += 1;
                cout << c + 1 << " " << d + 1 << "\n";
                f1.merge(c, d);
                f2.merge(c, d);
            }
            ans -= 1;
            i += 1, j += 1;
        }
    }
}

1559E. Mocha and Stars

E题在赛时没想到正解，现在学习一下官方的题解

~~说实话，似乎E题在多校见过？~~

首先让我们忽略 $Codeforces Round #738 (Div. 2) - 图17$ 的限制，令 $Codeforces Round #738 (Div. 2) - 图18$ #card=math&code=f%28%5Bl_1%2Cl_2%2C…%2Cl_n%5D%2C%5Br_1%2Cr_2%2C…%2Cr_n%5D%2CM%29&id=pGMUF) 为整数 $Codeforces Round #738 (Div. 2) - 图19$ #card=math&code=%28a_1%2Ca_2%2C..%2Ca_n%29&id=OAeBO) 的个数满足以下两个条件

$Codeforces Round #738 (Div. 2) - 图20$
对于所有的 i ， $Codeforces Round #738 (Div. 2) - 图21$ 都在 $Codeforces Round #738 (Div. 2) - 图22$ 范围之间

所以我们可以通过前缀和优化背包DP来达到在 $Codeforces Round #738 (Div. 2) - 图23$ #card=math&code=%5Cmathcal%7BO%7D%28nM%29&id=GyKCo) 内完成计算

此时再来考虑 $Codeforces Round #738 (Div. 2) - 图24$ 的约束条件，设 $Codeforces Round #738 (Div. 2) - 图25$ #card=math&code=%CE%BC%28n%29&id=XgTG3) 为莫比乌斯函数， $Codeforces Round #738 (Div. 2) - 图26$ #card=math&code=g%28a_1%2Ca_2%2C%E2%80%A6%2Ca_n%29&id=QOp5A)为 $Codeforces Round #738 (Div. 2) - 图27$ ，如果 $Codeforces Round #738 (Div. 2) - 图28$ #card=math&code=%28a_1%2Ca_2%2C%E2%8B%AF%2Ca_n%29&id=TY8n6) 满足我们提到的两个条件（没有 $Codeforces Round #738 (Div. 2) - 图29$ 的约束），否则为 $Codeforces Round #738 (Div. 2) - 图30$ 。

我们想要的答案是：

$Codeforces Round #738 (Div. 2) - 图31$ %3D1%5Dg(a1%2Ca_2%2C…%2Ca_n)%20%5C%5C%0A%3D%20%5Csum%5Climits%7Ba1%3Dl_1%7D%5E%7Br_1%7D%5Csum%5Climits%7Ba2%3Dl_2%7D%5E%7Br_2%7D…%5Csum%5Climits%7Ban%3Dl_n%7D%5E%7Br_n%7Dg(a_1%2Ca_2%2C…%2Ca_n)%5Csum%5Climits%7Bd%7C%5Cgcd(a1%2Ca_2%2C…%2Ca_n)%7D%CE%BC(d)%5C%5C%0A%3D%5Csum%5Climits%7Ba1%3Dl_1%7D%5E%7Br_1%7D%5Csum%5Climits%7Ba2%3Dl_2%7D%5E%7Br_2%7D…%5Csum%5Climits%7Ban%3Dl_n%7D%5E%7Br_n%7Dg(a_1%2Ca_2%2C…%2Ca_n)%5Csum%5Climits%7Bd%7Ca1%2Cd%7Ca_2%2C..%2Cd%7Ca_n%7D%CE%BC(d)%5C%5C%0A%3D%5Csum%5Climits%7Bd%3D1%7D%5EM%CE%BC(d)%5Csum%5Climits%7Ba_1%3D%E2%8C%88%5Cfrac%7Bl_1%7Dd%E2%8C%89%7D%5E%7B%E2%8C%8A%5Cfrac%7Br_1%7Dd%E2%8C%8B%7D…%5Csum%5Climits%7Ban%3D%E2%8C%88%5Cfrac%7Bl_n%7Dd%E2%8C%89%7D%5E%7B%E2%8C%8A%5Cfrac%7Br_n%7Dd%E2%8C%8B%7D%20g(a_1d%2Ca_2d%2C…%2Ca_nd)%0A%5Cend%7Barray%7D%0A#card=math&code=%5Cbegin%7Barray%7D%7Bll%7D%0A%5Csum%5Climits%7Ba1%3Dl_1%7D%5E%7Br_1%7D%5Csum%5Climits%7Ba2%3Dl_2%7D%5E%7Br_2%7D…%5Csum%5Climits%7Ban%3Dl_n%7D%5E%7Br_n%7D%5B%5Cgcd%28a_1%2Ca_2%2C…%2Ca_n%29%3D1%5Dg%28a_1%2Ca_2%2C…%2Ca_n%29%20%5C%5C%0A%3D%20%5Csum%5Climits%7Ba1%3Dl_1%7D%5E%7Br_1%7D%5Csum%5Climits%7Ba2%3Dl_2%7D%5E%7Br_2%7D…%5Csum%5Climits%7Ban%3Dl_n%7D%5E%7Br_n%7Dg%28a_1%2Ca_2%2C…%2Ca_n%29%5Csum%5Climits%7Bd%7C%5Cgcd%28a1%2Ca_2%2C…%2Ca_n%29%7D%CE%BC%28d%29%5C%5C%0A%3D%5Csum%5Climits%7Ba1%3Dl_1%7D%5E%7Br_1%7D%5Csum%5Climits%7Ba2%3Dl_2%7D%5E%7Br_2%7D…%5Csum%5Climits%7Ban%3Dl_n%7D%5E%7Br_n%7Dg%28a_1%2Ca_2%2C…%2Ca_n%29%5Csum%5Climits%7Bd%7Ca1%2Cd%7Ca_2%2C..%2Cd%7Ca_n%7D%CE%BC%28d%29%5C%5C%0A%3D%5Csum%5Climits%7Bd%3D1%7D%5EM%CE%BC%28d%29%5Csum%5Climits%7Ba_1%3D%E2%8C%88%5Cfrac%7Bl_1%7Dd%E2%8C%89%7D%5E%7B%E2%8C%8A%5Cfrac%7Br_1%7Dd%E2%8C%8B%7D…%5Csum%5Climits%7Ba_n%3D%E2%8C%88%5Cfrac%7Bl_n%7Dd%E2%8C%89%7D%5E%7B%E2%8C%8A%5Cfrac%7Br_n%7Dd%E2%8C%8B%7D%20g%28a_1d%2Ca_2d%2C…%2Ca_nd%29%0A%5Cend%7Barray%7D%0A&id=uIQ3M)

因为 $Codeforces Round #738 (Div. 2) - 图32$ 可以被改写成 $Codeforces Round #738 (Div. 2) - 图33$ ,等价于

$Codeforces Round #738 (Div. 2) - 图34$ f(%E2%8C%88%5Cfrac%20%7Bl1%7Dd%E2%8C%89%2C…%2C%E2%8C%88%5Cfrac%20%7Bl_n%7Dd%E2%8C%89%2C%E2%8C%8A%5Cfrac%20%7Br_1%7Dd%E2%8C%8B%2C…%2C%E2%8C%8A%5Cfrac%20%7Br_n%7Dd%E2%8C%8B%2C%E2%8C%8A%5Cfrac%20Md%E2%8C%8B)%0A#card=math&code=%5Csum%5Climits%7Bd%3D1%7D%5EM%CE%BC%28d%29f%28%E2%8C%88%5Cfrac%20%7Bl_1%7Dd%E2%8C%89%2C…%2C%E2%8C%88%5Cfrac%20%7Bl_n%7Dd%E2%8C%89%2C%E2%8C%8A%5Cfrac%20%7Br_1%7Dd%E2%8C%8B%2C…%2C%E2%8C%8A%5Cfrac%20%7Br_n%7Dd%E2%8C%8B%2C%E2%8C%8A%5Cfrac%20Md%E2%8C%8B%29%0A&id=kkQgB)

时间复杂度： $Codeforces Round #738 (Div. 2) - 图35$ %20%3D%20%5Cmathcal%7BO%7D(nM%5C%20log%5C%20M)#card=math&code=%5Cmathcal%7BO%7D%28n%5Csum%5Climits_%7Bi%3D1%7D%5EM%E2%8C%8A%5Cfrac%20Mi%E2%8C%8B%29%20%3D%20%5Cmathcal%7BO%7D%28nM%5C%20log%5C%20M%29&id=jTcTd)

#define maxn 100086
const int p = 998244353;
int n, m;
int l[maxn], r[maxn];
int f[maxn], sum[maxn];
int cal(int d) {
    int M = m / d;
    f[0] = 1;
    for (int i = 1; i <= M; i++) f[i] = 0;
    for (int i = 1; i <= n; i++) {
        int L = (l[i] + d - 1) / d, R = r[i] / d;
        if (L > R) return 0;
        for (int j = 0; j <= M; j++) sum[j] = (f[j] + (j ? sum[j - 1] : 0)) % p;
        for (int j = 0; j <= M; j++) {
            f[j] = ((j - L >= 0 ? sum[j - L] : 0) + p - (j - R - 1 >= 0 ? sum[j - R - 1] : 0)) % p;
        }
    }
    int ans = 0;
    for (int i = 1; i <= M; i++) ans = (ans + f[i]) % p;
    return ans;
}
int prm[maxn], cnt, mu[maxn];
bool tag[maxn];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i];
    mu[1] = 1;
    for (int i = 2; i <= m; i++) {
        if (!tag[i]) prm[++cnt] = i, mu[i] = p - 1;
        for (int j = 1; j <= cnt && prm[j] * i <= m; j++) {
            tag[i * prm[j]] = true;
            if (i % prm[j]) mu[i * prm[j]] = (p - mu[i]) % p;
            else break;
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) ans = (ans + 1ll * mu[i] * cal(i)) % p;
    cout << ans;
}

最后在看H神的代码时发现另外的一个代码思路

const int mod = 998244353;
void add(int &u, int v) {
    u += v;
    if (u >= mod) u -= mod;
}
void sub(int &u, int v) {
    u -= v;
    if (u < 0) u += mod;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<int> l(n), r(n);
    vector<int> np(m + 1), ans(m + 1), p;
    for (int i = 0; i < n; i += 1) cin >> l[i] >> r[i];
    for (int i = 2; i <= m; i += 1) {
        if (not np[i]) {
            p.push_back(i);
            for (int j = i * 2; j <= m; j += i) np[j] = 1;
        }
    }
    for (int i = 1; i <= m; i += 1) {
        vector<int> L(n), R(n);
        int M = m / i, ok = 1;
        for (int j = 0; j < n; j += 1) {
            L[j] = (l[j] + i - 1) / i;
            R[j] = r[j] / i;
            if (L[j] > R[j]) ok = 0;
            M -= L[j];
            R[j] -= L[j];
        }
        if (not ok or M < 0) continue;
        vector<int> dp(M + 1);
        dp[0] = 1;
        for (int j = 0; j < n; j += 1) {
            for (int i = 1; i <= M; i += 1) add(dp[i], dp[i - 1]);
            for (int i = M; i >= 0; i -= 1)
                if (i > R[j]) sub(dp[i], dp[i - R[j] - 1]);
        }
        for (int x : dp) add(ans[i], x);
    }
    for (int x : p)
        for (int i = 1; i * x <= m; i += 1)
            sub(ans[i], ans[i * x]);
    cout << ans[1];
}