AtCoder-Keyence2020D Swap and Flip

Table of Contents

AtCoder-Keyence2020D Swap and Flip #

题目大意 #

有 $n$ 张纸牌, 第 $i$ 张纸牌正面的数字是 $a_i$ , 反面的数字是 $b_i$ . 每次操作可以交换相邻的两张牌的位置, 同时翻转这两张牌. 初始所有的纸牌都是正面朝上. 求为了让看到的数字从左到右递增, 最少需要的操作次数. 如果无法做到这一点, 返回 -1 .

Solution 1 #

我们用 $s$ 记录最终状态下纸牌的翻转情况. 如果 s & (1 << i) == 1 代表纸牌处于翻转状态, 否则代表纸牌没有翻转. 首先注意到, 每次操作都会让翻转纸牌的数量 $+2$ , 不变或者 $-2$ . 由于初始所有纸牌正面朝上, 因此最终处于翻转状态的纸牌数量为偶数. 根据翻转状态, 我们可以确定最终正面朝上的数字是哪些, 以及它们是否经过了翻转, 用 $before$ 数组来记录这些状态. 将 $before$ 排序后的结果记为 $after$ 数组. 注意到这一步的排序不一定符合交换并翻转的规则 (排序过程相当于只进行了交换, 没有记录翻转) , 因此我们验证初始数组能否通过操作变为 $after$ 数组. 假设纸牌 $i$ 最终位置为 $j$ , 那么应当有:

$\vert i - j\vert \equiv before[i].second$ (翻转状态)
$before[i].first = after[j].first$

所有 $i, j$ 都得到匹配后, 说明当前的 $s$ 是一个合法的状态. 数组中的逆序对就是需要交换的次数.

代码如下:

#include "bits/stdc++.h"

using namespace std;
typedef pair<int, int> pii;

int main() {
    int n;
    cin >> n;
    vector<pii> card(n);
    for (int i = 0; i < n; i++) {
        cin >> card[i].first;
    }
    for (int i = 0; i < n; i++) {
        cin >> card[i].second;
    }
    int ans = 1e9;
    for (int s = 0; s < (1 << n); s++) { // s 表示最终卡牌翻转的状态
        int res = 0;
        int k = __builtin_popcount(s);
        if (k & 1) { 
            continue;
        }
        vector<pii> before(n), after(n); 
        for (int i = 0; i < n; i++) {
            if (s & (1 << i)) { 
                before[i] = make_pair(card[i].second, 1); 
                after[i] = before[i];
            }
            else {
                before[i] = make_pair(card[i].first, 0); 
                after[i] = before[i];
            }
        }
        sort(after.begin(), after.end()); 
        int cnt = 0; // cnt 记录得到匹配的 i 的数量
        vector<int> pos(n, -1); // pos[j] 表示排序后的 j 位置纸牌初始在 i 位置
        for (int i = 0; i < n; i++) { // 考虑 after[j] 从 card[i] 来
            for (int j = 0; j < n; j++) { // 枚举 i, j 的可能匹配
                if (pos[j] == -1 && abs(i - j) % 2 == before[i].second && before[i].first == after[j].first) { // 这里的翻转状态应当以 before 为准, 因为我们考虑的是 card[i]
                    cnt++;
                    pos[j] = i;
                    break;
                } 
            }
        }
        if (cnt != n) {
            continue;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (pos[i] > pos[j]) { // 逆序对
                    res++;
                }
            }
        }
        ans = min(ans, res);
    }
    if (ans == 1e9) {
        cout<<-1<<endl;
    }
    else {
        cout<<ans<<endl;
    }
    return 0;
}