题解：P4907 A换B problem

· · 题解

题解：

P4907

题目传送门

题目要求通过交换牌来使得每种花色的牌按顺序排列。交换规则是只能交换点数相同的牌。我们需要判断是否可以通过交换使得每种花色的牌按顺序排列，并输出最少的交换次数。

主要思路如下：

  1. 使用深度优先搜索 DFS 来尝试所有可能的交换方式。
  2. 在每次交换后，检查当前状态是否满足每种花色的牌按顺序排列。
  3. 使用一个二维数组 f 来记录每种花色的牌的状态。
  4. 通过递归的方式尝试每种可能的交换，并记录最少的交换次数。

  5. 如果在规定时间内找到解，则输出最少的交换次数，否则输出最少需要的牌数。

    AC CODE：

    
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 60, M = 20;

// 读取输入的函数 inline ll read() { ll x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; }

// 输出结果的函数 inline void write(ll x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x / 10); putchar(x % 10 + '0'); }

// 牌的结构体 struct Card { ll suit, rank; } cards[N];

ll n, x, y, K, ans = INT_MAX, min_missing = INT_MAX; char rank_str[2]; bool f[5][M];

// 检查当前状态是否满足每种花色的牌按顺序排列 bool check() { ll missing = 0; bool valid = true; for (int i = 1; i <= 4; i++) { ll min_rank = 15, max_rank = 0; for (ll j = 1; j <= 13; j++) { if (f[i][j]) { min_rank = j; break; } } for (ll j = 13; j >= 1; j--) { if (f[i][j]) { max_rank = j; break; } } for (int j = min_rank; j <= max_rank; j++) { if (!f[i][j]) { valid = false; missing++; } } } min_missing = min(min_missing, missing); return valid; }

// 深度优先搜索尝试所有可能的交换方式 void dfs(ll pos, ll sum) { if (sum >= ans) return; if (check()) { ans = min(ans, sum); return; } if (pos > n) return; if ((clock() - K) 1000 >= 200 CLOCKS_PER_SEC) { if (ans <= 52) { puts("Yes"); write(ans); } else { puts("No"); write(min_missing); } exit(0); } for (int i = 1; i <= 4; i++) { if (f[i][cards[pos].rank] && i != cards[pos].suit) continue; f[cards[pos].suit][cards[pos].rank] = 0; f[i][cards[pos].rank] = 1; if (i != cards[pos].suit) dfs(pos + 1, sum + 1); else dfs(pos + 1, sum); f[i][cards[pos].rank] = 0; f[cards[pos].suit][cards[pos].rank] = 1; } }

int main() { n = read(); for (int i = 1; i <= n; i++) { x = read(); scanf("%s", rank_str); if (rank_str[0] == 'A') y = 1; else if (rank_str[0] == 'J') y = 11; else if (rank_str[0] == 'Q') y = 12; else if (rank_str[0] == 'K') y = 13; else if (rank_str[0] == '1' && rank_str[1] == '0') y = 10; else y = rank_str[0] - '0'; cards[i].suit = x; cards[i].rank = y; } for (int i = 1; i <= n; i++) f[cards[i].suit][cards[i].rank] = 1; K = clock(); dfs(1, 0); if (ans <= 52) { puts("Yes"); write(ans); } else { puts("No"); write(min_missing); } return 0; }