题解：B4307 [蓝桥杯青少年组国赛 2024] 第二题

题目便捷入口

看题目，题目说我们有两排石头，每个石头不是黄色就是绿色；

让我们第一排某个位置和第二排的某个位置交换，或者就是第二排的某个位置和第一排交换，也就是说不可能是第 $x$ 行的某个位置和第 $x$ 行的某个位置交换！

从此，我们可以将每一列的颜色组合分为以下四种情况：

$(1, 1)$ ：两排都是 $1$ ，不需要交换。
$(0, 0)$ ：两排都是 $0$ ，不需要交换。
$(1, 0)$ ：第一排是 $1$ ，第二排是 $0$ ，需要交换。
$(0, 1)$ ：第一排是 $0$ ，第二排是 $1$ ，需要交换。

然后……我们假设这四个情况的列数分别为：

$x$ ： $(1, 1)$ 的列数。
$w$ ： $(0, 0)$ 的列数。
$y$ ： $(1, 0)$ 的列数。
$z$ ： $(0, 1)$ 的列数。

从此，我想出了一个不可能实现结果的结论： 如果 $y + z$ 是奇数，直接返回 $-1$ 。

OK，那么第一时间搞定了可不可能的问题，接下来，我们就要开始看看要多少次（最少）完成任务了。

第一步：直接配对交换：

对于 $(1, 0)$ 和 $(0, 1)$ 的列，可以直接交换这两列的第一排和第二排的石头，这样一次交换可以解决两列的问题。
得出来了，我们最少需要 $y \div 2 + z \div 2$ 次交换。

第二步： 剩余未配对的列：

肯定的的是 $y$ 与 $z$ 都是奇数，我们就会剩下一个 $(1, 0)$ 和一个 $(0, 1)$ 的列。
那么为了AC，我们有需要额外两次交换来解决这两列的问题（不得不说很麻烦）：
- 第一次交换：将 $(1, 0)$ 的第一排 $1$ 与某个 $(1, 1)$ 的第二排 $1$ 交换，得到 $(1, 1)$ 和 $(1, 0)$ 。
- 第二次交换：将新的 $(1, 0)$ 的第一排 $1$ 与 $(0, 1)$ 的第二排 $1$ 交换，得到 $(1, 1)$ 和 $(0, 0)$ 。
因此，剩余的两列需要 $2$ 次交换。

最终，我们辛辛苦苦干出来的公式：

\left\lfloor \frac{y}{2} \right\rfloor + \left\lfloor \frac{z}{2} \right\rfloor + (y \bmod 2) \times 2

上代码了：

CPP

#include <bits/stdc++.h>  // 好习惯*1
using namespace std;

int main() {
    int T;  // 测试数据组数
    cin >> T;
    while (T--) {  
        int n;  
        cin >> n;
        int a[10005], b[10005];  //石头石头来了
        
        // 第一排石头
        for (int i = 0; i < n; ++i)
             cin >> a[i];
        // 第二排石头
        for (int i = 0; i < n; ++i)
             cin >> b[i];
        int x = 0;  // 两排都是1的列数
        int y = 0;  // 第一排1第二排0的列数
        int z = 0;  // 第一排0第二排1的列数
        int w = 0;  // 两排都是0的列数
        for (int i = 0; i < n; ++i) {
            if (a[i] == 1 && b[i] == 1) x++;
            else if (a[i] == 1 && b[i] == 0) y++;
            else if (a[i] == 0 && b[i] == 1) z++;
            else w++;
        }
        // 如果需要交换的列数(y+z)是奇数，则无解
        if ((y + z) % 2 != 0) {
            cout << -1 << '\n';
            continue;  // 跳过本次循环，处理下一组数据
        }
        // 计算最少交换次数：
        // 1. 每对(1,0)和(0,1)可以直接交换解决，需要y/2 + z/2次
        // 2. 如果y和z是奇数，最后会剩下一对(1,0)和(0,1)，需要额外2次交换
        int ans = y / 2 + z / 2 + (y % 2) * 2;
        cout << ans << '\n';  // 输出结果
    }
    return 0;  //好习惯*2
    为了您的安全，请不要抄袭代码！！！这非常重要！
}

真心希望大家可以学会这道题，掌握知识点和如何推导公式qwq。

题解：B4307 [蓝桥杯青少年组国赛 2024] 第二题

文章操作

相关推荐

评论

题解：B4307 [蓝桥杯青少年组国赛 2024] 第二题