Educational Codeforces Round 157 (Rated for Div. 2)

Shiroha白羽的博客

Shiroha · 2024-01-01 · via Shiroha白羽的博客

A. Treasure Chest

大致题意

有一条路上，有一个宝箱(x)和一个钥匙(y)，开始人在 0 号位置，可以携带钥匙、宝箱进行移动，但是最多只能同时携带宝箱走 $k$ 步

问最多需要走几步才能同时拥有宝箱和钥匙

思路

说白了就是钥匙可以在 $[y, \inf]$ 范围内移动，而宝箱只能在 $[x-k, x+k]$ 范围内，所以需要至少走到 $max(x, y)$ 后，再回到 $[x-k, x+k]$ 区间内

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int x, y , k;
        cin >> x >> y >> k;
        cout << max(x, y) + max(0, y - x - k) << endl;
    }
}

B. Points and Minimum Distance

大致题意

有一堆的数字，需要两两组合，变成平面上的点，然后在再逐个通过棋盘距离来连接所有点，要尽可能让线短

思路

就是要避免反复走，即一会往左一会往右，另外要尽可能短。

我的构造方法是这样的，将数组按照大小拆成两半，小一点的一半和大一点的一半，然后 x 只取小一点的，然后从最小开始取，y 则从大一点的开始，然后从最小开始取即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n * 2);
        for (auto& i: data) cin >> i;
        sort(data.begin(), data.end());
        vector<pair<int, int>> res(n);
        for (int i = 0; i < n; ++i) res[i] = {data[i], data[n + i]};
        int ans = 0;
        for (int i = 1; i < n; ++i) ans += abs(res[i].first - res[i - 1].first) + abs(res[i].second - res[i - 1].second);
        cout << ans << endl;
        for (const auto& [fst, snd]: res) cout << fst << ' ' << snd << endl;
    }
}

C. Torn Lucky Ticket

大致题意

有一个字符串组，每个字母都是数字，每个字符串的最大长度不超过 $5$ 个。

任选两个字符串连在一块，使得整个字符串的长度恰好为偶数，且拆成两半之后，再把两边的每一个数字加起来，使得两边相等

问有多少种可能

思路

看数组量级，说明需要查找的方式来找匹配的值

两个字符串相同长度的时候，非常的简单统计一下即可

如果不等长，那么就有几种组合 $1+3,1+5,2+4,3+5$

最简单的方式就是枚举所有的拆法，去枚举那些长度较长的部分，并将结果写入到统计表里，然后查找即可

AC code

#define int long longvoid solve() {
    int n;
    cin >> n;
    vector<string> data(n);
    for (auto& i: data) cin >> i;
    map<pair<int, int>, int> cnt;
    for (auto& i: data) {
        int sum = 0;
        for (const char l: i) sum += l - '0';
        cnt[{sum, i.size()}]++;
        if (i.size() == 3 || i.size() == 5 || i.size() == 4) {
            cnt[{sum - (i.front() - '0') * 2, i.size() - 2}]++;
            cnt[{sum - (i.back() - '0') * 2, i.size() - 2}]++;
        }
        if (i.size() == 5) {
            cnt[{sum - (i[4] - '0' + i[3] - '0') * 2, 1}]++;
            cnt[{sum - (i[0] - '0' + i[1] - '0') * 2, 1}]++;
        }
    }
    int ans = 0;
    for (auto& i: data) {
        int sum = 0;
        for (const char l: i) sum += l - '0';
        if (auto iter = cnt.find({sum, i.length()}); iter != cnt.end()) ans += iter->second;
    }
    cout << ans << endl;
}

D. XOR Construction

大致题意

有一个数组 $a$，长度 $n-1$，需要构造出一个数组长度为 $n$ 的数组，满足数组是 $[0,n-1]$ 的排列，且 $b_i \oplus b_{i+1} = a_i$

思路

显然可以得到，$b_i = b_1 \oplus a_1 \oplus a_2 \oplus a_3 \dots \oplus a_{i-1}$

那么只需要枚举 $b_1$ 的值，然后去判断是否能够保证所有的 $b_i \le n$ 即可

如果找到了，那么就是答案，并不需要判断是否满足是 $[0,n-1]$ 的排列。

原因也很简单

题目说明必定有答案，那么必然有一个解
假如当前值能够满足所有结果值都在 $[0, n-1]$ 后并不是正确的解（即存在重复的值了）
- 那么必然还存在另外一个解不存在重复的解，假定错误的解为 $b_1$，正确的为 $b_1’$
- 那么必定存在一个 $i,j(i \le j)$，满足 $b_i = b_j$
- 那么可以得到 $b_j = b_i \oplus a_{i} \oplus a_{i+1} \oplus a_{i+2} \dots \oplus a_{j-1} = b_i$
- 即 $a_{i} \oplus a_{i+1} \oplus a_{i+2} \dots \oplus a_{j-1}$
- 那么必然就可以得到 $b_i’ \oplus a_{i} \oplus a_{i+1} \oplus a_{i+2} \dots \oplus a_{j-1} = b_j’$
- 即两个解都不是正确的解

AC code

void solve() {
    int n;
    cin >> n;
    vector<int> data(n - 1);
    for (auto& i: data) cin >> i;    struct node {
        int cnt, n[2];
    };
    vector<node> tree(n * 32);
    int len = 0;
    auto build = [&] {
        tree[len] = {0, -1, -1};
        return len++;
    };
    const auto root = build();
    auto add = [&](const int x) {
        int cur = root;
        for (int i = 30; i >= 0; --i) {
            const auto v = x & (1 << i) ? 1 : 0;
            if (tree[cur].n[v] == -1) tree[cur].n[v] = build();
            cur = tree[cur].n[v];
        }
    };
    auto find = [&](const int x) {
        int cur = root, ans = 0;
        for (int i = 30; i >= 0; --i) {
            const auto v = x & 1 << i ? 1 : 0;
            if (const auto u = v ^ 1; tree[cur].n[u] != -1) {
                cur = tree[cur].n[u];
                ans += 1 << i;
            } else cur = tree[cur].n[v];
        }
        return ans;
    };
    int tmp = 0;
    for (const auto& i: data) {
        tmp ^= i;
        add(tmp);
    }
    for (int i = 0; i < n; ++i) {
        tmp = find(i);
        if (tmp >= n) continue;
        tmp = i;
        cout << tmp;
        for (const auto& j: data) {
            tmp ^= j;
            cout << ' ' << tmp;
        }
        cout << endl;
        return;
    }
}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Shiroha白羽的博客

A. Treasure Chest

大致题意

思路

AC code

B. Points and Minimum Distance

大致题意

思路

AC code

C. Torn Lucky Ticket

大致题意

思路

AC code

D. XOR Construction

大致题意

思路

AC code