2004(EDU169div2)

A. Closest Point

考虑直线上的一组点。两点 $i$ 和 $j$ 之间的距离为 $| i - j |$ .

如果集合中没有其他点 $k$ ，使得 $j$ 到 $k$ 的距离严格地小于 $j$ 到 $i$ 的距离，那么集合中的点 $i$ 是最接近集合中的点 $j$ 的。换句话说，集合中所有其他点到 $j$ 的距离都大于或等于 $| i - j |$ 。

给你一组点。你必须在这个集合中加入一个整数的点，使它与集合中现有的每一个点不同，并且它成为与集合中每一个点**最近的点。这可能吗？

void solve() {
    int n;cin >> n;
    set<int>s;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;s.insert(x);
    }
    if (s.size() == 2) {
        int a = *s.begin(), b = *++s.begin();
        if (abs(a - b) >= 2) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    } else {
        cout << "NO\n";
    }
}

B. Game with Doors

有 $100$ 个房间排成一排，它们之间有 $99$ 扇门； $i$ 扇门连接着 $i$ 和 $i + 1$ 两个房间。每扇门都可以上锁或不上锁。最初，所有的门都没有上锁。

如果房间 $x$ 和房间 $y$ 之间的所有门都没有上锁，我们就说房间 $x$ 可以从房间 $y$ 到达。

你知道吗？

爱丽丝在 $[l, r]$ 段的某个房间里；
鲍勃在 $[L, R]$ 段的某个房间里；
爱丽丝和鲍勃在不同的房间。

但是，你并不知道他们具体在哪个房间。

你不想让爱丽丝和鲍勃接触到对方，所以你要锁上一些门来防止他们接触到对方。无论爱丽丝和鲍勃在给定段落中的起始位置如何，要使他们不能相遇，你必须锁上的门的最小数目是多少？

wa 了一发，完全不应该的，思路都已经完全正确了... 注意点

void solve() {
    int l, r, L, R;cin >> l >> r >> L >> R;
    if (l > L) {
        swap(l, L);swap(r, R);
    } else if (l == L && r < R) {
        swap(l, L);swap(r, R);
    }
    if (r < L) {
        cout << "1\n";return;
    }
    if (L >= l && R <= r) {
        int ans = R - L + 2;
        if (L == l)ans--;
        if (R == r)ans--;
        cout << ans << '\n';return;
    }
    cout << r - L + 2 << '\n';
}

C. Splitting Items

爱丽丝和鲍勃有 $n$ 件物品想平分，于是他们决定玩一个游戏。所有物品都有成本， $i$ （一件）物品的成本为 $a_{i}$ 。玩家从爱丽丝开始轮流移动。

在每个回合中，玩家从剩下的物品中选择一个并拿走。游戏一直进行到没有物品为止。

假设 $A$ 是爱丽丝拿走物品的总费用， $B$ 是鲍勃拿走物品的总费用。这样，游戏的得分就等于 $| A - B |$ 。

爱丽丝希望得分最大化，而鲍勃希望得分最小化。爱丽丝和鲍勃都会以最优方式下棋。

但游戏将在明天进行，所以今天鲍勃可以稍微修改一下成本。他可以将几项（可能一项都不增加，也可能全部增加）物品的成本 $a_{i}$ 增加一个整数值（可能增加相同的值，也可能每项增加不同的值）。但是，增加的总金额必须小于或等于 $k$ 。否则，爱丽丝可能会怀疑。请注意，鲍勃不能减少成本，只能增加成本。

鲍勃可能获得的最低分数是多少？

wa 4 发，不知道为什么错了，奇奇怪怪的

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end(), greater<int>());
    int ans = 0;
    for (int i = 1;i <= (n & 1 ? n - 1 : n);i++) {
        if (i & 1)ans += a[i];
        else ans -= a[i];
    }
    ans = max(ans - k, 0ll);
    if (n & 1)ans += a[n];
    cout << ans << '\n';
}

不知道为什么会错的：

对拍了一下，HACK 数据：

9 106
933 879 781 765 656 360 238 202 120

UPD：发现错误：a[i] = a[i - 1];k -= a[i - 1] - a[i]; 顺序反了，真是个傻逼。。。。

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end(), greater<int>());
    for (int i = 2;i <= n;i += 2) {
        if (a[i - 1] - a[i] <= k) {
            k -= a[i - 1] - a[i];a[i] = a[i - 1];
        } else {
            a[i] += k;k = 0;
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        if (i & 1)ans += a[i];
        else ans -= a[i];
    }
    cout << ans << '\n';
}

D. Colored Portals

在一条直线上有 $n$ 座城市。这些城市的编号从 $1$ 到 $n$ 。

传送门用于在城市之间移动。传送门有 $4$ 种颜色：蓝色、绿色、红色和黄色。每个城市都有两种不同颜色的传送门。如果城市 $i$ 和城市 $j$ 的传送门颜色相同，则可以从城市 $i$ 移动到城市 $j$ （例如，可以在 "蓝-红 "城市和 "蓝-绿 "城市之间移动）。这种移动需要花费 $| i - j |$ 枚金币。

你的任务是回答 $q$ 个独立的问题：计算从城市 $x$ 移动到城市 $y$ 的最小花费。

Solution

二分

表面看是最短路，其实仔细想想就知道不是这个做法

思路：

从题目可以知道，一共六种组合，若出现两个城市无法配对的问题，则最多只用中转一次就能到另外一个城市

若除了 $x, y$ 颜色没有其他颜色的城市了，则无法到达，否则一定能找到一个城市作为中转达到另外一个城市。

现在就有另外一个问题：如何在其他不同颜色的所有城市中找到使得 $| i - k | + | j - k |$ 最小的值呢？

如果能找到一个 $k$ 使得 $i < k < j$ ，则这时答案就是 $j - i$ .

若不能找到这样的 $k$ ，则每次二分的去寻找使得答案相对最小的，即距离 $i$ 或 $j$ 最近的 $k$ 即可，在这里面取最小值即可。

思路完全正确，但是写代码写错了... 正确代码如下：

const string tar[] = {"BG", "BR", "BY", "GR", "GY", "RY"};
void solve() {
    int n, q;cin >> n >> q;
    vector<string> s(n + 1);
    vector<vector<int>> idx(6);
    for (int i = 0;i < 6;i++)idx[i].push_back(0);
    for (int i = 1;i <= n;i++) {
        cin >> s[i];
        for (int j = 0;j < 6;j++)if (s[i] == tar[j])idx[j].push_back(i);
    }
    for (int i = 0;i < 6;i++)idx[i].push_back(1e9);

    while (q--) {
        int x, y;cin >> x >> y;
        if (x > y)swap(x, y);
        if (s[x][0] == s[y][0] || s[x][0] == s[y][1] || s[x][1] == s[y][1] || s[x][1] == s[y][0]) {
            cout << y - x << '\n';continue;
        }
        int ok = 0;
        for (int i = 0;i < 6;i++) {
            if (tar[i] == s[x] || tar[i] == s[y] || !idx[i].size()) continue;
            auto k = lower_bound(idx[i].begin(), idx[i].end(), x);
            if (*k != 1e9 && *k < y) {
                ok = 1;break;
            }
        }
        if (ok) {
            cout << y - x << '\n';continue;
        }
        int ans = 1e9;
        for (int i = 0;i < 6;i++) {
            if (tar[i] == s[x] || tar[i] == s[y] || !idx[i].size()) continue;
            auto k1 = lower_bound(idx[i].begin(), idx[i].end(), x);
            if (*k1 != 1e9) {
                ans = min(ans, *k1 - y + *k1 - x);
            }
            auto k2 = upper_bound(idx[i].begin(), idx[i].end(), x);
            --k2;
            if (*k2 != 0) {
                ans = min(ans, x + y - *k2 - *k2);
            }
        }
        if (ans == 1e9)ans = -1;
        cout << ans << '\n';
    }
}

其实代码还可以简化:

const string tar[] = {"BG", "BR", "BY", "GR", "GY", "RY"};
void solve() {
    int n, q;cin >> n >> q;
    vector<string> s(n + 1);
    vector<vector<int>> idx(6);
    for (int i = 0;i < 6;i++)idx[i].push_back(0);
    for (int i = 1;i <= n;i++) {
        cin >> s[i];
        for (int j = 0;j < 6;j++)if (s[i] == tar[j])idx[j].push_back(i);
    }
    for (int i = 0;i < 6;i++)idx[i].push_back(1e9);

    while (q--) {
        int x, y;cin >> x >> y;
        if (x > y)swap(x, y);
        if (s[x][0] == s[y][0] || s[x][0] == s[y][1] || s[x][1] == s[y][1] || s[x][1] == s[y][0]) {
            cout << y - x << '\n';continue;
        }
        int ans = 1e9;
        for (int i = 0;i < 6;i++) {
            if (tar[i] == s[x] || tar[i] == s[y] || !idx[i].size()) continue;
            auto k = lower_bound(idx[i].begin(), idx[i].end(), x);
            if (*k != 1e9) {
                ans = min(ans, abs(*k - y) + *k - x);
            }
            --k;
            if (*k != 0) {
                ans = min(ans, x + y - *k - *k);
            }
        }
        if (ans == 1e9)ans = -1;
        cout << ans << '\n';
    }
}

E. Not a Nim Problem

爱丽丝和鲍勃正在玩一个游戏。他们有 $n$ 堆棋子，其中 $i$ 堆最初有 $a_{i}$ 颗棋子。

在他们的回合中，玩家可以选择任意一堆石子，并从中取出任意正数的石子，但有一个条件：

让当前石堆中的石子数量为 $x$ 。从棋子堆中取走 $y$ ，使得 $x$ 和 $y$ 的最大公约数等于 1。

无法下棋的棋手输棋。两位棋手都以最佳状态下棋（也就是说，如果一位棋手的策略能让他获胜，那么无论对手如何回应，他都会获胜）。爱丽丝先下。

确定谁会赢。

Solution

博弈论 /SG 函数

EDU：学习博弈论

可以先暴力列出 $s g$ 函数，根据 sg 函数的值来找规律：

void solve() {
    constexpr int N = 500;
    vector<int> sg(N);
    for (int i = 1;i < N;i++) {
        set<int>s;
        for (int j = 1;j <= i;j++) {
            if (__gcd(i, j) == 1) {
                s.insert(sg[i - j]);
            }
        }
        int idx = 0;
        for (auto x : s) {
            if (x == idx)idx++;
        }
        sg[i] = idx;
    }
    vector<vector<int>> q(N);
    for (int i = 0;i < N;i++)q[sg[i]].push_back(i);
    for (int i = 0;i < N;i++) {
        cout << i << ": ";
        for (auto x : q[i])cout << x << " ";
        cout << '\n';
    }
}

得到 $s g_{0 \sim 99}$ ：

0 1 0 2 0 3 0 4 0 2 0 5 0 6 0 2 0 7 0 8 0 2 0 9 0 3 0 2 0 10 0 11 0 2 0 3 0 12 0 2 0 13 0 14 0 2 0 15 0 4 0 2 0 16 0 3 0 2 0 17 0 18 0 2 0 3 0 19 0 2 0 20 0 21 0 2 0 4 0 22 0 2 0 23 0 3 0 2 0 24 0 4 0 2 0 3 0 25 0 2

$q_{0 \sim 99}$ : (即 $q_{s g_{i}}$ )

0: 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 
1: 1 
2: 3 9 15 21 27 33 39 45 51 57 63 69 75 81 87 93 99 
3: 5 25 35 55 65 85 95 
4: 7 49 77 91 
5: 11 
6: 13 
7: 17 
8: 19 
9: 23 
10: 29 
11: 31 
12: 37 
13: 41 
14: 43 
15: 47 
16: 53 
17: 59 
18: 61 
19: 67 
20: 71 
21: 73 
22: 79 
23: 83 
24: 89 
25: 97

易得

当 $i$ 为偶数时 $s g_{i} = 0$
只看第一项，从 2 开始，之后的每一项是 $3, 5, 7, 11, \dots$ 都是质数项即 $s g_{3} = 2, s g_{5} = 3, \dots, \to s g_{p r i m e s_{i}} = i + 1$
在一个值 $x$ 对应多个 $s g_{i}$ 时，可以发现后面的数的最小质因数就是第一个质数，即:
$s g_{{l i s t}} = x$ ， ${i n l i s t \cap i > 0 : m i n p [l i s t_{i}] = l i s t_{0}}$

则有： $s g_{p r i m e s_{i} = i + 1}$ ， $s g_{i} = s g_{m i n p_{i}}$

constexpr int N = 1e7;
int sg[N + 1];
void solve() {
    int n;cin >> n;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;ans ^= sg[x];
    }
    if (ans != 0) {
        cout << "Alice\n";
    } else {
        cout << "Bob\n";
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    sieve(N);
    sg[0] = 0;sg[1] = 1;sg[2] = 0;
    for (int i = 1;i < primes.size();i++) {
        sg[primes[i]] = i + 1;
    }
    for (int i = 3;i <= N;i++) {
        sg[i] = sg[minp[i]];
    }
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
}