斗地主
题目大意
牛牛最近迷上了一种叫斗地主的扑克游戏. 斗地主是一种使用黑桃、红心、梅花、方片的 A 到 K 加上大小王的共 54 张牌来进行的扑克牌游戏. 在斗地主中, 牌的大小关系根据牌的数码表示如下: 3<4<5<6<7<8<9<10
样例输入
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1样例输出
3样例解释
共有 1 组手牌, 包含 8 张牌: 方片 7, 方片 8, 黑桃 9, 方片 10, 黑桃 J, 黑桃 5, 方片 A 以及黑桃 A. 可以通过打单顺子 (方片 7, 方片 8, 黑桃 9, 方片 10, 黑桃 J), 单张牌 (黑桃 5) 以及对子牌 (黑桃 A 以及方片 A) 在 3 次内打光.
规模
\(n <= 23\).
手牌不一定是随机生成的
在此题中认为两个王不能组成对子牌
时间限制: 2s 空间限制: 1GB
Explanation
这道题用 大 DFS, 小 DP, 交错暴力的方式做.
先大范围将所有单、双、三顺子全部取掉, 这个操作是要暴力搜寻的, 当然时间常数很大, 但是是 \(O(1)\) 的. 然后我们再大规模贪心 (贪心需要大量特判, 如果不仔细写的话, NOIP 官方的数据还是能过的, 但是一遇到 UOJ 的强力数据就会统统 WA 掉) 或者 DP 保证正确.
我不是拿 DP 写的, 所以就把一些奇怪的特判贴上来.
这个是在 UOJ 上能过 97 分的版本.
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long lli;
const int infinit = 0x007f7f7f;
// 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A, 2, Joker.
class CardSet
{
public:
int data_1, data_2, data_3;
void clear(void) {
data_1 = data_2 = data_3 = 0; }
int get(int pos) {
return (((data_1 >> pos) & 1) << 2)
+ (((data_2 >> pos) & 1) << 1)
+ (((data_3 >> pos) & 1) << 0); }
void print(void) {
for (int i = 1; i <= 14; i++)
printf("%d ", this->get(i));
printf("\n"); }
void set(int pos, int dat) {
if (((data_1 >> pos) & 1) != ((dat >> 2) & 1))
data_1 ^= (1 << pos);
if (((data_2 >> pos) & 1) != ((dat >> 1) & 1))
data_2 ^= (1 << pos);
if (((data_3 >> pos) & 1) != ((dat >> 0) & 1))
data_3 ^= (1 << pos); }
void modify(int pos, int dat) {
set(pos, get(pos) + dat); }
CardSet clone(void) { CardSet b = *this; return b; }
};
int T, n;
int dp(CardSet in, int depth)
{
int cnt[5] = {0, 0, 0, 0, 0};
int res = 0;
for (int i = 1; i <= 14; i++)
cnt[in.get(i)]++;
// Trying all other combinations
while (cnt[4] >= 1 && cnt[2] >= 2) // Four with two pairs
cnt[4] -= 1, cnt[2] -= 2, res++;
while (cnt[4] >= 1 && cnt[1] >= 2) // Four with two singles
cnt[4] -= 1, cnt[1] -= 2, res++;
while (cnt[4] >= 1 && cnt[2] >= 1) // Four with two duplicate singles
cnt[4] -= 1, cnt[2] -= 1, res++;
while (cnt[3] >= 1 && cnt[1] >= 1) // Three with one single
cnt[3] -= 1, cnt[1] -= 1, res++;
while (cnt[3] >= 1 && cnt[2] >= 1) // Three with one pair
cnt[3] -= 1, cnt[2] -= 1, res++;
res += cnt[4] + cnt[3] + cnt[2] + cnt[1]; // Add single pairs
res += depth; // Iterative depth
return res;
}
int dfs(CardSet in, int depth)
{
int dfs_part_min = infinit;
#define minimize(__x) dfs_part_min = min(dfs_part_min, (__x))
// Dynamic programming
minimize(dp(in, depth));
// Two *3 in a row
for (int i = 1; i <= 14; i++) {
int j = i - 1;
while (j < 12 && in.get(j + 1) >= 3) j++;
if (j - i < 2 - 1) continue;
// Applying to clone
CardSet out = in.clone();
for (int k = i; k <= j; k++)
out.modify(k, -3);
minimize(dfs(out, depth + 1));
}
// Three *2 in a row
for (int i = 1; i <= 14; i++) {
int j = i - 1;
while (j < 12 && in.get(j + 1) >= 2) j++;
if (j - i < 3 - 1) continue;
// Applying to clone
CardSet out = in.clone();
for (int k = i; k <= j; k++)
out.modify(k, -2);
minimize(dfs(out, depth + 1));
}
// Five *1 in a row
for (int i = 1; i <= 14; i++) {
int j = i - 1;
while (j < 12 && in.get(j + 1) >= 1) j++;
if (j - i < 5 - 1) continue;
// Applying to clone
CardSet out = in.clone();
for (int k = i; k <= j; k++)
out.modify(k, -1);
minimize(dfs(out, depth + 1));
}
return dfs_part_min;
}
int main(int argc, char** argv)
{
CardSet cs;
scanf("%d%d", &T, &n);
for (int idx = 1; idx <= T; idx++) {
cs.clear();
for (int i = 1, a, b; i <= n; i++) {
scanf("%d%d", &a, &b);
if (a == 0) cs.modify(14, 1);
else if (a <= 2) cs.modify(11 + a, 1);
else cs.modify(a - 2, 1);
}
// Read card set, ready to work.
// Brute force all consequential combinations...
int res = dfs(cs, 0);
printf("%d\n", res);
}
return 0;
}但是为什么会错呢 (雾)~
原因是这样的几组 hack 数据:
1 17
7 3
4 2
5 2
10 1
10 3
3 3
13 4
4 4
7 2
0 2
4 1
13 3
7 4
4 3
10 4
5 4
0 1为什么没有过呢? 因为四带二是不能带上大小王的.
大小王也不能被三带二的 (换句话说大小王不是一种牌, 所以我们把它剔除出去)
1 8
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4为什么也没有过呢? 因为四带二可以一对四张牌把另一个四张牌拆成两对一起带走.
1 22
9 1
6 1
12 1
12 4
3 3
6 3
12 2
7 3
3 4
7 4
13 3
12 3
7 1
3 2
10 2
13 4
11 4
10 3
6 2
6 4
4 3
13 2为什么还是没有过呢? 因为四带二可以拆掉一张三张牌的. 但是这样拆不一定具有贪心最优性, 所以我们就略微修改一下贪心的函数, 让它能够接受这样拆分 (也就是代码中的work_4_3, 这个 变量代表了拆掉多少组 (4 张牌, 3 张牌), 然后 dfs+贪心搞定.
这样这道题就是过了 hack 的 AC 代码了 (是不是很吼啊)~
Example Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef long long lli;
const int infinit = 0x007f7f7f;
// 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A, 2, Joker.
class CardSet
{
public:
int data_1, data_2, data_3;
void clear(void) {
data_1 = data_2 = data_3 = 0; }
int get(int pos) {
return (((data_1 >> pos) & 1) << 2)
+ (((data_2 >> pos) & 1) << 1)
+ (((data_3 >> pos) & 1) << 0); }
void print(void) {
for (int i = 1; i <= 14; i++)
printf("%d ", this->get(i));
printf("\n"); }
void set(int pos, int dat) {
if (((data_1 >> pos) & 1) != ((dat >> 2) & 1))
data_1 ^= (1 << pos);
if (((data_2 >> pos) & 1) != ((dat >> 1) & 1))
data_2 ^= (1 << pos);
if (((data_3 >> pos) & 1) != ((dat >> 0) & 1))
data_3 ^= (1 << pos); }
void modify(int pos, int dat) {
set(pos, get(pos) + dat); }
CardSet clone(void) { CardSet b = *this; return b; }
};
int T, n;
int dp(CardSet in, int depth, int work_4_3)
{
#define myp printf("cnt. %d %d %d %d\n", cnt[1], cnt[2], cnt[3], cnt[4])
int cnt[5] = {0, 0, 0, 0, 0};
int res = 0, final_res = infinit;
for (int i = 1; i <= 13; i++)
cnt[in.get(i)]++;
bool has_joker_pair = in.get(14) >= 2;
cnt[1] += in.get(14); // Jokers must not be counted as cards of the same type
// Examining branch conditions
if (cnt[4] >= 1 && cnt[3] >= 1 && work_4_3 <= 0)
for (int i = 1; i <= min(cnt[3], cnt[4]); i++)
final_res = min(final_res, dp(in, depth, i));
// Brute force work_4_3.
for (int i = 1; i <= work_4_3; i++) {
cnt[4] -= 1, cnt[3] -= 1, cnt[1] += 1, res++;
if (cnt[2] >= 1) cnt[2] -= 1; }
// Trying all other combinations
while (cnt[4] >= 1 && cnt[2] >= 2) // Four with two pairs
cnt[4] -= 1, cnt[2] -= 2, res++;
while (cnt[4] >= 1 && cnt[1] >= 2) // Four with two singles
cnt[4] -= 1, cnt[1] -= 2, res++;
while (cnt[4] >= 1 && cnt[2] >= 1) // Four with two duplicate singles
cnt[4] -= 1, cnt[2] -= 1, res++;
while (cnt[4] >= 2) // Four with two pairs of the same type
cnt[4] -= 2, res++;
while (cnt[3] >= 1 && cnt[1] >= 1) // Three with one single
cnt[3] -= 1, cnt[1] -= 1, res++;
while (cnt[3] >= 1 && cnt[2] >= 1) // Three with one pair
cnt[3] -= 1, cnt[2] -= 1, res++;
if (has_joker_pair && cnt[1] >= 2)
cnt[1] -= 2, res++;
res += cnt[4] + cnt[3] + cnt[2] + cnt[1]; // Add single pairs
res += depth; // Iterative depth
final_res = min(final_res, res);
// in.print();
// printf("result %d is %d\n", work_4_3, final_res);
return final_res;
}
int dfs(CardSet in, int depth)
{
int dfs_part_min = infinit;
#define minimize(__x) dfs_part_min = min(dfs_part_min, (__x))
// Dynamic programming
minimize(dp(in, depth, 0));
// Two *3 in a row
for (int i = 1; i <= 14; i++) {
int j = i - 1;
while (j < 12 && in.get(j + 1) >= 3) j++;
if (j - i < 2 - 1) continue;
// Applying to clones
CardSet out = in.clone();
for (int k = i; k < i + 1; k++)
out.modify(k, -3);
for (int k = i + 1; k <= j; k++) {
out.modify(k, -3);
minimize(dfs(out, depth + 1));
}
}
// Three *2 in a row
for (int i = 1; i <= 14; i++) {
int j = i - 1;
while (j < 12 && in.get(j + 1) >= 2) j++;
if (j - i < 3 - 1) continue;
// Applying to clone
CardSet out = in.clone();
for (int k = i; k < i + 2; k++)
out.modify(k, -2);
for (int k = i + 2; k <= j; k++) {
out.modify(k, -2);
minimize(dfs(out, depth + 1));
}
}
// Five *1 in a row
for (int i = 1; i <= 14; i++) {
int j = i - 1;
while (j < 12 && in.get(j + 1) >= 1) j++;
if (j - i < 5 - 1) continue;
// Applying to clone
CardSet out = in.clone();
for (int k = i; k < i + 4; k++)
out.modify(k, -1);
for (int k = i + 4; k <= j; k++) {
out.modify(k, -1);
minimize(dfs(out, depth + 1));
}
}
return dfs_part_min;
}
int main(int argc, char** argv)
{
CardSet cs;
scanf("%d%d", &T, &n);
for (int idx = 1; idx <= T; idx++) {
cs.clear();
for (int i = 1, a, b; i <= n; i++) {
scanf("%d%d", &a, &b);
if (a == 0) cs.modify(14, 1);
else if (a <= 2) cs.modify(11 + a, 1);
else cs.modify(a - 2, 1);
}
// Read card set, ready to work.
// Brute force all consequential combinations...
int res = dfs(cs, 0);
printf("%d\n", res);
}
return 0;
}