CodeChef November Lunchtime 2020

jiangly · 2020-11-29 01:10:01 · 个人记录

由于是第一把 CC，0 rating，所以只做了 div.2，div.1 之后来补（

update : 补了（

Gasoline Introduction

模拟。

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::vector<int> a(n);
        for (int i = 0; i < n; ++i) std::cin >> a[i];
        int i = 0;
        int cur = a[0];
        while (i + 1 < n && cur > 0) {
            ++i;
            cur += a[i];
            --cur;
        }
        std::cout << i + cur << "\n";
    }

    return 0;
}

Gasoline

容易发现只要总油量达到 n 则一定存在合法的起点，贪心即可。

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::vector<std::pair<int, int>> a(n);
        for (int i = 0; i < n; ++i) std::cin >> a[i].second;
        for (int i = 0; i < n; ++i) std::cin >> a[i].first;
        std::sort(a.begin(), a.end());

        int64_t ans = 0;
        int res = n;
        for (int i = 0; i < n; ++i) {
            int t = std::min(res, a[i].second);
            ans += int64_t(t) * a[i].first;
            res -= t;
        }

        std::cout << ans << "\n";
    }

    return 0;
}

Xor Compare

数位 DP。

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        int x, y, n;
        std::cin >> x >> y >> n;
        ++n;

        int dp[32][2][2] {};
        dp[31][0][0] = 1;
        for (int i = 30; i >= 0; --i)
            for (int a = 0; a < 2; ++a)
                for (int b = 0; b < 2; ++b)
                    for (int v = 0; v < 2; ++v)
                        if ((a || v <= (n >> i & 1)) && (b || ((x >> i & 1) ^ v) <= ((y >> i & 1) ^ v)))
                            dp[i][a || v < (n >> i & 1)][b || ((x >> i & 1) ^ v) < ((y >> i & 1) ^ v)] += dp[i + 1][a][b];
        std::cout << dp[0][1][1] << "\n";
    }

    return 0;
}

Rook Path

建立二分图，每个车相当于一条边，求欧拉路径即可。

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        int n, m;
        std::cin >> n >> m;
        std::vector<std::vector<std::pair<int, int>>> e(2 * n);
        for (int i = 0; i < m; ++i) {
            int u, v;
            std::cin >> u >> v;
            --u, --v;
            v += n;
            e[u].emplace_back(v, i);
            e[v].emplace_back(u, i);
        }

        int s = -1;
        for (int i = 0; i < 2 * n; ++i)
            if (e[i].size() % 2 == 1) s = i;
        if (s == -1)
            for (int i = 0; i < 2 * n; ++i)
                if (!e[i].empty()) s = i;

        std::vector<int> cur(2 * n);
        std::vector<bool> vis(m);

        bool first = true;
        std::function<void(int, int)> dfs = [&](int u, int p) {
            for (int &i = cur[u]; i < int(e[u].size()); ) {
                auto [v, j] = e[u][i++];
                if (vis[j]) continue;
                vis[j] = true;
                dfs(v, j);
            }
            if (p != -1) {
                if (!first) std::cout << " ";
                std::cout << p + 1;
                first = false;
            }
        };
        dfs(s, -1);
        std::cout << "\n";
    }

    return 0;
}

Fractions

得到的分数为 \frac{ij+i}{ij+j}，它是好分数的条件是 \frac{j-i}{ij+j} 约分后形如 \frac 1m，即 (j-i)\mid(ij+j)。

设 j=i+k，则条件等价于 k\mid(i+1)(i+k)，即 k\mid i(i+1)。问题变成求每个 i(i+1) 有多少个不超过 n-i 的约数。由于 i 和 i+1 互素，因此 i(i+1) 的约数和 (i 的约数，i+1 的约数) 数对一一对应。枚举 i 的约数，用一个指针扫 i+1 的约数即可。

时间复杂度 O(n\log n)，有点卡常。

#include <bits/stdc++.h>

constexpr int N = 1e6;

int pool[20000000];
int *d[N + 2], *cur[N + 1];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    int ans = 0;
    std::vector<int> cntd(n + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) ++cntd[j];
    d[1] = pool;
    for (int i = 1; i <= n; ++i) d[i + 1] = d[i] + cntd[i];
    for (int i = 1; i <= n; ++i) cur[i] = d[i];
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) *(cur[j]++) = i;

    for (int i = 1; i < n; ++i) {
        int *j = d[i + 1];
        for (int k = cntd[i] - 1; k >= 0; --k) {
            while (j != d[i + 2] && int64_t(d[i][k]) * *j <= n - i) ++j;
            ans += j - d[i + 1];
        }
    }

    std::cout << ans << "\n";

    return 0;
}

Circle Eating

吃掉 A_1 之后，实际上是一个序列上的问题，每次选择首尾的一个数吃掉。

我们把从首尾吃掉连续的一段成为一次操作，如果一次操作没有使得总和增加则显然不优秀 (除了最后一次必须全部吃完)。既然总和一直在增加，每次选择最小前缀和最大的操作即可。

时间复杂度 O(N)。

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::vector<int> a(n);
        for (int i = 0; i < n; ++i) std::cin >> a[i];

        std::vector<int64_t> pre(n + 1);
        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + a[i];

        std::vector<int> lNext(n + 1, -1), rNext(n + 1, -1);
        std::vector<int64_t> lPre(n + 1), rPre(n + 1);

        int64_t preMin = 0, preSum = 0;
        for (int i = 1, j = 1; i < n; ++i) {
            preSum += a[i];
            preMin = std::min(preMin, preSum);
            if (preSum > 0) {
                lNext[j] = i + 1;
                lPre[j] = preMin;
                j = i + 1;
                preSum = preMin = 0;
            }
        }

        preSum = preMin = 0;
        for (int i = n - 1, j = n; i >= 1; --i) {
            preSum += a[i];
            preMin = std::min(preMin, preSum);
            if (preSum > 0) {
                rNext[j] = i;
                rPre[j] = preMin;
                j = i;
                preSum = preMin = 0;
            }
        }

        int64_t ans = a[0], cur = a[0];

        int l = 1, r = n;
        while (l < r) {
            int a = lNext[l];
            int b = rNext[r];
            if (a > r) a = -1;
            if (b < l) b = -1;

            if (a == -1 && b == -1) {
                ans = std::min(ans, pre[n]);
                break;
            }

            int64_t va, vb;
            if (a == -1) va = -1e18;
            else va = cur + lPre[l];

            if (b == -1) vb = -1e18;
            else vb = cur + rPre[r];

            if (va > vb) {
                ans = std::min(ans, va);
                l = a;
            } else {
                ans = std::min(ans, vb);
                r = b;
            }

            cur = pre[n] - (pre[r] - pre[l]);
        }

        std::cout << ans << "\n";
    }

    return 0;
}

Circle Coloring

如果是序列上的问题，显然可以直接 DP，复杂度 O(\sum_{i=1}^N |A_i|)。

记 M=\sum_{i=1}^N|A_i|。如果 N\ge \sqrt M，那么最小的一个集合大小一定不超过 \sqrt M，枚举这个集合选择的数，就可以转化成序列上问题，复杂度 O(M\cdot \min_{i=1}^N\{|A_i|\})。如果 N<\sqrt M，那么考虑容斥，即先假设是序列上问题，再减掉 a_1=a_N 的方案数。后者其实就是把 A_1 和 A_n 变成它们的交之后的环上问题，可以递归解决。每次递归会使得 N 减少 1，故总复杂度 O(NM)。

结合起来的复杂度即为 O(M^{1.5})。

#include <bits/stdc++.h>

constexpr int P = 998244353;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<std::vector<int>> a(n);

    int maxA = 0;

    for (int i = 0; i < n; ++i) {
        int m;
        std::cin >> m;
        a[i].resize(m);
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
            maxA = std::max(maxA, a[i][j]);
            a[i][j]--;
        }
        std::sort(a[i].begin(), a[i].end());
    }

    int ans = 0;
    if (n >= 400) {

        int k = 0;
        for (int i = 0; i < n; ++i)
            if (a[i].size() < a[k].size()) k = i;

        std::rotate(a.begin(), a.begin() + k, a.end());

        std::vector<int> dp, g;
        for (int i = 0; i < int(a[0].size()); ++i) {
            dp.assign(maxA, 0);
            g.assign(maxA, 0);
            dp[a[0][i]] = 1;
            int sum = 1;
            for (int j = 1; j < n; ++j) {
                int nSum = 0;
                for (auto x : a[j]) {
                    dp[x] = (sum - (g[x] == j - 1 ? dp[x] : 0) + P) % P;
                    nSum = (nSum + dp[x]) % P;
                    g[x] = j;
                }
                sum = nSum;
            }
            ans = (ans + sum - (g[a[0][i]] == n - 1 ? dp[a[0][i]] : 0)) % P;
        }
        ans = (ans + P) % P;

    } else {

        auto solve = [&](auto self, auto &a) {
            if (a.size() == 1) return 0;

            int n = a.size();

            std::vector<int> dp(maxA), g(maxA);
            int sum = 1;
            for (int j = 0; j < n; ++j) {
                int nSum = 0;
                for (auto x : a[j]) {
                    dp[x] = (sum - (g[x] == j - 1 ? dp[x] : 0) + P) % P;
                    nSum = (nSum + dp[x]) % P;
                    g[x] = j;
                }
                sum = nSum;
            }
            int ans = sum;

            std::vector<int> inter(a[0].size());
            inter.erase(std::set_intersection(a[0].begin(), a[0].end(), a[n - 1].begin(), a[n - 1].end(), inter.begin()), inter.end());
            a.pop_back();
            a[0] = std::move(inter);

            ans = (ans - self(self, a) + P) % P;
            return ans;
        };

        ans = solve(solve, a);
    }

    std::cout << ans << "\n";

    return 0;
}