比赛链接：https://codeforces.com/contest/1421

A. XORwice

题意

给出两个正整数 \(a、b\)，计算 \((a \oplus x) + (b \oplus x)\) 的最小值。

题解

\[\begin{equation} a+b = a \oplus b + ((a\ \&\ b)<<1) \end{equation}
\]

\[\begin{equation} (a \oplus x) + (b \oplus x) = ((a \oplus x) \oplus (b \oplus x)) + (((a \oplus x)\ \& \ (b \oplus x))<<1) \end{equation}
\]

\[\ \ \ \ \ \ \ \ \ \ = (a \oplus b) + (((a \oplus x)\ \&\ (b \oplus x))<<1)
\]

显然存在 \(x\)（事实上 \(x = a\ \& \ b\)）使得 \(((a \oplus x)\ \& \ (b \oplus x)) = 0\) 。

所以 \((a \oplus x) + (b \oplus x) \ge a \oplus b\) 。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {

        int a, b;

        cin >> a >> b;

        cout << (a ^ b) << "\n";

    }

    return 0;

}

B. Putting Bricks in the Wall

题意

有一个 \(01\) 方阵，起点和终点分别位于左上角和右下角，每次只能选择一条 \(0\) 路径或 \(1\) 路径到达终点。

现在要使起点终点不连通，最多可以反转两个方格，输出任一方案。

题解

如果不能连通，最简单的方案就是使得左上角和右下角相邻四个方块的状态为 \(0011\) 或 \(1100\) 。

所以枚举两种状态，如果需要更改的次数小于等于 \(2\) 输出即可。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {

        int n;

        cin >> n;

        vector<string> MP(n);

        for (auto &x : MP) cin >> x;

        string s;

        (((s += MP[0][1]) += MP[1][0]) += MP[n - 2][n - 1]) += MP[n - 1][n - 2];

        for (string t : {"0011", "1100"}) {

            vector<pair<int, int>> v;

            if (s[0] != t[0]) v.emplace_back(1, 2);

            if (s[1] != t[1]) v.emplace_back(2, 1);

            if (s[2] != t[2]) v.emplace_back(n - 1, n);

            if (s[3] != t[3]) v.emplace_back(n, n - 1);

            if (v.size() <= 2) {

                cout << v.size() << "\n";

                for (auto [x, y] : v) cout << x << ' ' << y << "\n";;

                break;

            }

        }

    }

    return 0;

}

C. Palindromifier

题意

给出一个字符串 \(s_1s_2 \dots s_{n-1}s_n\)，每次操作有两种选择：

将 \(s_2s_3 \dots s_i(i \le n-1)\) 反转后添加到字符串左侧
将 \(s_is_{i+1} \dots s_{n-1}(i \ge 2)\) 反转后添加到字符串右侧

最多操作 \(30\) 次，给出使得字符串为回文字符串的操作过程。

题解

以某一端为对称中心构造即可。

如：12345 就以 5 为中心对称构造

12345

212345

2123454321

21234543212

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    string s;

    cin >> s;

    cout << 3 << "\n";

    cout << 'L' << ' ' << 2 << "\n";

    cout << 'R' << ' ' << 2 << "\n";

    cout << 'R' << ' ' << 2 * s.size() - 1 << "\n";

    return 0;

}

D. Hexagons

题意

给出：

\(x+1\) 的花费 \(c_6\)
\(x+1,\ y+1\) 的花费 \(c_1\)
\(y+1\) 的花费 \(c_2\)
\(x-1\) 的花费 \(c_3\)
\(x-1,\ y-1\) 的花费 \(c_4\)
\(y-1\) 的花费 \(c_5\)

计算从 \((0,0)\) 走到 \((x,y)\) 的最小花费。

题解

计算一下六个方向的最小花费，然后分类讨论即可。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {

        long long x, y;

        cin >> x >> y;

        long long c1, c2, c3, c4, c5, c6;

        cin >> c1 >> c2 >> c3 >> c4 >> c5 >> c6;

        c1 = min(c1, c2 + c6);

        c2 = min(c2, c1 + c3);

        c3 = min(c3, c2 + c4);

        c4 = min(c4, c3 + c5);

        c5 = min(c5, c4 + c6);

        c6 = min(c6, c1 + c5);

        if (x >= 0 and y >= 0) {

            if (x > y)

                cout << y * c1 + (x - y) * c6 << "\n";

            else

                cout << x * c1 + (y - x) * c2 << "\n";

        } else if (x <= 0 and y <= 0) {

            if (x > y)

                cout << -x * c4 + (x - y) * c5 << "\n";

            else

                cout << -y * c4 + (y - x) * c3 << "\n";

        } else if (x >= 0 and y <= 0) {

            cout << x * c6 - y * c5 << "\n";

        } else if (x <= 0 and y >= 0) {

            cout << -x * c3 + y * c2 << "\n";

        }

    }

    return 0;

}

巴特西

Codeforces Round #676 (Div. 2)【ABCD】

A. XORwice

题意

题解

代码

B. Putting Bricks in the Wall

题意

题解

代码

C. Palindromifier

题意

题解

代码

D. Hexagons

题意

题解

代码

最新文章

热门文章