Codeforces Global Round 29(1+2)

A

注意到我们先走的一步必须小于后走的一步

• 当 $x<y$时候一步$x$一步$y$即可
• 当$y=1$ 时候无论如何走都无法走到
• 当$x>y$ 时候，必须满足$x-1>y$因为第一步走1,然后走向上走$y$，最后走到$(x,y)$,即三步

Ac solution

void solve()
{
    i64 x, y;
    cin >> x >> y;
    if (x < y) {
        cout << 2 << endl;
        return;
    }
    if (x - 1 > y && y != 1) {
        cout << 3 << endl;
        return;
    }
    cout << -1 << endl;
    return;
}

B

我们的目标是将2个一样的$n$排列放入一个长度为$2n$的数组中并且两个相同元素下标差为当前元素的倍数

注意到这样的排序：

$$[n,n-1,\cdots ,3,2,1,n,1,2,3,\cdots ,n-1]$$

满足题意

同样成立的还有

先排序所有偶数，在结果{$\cdots ,2,x,2,\cdots$}中的x位置填入最大奇数，然后以此往下排列即可

Ac solution

void solve()
{
    i64 n;
    cin >> n;
    vector<i64> res(2 * n + 1);
    i64 idx = 1;
    for (i64 i = n; i >= 1; i--) {
        if (i % 2 == 0) {
            res[idx] = i;
            res[idx + i] = i;
            idx++;
        }
    }
    idx = n / 2 + 1;
    for (i64 i = n; i >= 1; i--) {
        if (i & 1) {
            res[idx] = i;
            if (i == 1) {
                res[2 * n] = 1;
                break;
            }
            res[idx + i] = i;
            while (res[idx] != 0) {
                idx++;
            }
        }
    }
    for (i64 i = 1; i <= 2 * n; i++) {
        cout << res[i] << " ";
    }
 
    cout << endl;
}

C

思维题，考虑下面情况

• “1010” : 选择两个兔子互相向下标2位置跳，冲突，得以固定

• “11011”: 无约束，兔子任意跳跃，无法固定

• “1010101”: 对于下标1,3兔子可以用第一种方式固定，但是对于下标为5的兔子就无法固定

• “000” ：兔子互相面向跳跃，得以固定

我们不难看出，只需要寻找类似 “101010…”的交替子串就可以确定这一堆兔子能否被固定，具体而言，就是当交替子串的’0’个数是偶数时候可以固定，遍历一遍即可，复杂度$O(n)$

Ac solution

void solve()
{
    i64 n;
    string s;
    cin >> n >> s;
 
    bool ok = 1;
    for (i64 i = 0; i < n && ok;) {
        i64 j = i;
        while (j + 1 < n && s[j + 1] != s[j]) j++;
        if (s[i] == '1' && s[j] == '1') {
            i64 cnt0 = 0;
            for (i64 k = i; k <= j; k++)
                if (s[k] == '0') cnt0++;
            if (cnt0 & 1) ok = 0;
        }
        i = j + 1;
    }
 
    cout << (ok ? "YES" : "NO") << endl;
}

D

我说 D << C

显然对于偶数，其对差值的贡献为0,我们只需要考虑奇数的情况，排序然后模拟就好了，每次经过一次奇数，下一次奇数都会是对方先选，所以Alice一定会先选最大的奇数

主要是排序贡献的复杂度$O(n\log n)$

Ac solution

void solve()
{
    i64 n;
    cin >> n;
    vint v(n);
    map<i64, i64> mp;
    for (i64 i = 0; i < n; i++) {
        cin >> v[i];
        mp[v[i]]++;
    }
    vpii vp(all(mp));
    ranges::sort(vp, [](pii a, pii b) { return a.second > b.second; });
    i64 ans1 = 0, ans2 = 0;
    i64 cur = 0;
    for (auto &&[a, b] : vp) {
        if (a % 2 == 0) {
            ans1 += b * (a / 2);
            ans2 += b * (a / 2);
        }
        else {
            if (cur == 0) {
                ans1 += b * ((a + 1) / 2);
                ans2 += b * (a / 2);
            }
            else {
                ans2 += b * ((a + 1) / 2);
                ans1 += b * (a / 2);
            }
            cur ^= 1;
        }
    }
    cout << ans1 << " " << ans2 << endl;
}