Educational Codeforces Round 183 (Rated for Div. 2)

Educational Codeforces Round 183 (Rated for Div. 2)

A	B	C	D	E	F	G
O	O	O	O	O	Ø

F - Long Journey

在一个数轴上，有一个从 $0$ 号单元格移动到 $m$ 号单元格的芯片。

总共有 $n$ 种陷阱，第 $i$ 种陷阱的规则是：在第 $k$ 次移动结束时，如果 $k \equiv i \pmod n$，那么所有满足 $x \bmod a_i = b_i$ 的单元格 $x$ 都会激活陷阱。

每次移动，芯片可以前进一格或停在原地。如果在某次移动开始时，芯片位于一个已经激活的陷阱中，则游戏失败。

目标是计算到达单元格 $m$ 所需的最小移动次数。注意，在到达 $m$ 的那一回合结束时，如果 $m$ 处的陷阱被激活，这不算作一次成功的到达。

$2 \le a_i \le 10$, $1 \le n \le 10$; $1 \le m \le 10^{12}$

状态只和位置 $x$ 和回合数 $r$ 有关。

$x$ 有周期 $L = \text{lcm}(a_1, a_2, \dots, a_n)$

$r$ 有周期 $n$

状态数是 $O(\text{lcm}(a_1, a_2, \dots, a_n) \cdot n) = O(25200)$

首先对于一个状态而言，转移是确定的，而且这是一张有向图，出度为 $1$

如果这张图没有环，我们跑一次也就是 $O(25200)$，有环的话用环加速转移即可

void solve() {
    int n = read();
    int m = read();

    vector<int> a(n), b(n);
    for (auto &x : a) x = read();
    for (auto &x : b) x = read();

    int L = 1;
    for (auto x : a) L = lcm(L, x);

    int N = L * n;
    
    vector safe(L, vector(n, 1ll));
    for (int x = 0; x < L; x++) {
        for (int t = 0; t < n; t++) {
            int i = (t - 1 + n) % n;
            if (x % a[i] == b[i]) {
                safe[x][t] = 0;
            }
        }
    }

    vector f(N, -1ll), cost(N, 0ll);
    auto get = [&](int id) -> void {
        if (f[id] != -1) return;

        int x = id / n;
        int r = id % n;

        for (int w = 0; w < n; w++) {
            int ok = 1;
            for (int k = 1; k <= w; k++) {
                int t = (r + k) % n;
                if (!safe[x][t]) { ok = 0; break; }
            }
            if (!ok) continue;

            int nx = (x + 1) % L;
            int nr = (r + w + 1) % n;
            int nid = nx * n + nr;
            if (safe[nx][nr]) {
                f[id] = nid;
                cost[id] = w + 1;
                return;
            }

        }

        f[id] = -2;
    };

    vector sum(N, 0ll), d(N, -1ll);
    int id = 0, tot = 0, step = 0;
    int cur = id;

    while (step < m and d[cur] == -1) {
        d[cur] = step;
        sum[cur] = tot;

        get(cur);
        if (f[cur] == -2) { cout << "-1\n"; return; }

        tot += cost[cur];
        cur = f[cur];
        step++;
    }

    if (step == m) { 
        cout << tot << '\n';
    } else {
        int clen = step - d[cur];
        int ccost = tot - sum[cur];
        int need = m - d[cur];
        int ans = sum[cur] + need / clen * ccost;
        for (int i = 0; i < need % clen; i++) {
            get(cur);
            ans += cost[cur];
            cur = f[cur];
        }
        cout << ans << '\n';
    }
}

E - Predicting Popularity

把值扔到桶里面，对桶做前缀和

条件转化一下，在线段树上面二分就做完了

struct Tag {
    int x = 0;
    void apply(const Tag &t) & {
        x += t.x;
    }
};

struct Info {
    int x = inf;
    Info() = default;
    Info(int v) : x(v) {} 
    void apply(const Tag &t) & {
        x += t.x;
    }
};

Info operator+(const Info &a, const Info &b) {
    return {min(a.x, b.x)};
}


void solve() {
    int ac = read();
    int dr = read();
    int n = read();
    vector<int> a(n + 1), d(n + 1);
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) d[i] = read();

    auto calc = [&](int i) -> int {
        int res = max(a[i] - ac, 0ll) + max(d[i] - dr, 0ll);
        return min(n + 1, res);
    };

    vector<int> cnt(n + 2);
    for (int i = 1; i <= n; i++) {
        cnt[calc(i)]++;
    }
    vector<int> pre(n + 3);
    for (int i = 1; i <= n + 1; i++) {
        pre[i] = pre[i - 1] + cnt[i - 1];
    }
    auto f = pre;
    for (int i = 0; i <= n + 1; i++) f[i] -= i;
    LazySegmentTree<Info, Tag> seg(f);
    // debug(seg.n);

    int m = read();
    while (m--) {
        int k = read();
        int na = read();
        int nd = read();


        seg.rangeApply(calc(k) + 1, n + 2, {-1});
        a[k] = na, d[k] = nd;
        seg.rangeApply(calc(k) + 1, n + 2, {+1});

        int res = seg.findFirst(0, n + 2, [&](auto i) {
            return i.x < 0;
        });
        if (res == -1) res = n + 1;
        cout << res - 1 << '\n';
    }
}

D - Inversion Value of a Permutation

记得以前做到个是构造对应逆序对数量，但这个不太一样。

考虑先倒着排让区间数量最大，然后翻转一个区间的收益是和区间长度 $x$ 有关的，为 $\frac{x(x - 1)}{2}$

对这个背包一下

int val(int x) { return x * (x - 1) / 2; }
const int N = 30 * 30;
int f[N], g[N];
void init() {
    for (int i = 1; i < N; i++) {
        f[i] = 1e9;
        for (int j = 2; val(j) <= i; j++) {
            if (f[i - val(j)] + j < f[i]) {
                f[i] = f[i - val(j)] + j;
                g[i] = j;
            }
        }
    }
}

void solve() {
    int n = read();
    int k = read();

    vector<int> a(n);
    ranges::iota(a, 0);
    ranges::reverse(a);

    k = val(n) - k;
    for (int i = 0; i < n and k; ) {
        int len = g[k];
        if (i + len > n) break;
        reverse(a.begin() + i, a.begin() + i + len);

        k -= val(len);
        i += len;
    }

    if (k) {
        cout << "0\n";
    } else {
        for (auto x : a) cout << x + 1 << " ";
        cout << '\n';
    }
}

C - Monocarp’s String

看成 +1 / -1。删掉区间使得总和为 0，求最小长度

B - Deck of Cards

void solve() {
    int n = read();
    int k = read();
    string s; cin >> s;

    int cnt[3] { };
    for (auto c : s) {
        ++cnt[c - '0'];
    }

    string ans;
    for (int i = 1; i <= n; ++ i) {
        if (cnt[0] < i and cnt[1] <= n - i) {
            if (cnt[0] + cnt[2] < i and cnt[1] + cnt[2] <= n - i) {
                ans += '+';
            } else {
                if (cnt[0] + cnt[1] + cnt[2] == n) {
                    ans += '-';
                } else {
                    ans += '?';
                }
            }
        } else {
            ans += '-';
        }
    }
    cout << ans << '\n';
}

A - Candies for Nephews

void solve() {
    int n = read();
    int ans = (n + 2) / 3 * 3 - n;
    cout << ans << '\n';
}