A. Treasure Chest

分类讨论一下，只有两种情况。

1. 走到钥匙处，然后走到箱子处
2. 走到箱子处，移动箱子，走到钥匙处，走回箱子处

对于第二种情况可以直接枚举箱子被移动到的位置

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;


void solve() {
    int x, y, k;
    cin >> x >> y >> k;
    int res = abs(y - 0) + abs(x - y);
    for (int i = x - k, cnt; i <= x + k; i++) {
        cnt = abs(x - 0) + abs(x - i) + 2 * abs(i - y);
        res = min(res, cnt);
    }
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

B. Points and Minimum Distance

这里面有个比较好想的结论是不要走回头路。

把所有的点排序一下，然后考虑把点分开，首先\(a_1\)一定是起点，要找到\(n-1\)个点到\(a_1\)的距离和最小，显然是\(a_2,a_3,\dots,a_n\)，则取这些点做横坐标，剩下的点做纵坐标即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;


void solve() {
    int n;
    cin >> n;
    vi a(n * 2 + 1);
    for (int i = 1; i <= n * 2; i++) cin >> a[i];
    sort( a.begin() + 1, a.end() );
    cout << a[n] - a[1] + a[n+n] - a[n+1] << "\n";
    for( int i = 1 , j = n + 1 ; i <= n ; i ++ , j ++ )
        cout << a[i] << " " << a[j] << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

C. Torn Lucky Ticket

这题，如果注意到长度不超过 5 的话，会比较好想。

首先把所有的字符串按照长度分类。

然后先枚举\(i+j\)长度，再枚举\(i\)的长度，这样可以算出\(j\)的长度。

假设\(|i+j|=4,|i|=1\)，则就是用\(a,bcd\)拼成\(abcd\)，根据题目可知\(a+b = c + d\)，则有\(a=c + d - b\)，\(O(n)\)的遍历长度为 1 和 3 的字符串，分别用桶统计\(a,c +d-b\)的值出现的次数，然后变量两个桶，把值相同的两个次数相乘再求和就是答案。

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;


void solve() {
    int n, res = 0;
    cin >> n;
    vector<vector<string>> cnt(6);
    string num;
    for (int i = 1; i <= n; i++)
        cin >> num, cnt[num.size()].push_back(num);

    for (int len = 2, mid; len <= 10; len += 2) {
        mid = len / 2;
        for (int l = 1, r; l <= 5; l++) {
            r = len - l;
            if (r < 1 or r > 5) continue;
            vector<int> a(50), b(50);
            for (auto s: cnt[l]) {
                int x = 0;
                for (int i = 0; i < min(mid, l); i++)
                    x += s[i] - '0';
                for (int i = mid; i < l; i++)
                    x -= s[i] - '0';
                if( x < 0 ) continue;
                a[x]++;
            }
            for (auto s: cnt[r]) {
                int x = 0;
                for (int i = max(r - mid, 0ll); i < r; i++)
                    x += s[i] - '0';
                for (int i = 0; i < r - mid; i++)
                    x -= s[i] - '0';
                if( x < 0 ) continue;
                b[x]++;
            }
            for (int i = 0; i < 50; i++)
                res += a[i] * b[i];
        }
    }
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

D. XOR Construction

以\(n=4\)为例子，对题目的定义做一些小修改方便理解

首先我们知道 \(b_i\)是\([0,n)\)，我们可以统计\(b_i\)二进制位每一位 1 出现的次数，对\(c_i\)做相同的统计，

如果一位上的数在\(c_i\)和\(b_i\)中出现的次数相同，则\(b_0\)这一位一定是\(0\)，否则一定是\(1\)，据此可退出\(b_0\)的值，然后就可以根据\(b_i=c_i\oplus b_0\)推出所有的\(b_i\)

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n), b(n), cntA(31), cntB(31);
    for (int i = 1; i < n; i++)
        cin >> a[i] , a[i] ^= a[i-1];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 31; j++) {
            if ((i >> j) & 1) cntA[j]++;
            if ((a[i] >> j) & 1) cntB[j]++;
        }
    }
    for (int i = 0; i < 31; i++)
        b[0] += (cntA[i] != cntB[i]) * (1 << i);
    for (int i = 1; i < n; i++)
        b[i] = b[0] ^ a[i];
    for( auto i : b )
        cout << i << " ";
    cout << "\n";
    return 0;
}

E. Infinite Card Game

对于当前的卡牌，最优解一定是在能破防的情况下，防御力尽可能大。这样的话，对于每一张卡牌的后继实际上是唯一的。

此时可以转换成有向图，对于一个联通子图，如果有环，则子图所有的点都是平局，如果无环，还可以保证只有一个汇点，我们只需要知道汇点是谁的卡片，整张子图所有的卡片状态就可以确定了。

为了方便统计，把图建成反向图，根据起点种类染色，然后用拓扑序的形式完成对整张图的染色。

#include<bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;

#define mp make_pair

void solve() {
    int n;
    cin >> n;
    vector<pii> a(n);
    for (auto &i: a) cin >> i.first;
    for (auto &i: a) cin >> i.second;

    int m;
    cin >> m;
    vector<pii> b(m);
    for (auto &i: b) cin >> i.first;
    for (auto &i: b) cin >> i.second;

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vi aSufMaxPos(n), bSufMaxPos(m);
    aSufMaxPos[n - 1] = n - 1;
    for (int i = n - 2; i >= 0; i--) {
        aSufMaxPos[i] = aSufMaxPos[i + 1];
        if (a[i].second > a[aSufMaxPos[i]].second)
            aSufMaxPos[i] = i;
    }
    bSufMaxPos[m - 1] = m - 1;
    for (int i = m - 2; i >= 0; i--) {
        bSufMaxPos[i] = bSufMaxPos[i + 1];
        if (b[i].second > b[bSufMaxPos[i]].second)
            bSufMaxPos[i] = i;
    }

    vector<vi> g(n + m);
    vi inner(n + m);
    for (int i = 0, pos; i < n; i++) {
        pos = lower_bound(b.begin(), b.end(), mp(a[i].second + 1, 0)) - b.begin();
        if (pos == m) continue;
        pos = bSufMaxPos[pos] + n;
        // 正常应该是 i -> pos , 为了方便统计答案，反向建图
        g[pos].push_back(i), inner[i]++;
    }
    for (int i = 0, pos; i < m; i++) {
        pos = lower_bound(a.begin(), a.end(), mp(b[i].second + 1, 0)) - a.begin();
        if (pos == n) continue;
        pos = aSufMaxPos[pos];
        g[pos].push_back(n + i), inner[n + i]++;
    }

    queue<int> q;
    vi f(n + m);
    for (int i = 0; i < n; i++) {
        if (b.back().first > a[i].second) continue;
        // a[i] 做结尾时,所有的 b 都无法破防,则 a[i] 必胜
        f[i] = 1, q.push(i);
    }
    for (int i = 0; i < m; i++) {
        if (a.back().first > b[i].second) continue;
        // b[i] 做结尾时,所有 a 都无法破防,则 b[i] 必败
        f[n + i] = -1, q.push(n + i);
    }
    for (int u; !q.empty();) {
        u = q.front(), q.pop();
        for (auto v: g[u]) {
            f[v] = f[u];
            if (--inner[v] == 0) q.push(v);
        }
    }
    vi res(3);
    for (int i = 0; i < n; i++) {
        if (f[i] == 1) res[0]++;
        else if (f[i] == 0) res[1]++;
        else res[2]++;
    }
    cout << res[0] << " " << res[1] << " " << res[2] << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• Hey left 1 Codeforces Round 918 (Div. 4)
• CodeForces 1312G Autocompletion
• Educational Codeforces Round 152 (Rated for Div. 2)
• codeforces 918 div4
• CF Beta Round 93-D.Fibonacci Sums-齐肯多夫分解、DP
• CodeForces 1329D Dreamoon Likes Strings
• CodeForces 1237H Balanced Reversals
• vp Codeforces Round 915 (Div. 2)
• Codeforces [Hello 2024]

Educational Codeforces Round Rated 157educational codeforces round rated educational codeforces round 157 round codeforces rated based educational codeforces round 151 construction educational codeforces round educational codeforces round 147 cf-educational educational codeforces round educational codeforces round 158 educational codeforces contest round educational codeforces monsters round