Educational Codeforces Round 169 (Rated for Div. 2)

比赛链接

Problems	AC
A. Closest Point	○
B. Game with Doors	○
C. Splitting Items	○
D. Colored Portals	○
E. Not a Nim Problem	⊕
F. Make a Palindrome
G. Substring Compression

A

只能是 2 个点的情况，且得有空隙插

B

分类讨论区间包含情况即可

C

策略是唯一的

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

    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = read();
    std::sort(a.rbegin(), a.rend());

    int ans = 0;
    for (int i = 1; i < n; i += 2) {
        int t = min(k, a[i - 1] - a[i]);
        k -= t, a[i] += t;
    }

    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) ans += a[i];
        else ans -= a[i];
    }

    cout << ans << '\n';
}

D

要么是可以直接跳，要么是向左或者向右各找一个最近的跳看看哪个小。如果不是最近的话肯定劣于最近的。预处理一下即可。

const std::string color = "BGRY";

int id(int x, int y) {
    if (x > y) swap(x, y);
    return y * (y - 1) / 2 + x;
}

void solve() {
    int n = read(), q = read();
    
    vector<std::array<int, 2>> c(n + 2);
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        
        for (int j = 0; j < 2; j++) {
            c[i][j] = color.find(s[j]);
        }
    }

    vector<std::array<int, 6>> pre(n + 1), nxt(n + 1);

    for (int i = 1; i <= n; i++) {
        if (i == 1) pre[i].fill(0);
        else pre[i] = pre[i - 1];
        pre[i][id(c[i][0], c[i][1])] = i;
    }
    for (int i = n; i >= 1; i--) {
        if (i == n) nxt[i].fill(n + 1);
        else nxt[i] = nxt[i + 1];
        nxt[i][id(c[i][0], c[i][1])] = i;
    }

    for (int i = 0; i < q; i++) {
        int x = read(), y = read();
        int ans = 1e9;
        if (x > y) swap(x, y);
        for (auto a : c[x]) {
            for (auto b : c[y]) {
                if (a == b) ans = y - x;
                else {
                    int w = id(a, b);
                    for (auto z : {nxt[x][w], pre[y][w]}) {
                        if (1 <= z and z <= n) {
                            ans = min(ans, abs(x - z) + abs(y - z));
                        }
                    }
                }
            }
        }

        cout << (ans == 1e9 ? -1 : ans) << "\n";
    }
}

E 博弈论

给定 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。对于每次操作，玩家可以选择任意一堆石子，设其还剩 $x$ 个，若玩家可以从中取走 $y$ 个，当且仅当 $\gcd(x,y) = 1$。不能取石子的人输，问先手是否必胜。

发现每堆游戏是相对独立的，可以计算每堆的 SG 函数 值，然后将这些值进行异或运算，以判断当前状态是否为必胜（即结果是否为 $0$）

首先可以观察到 $SG(0) = 0, SG(1) = 1, SG(2) = 0$

进一步地，打表发现：质数的 $SG$ 值是连续的（$2$ 除外）；且合数的 $SG$ 值等于其最小质因子的 $SG$ 值。

用数学归纳法不难证明。

实现时可以考虑用线性筛，因为线性筛时每个合数会被其最小的质因数筛到。

std::vector<int> minp, primes, sg;
void sieve(int n) {
    minp.assign(n + 1, 0), primes.clear();
    sg.assign(n + 1, 0);
    sg[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i, primes.push_back(i);
            sg[i] = primes.size();
        }
        sg[2] = 0;

        for (auto p : primes) {
            if (i * p > n) break;
            minp[i * p] = p;
            sg[i * p] = sg[p];
            if (p == minp[i]) break;
        }
    }
}

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

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans ^= sg[read()];
    }
    puts(ans ? "Alice" : "Bob");
}