题解
13 分钟 读完 (大约 1991 个字) 0次访问

NOIP2015 - 斗地主增强版

【NOIP2015】【LuoguP2540】斗地主增强版
题目链接: https://www.luogu.org/problem/P2540

前言

暴力出奇迹，我是搜索小名士。

早在一年前就用贪心完成了普通版，然后现在忘了。

所以重新写一遍这道题，并且提高难度做增强版。看了仅剩的智商，我选择搜索。

分析

其实我一开始没有想着去写100分的代码，因为爆搜的复杂度太大，然后这题好像我只会爆搜。

第一步

首先，很容易想到一种最纯粹的爆搜。每层都将当前剩余牌可行的情况全部枚举判断，然后打出一种可行的牌进入下一层继续搜索。

1
搜索是盲目的，我们考虑剪枝。    ——某金牌教练

一个剪枝是搜索必备，如果当前答案大于或等于已知的最小答案，我们接下来的搜索一定不会更新答案，所以回到上一层。

然后再继续想，可以加一个启发式剪枝，计算打出所有剩余牌的最大出牌次数。

用肉眼就能推出，一副牌的最大出牌次数就是牌的数码种类数，两个王在此可以算一种。然后我们计算出当前最大出牌次数加上当前已出牌次数去更新答案，这样就会剪去接下来的一些较差的出牌方法。

第二步

上面的方法必不能通过本题，不需要尝试也能猜测。所以还要继续剪枝。

再稍微思考一下，我们每层搜索将全部出牌方法都枚举一遍过于暴力。我们发现，有些出牌方法自始至终永远不可行，并且可行的出牌方法一定越来越少。然后就想到了预处理，我们预处理出最开始的手牌的可行出牌方法。

这里我的代码极其鬼畜，可能对代码能力有些要求。我用了一些自认为省空间，用起来舒服的方法。将可行方法的信息写成结构体，就不演示，代码中在讲讲。

最关键的是，我们要计算每种方法的出牌数量，可用来后续我们继续优化。

这些代码全部可在输入后搜索前执行，我是将这些可行方法放到了vector中。在搜索时，枚举vector的所有元素。再进行一次针对性判断，也就是判断需要打的那几张牌就够了。

第三步

我们说记录了每种方法的出牌数量。那我们从大到小排序，这样大概能优化时间，我也不知道。

在这我们提个醒，如果你将王炸、对子、三张牌放入可行方法中，那你一定会TLE，因为我一开始就是这样。（实践出真知，但其实非加强版不需要，到这里已经通过了）

我们每层搜索，只枚举上一层搜索枚举没有枚举到的就行了，这是个小剪枝。如果当前方法的出牌数大于当前剩余数量，就直接枚举下一个出牌方法，这也可算上个小剪枝。然后还要再次判断当前剩余的牌下这种方法是否可行。

还有几个小的要点，我们不管是预处理，还是每层搜索都要用到一个小动态规划，用来求某个牌当左端点，可以连成（单、双、三）顺子的最大长度。鉴于这个题的难度，我相信大家都会这个小动归。

然后还有几个提示，四带二可以带两个相同数码的对子（俗称炸弹），同理，可以带两个相同数码的一张牌（俗称对子）。然后1当14，大小王当15、16比较好写代码。

经过多次提交更改调试，终于通过了本题。

代码

不开O2两秒多通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int T, n;
struct PAI {
	int num, col;
} ps[30];
// 记录牌的数码，颜色（没啥用）
#define SHUNZI 3
#define SANDAI 4
#define SIDAI 5
//顺子、三带、四带
struct CP {
    // 记录出牌方法的信息
	int typ, l, r, k1, k2, siz;
    // typ 为宏定义的值
    // siz 为出牌数量
    // l r 多种使用。l：顺子左端点，其他为最多的那张牌。r：顺子右端点，其他为少的那张牌需要的个数
    // k1 k2 三带、四带使用，表示附带哪一（两）张牌。
	CP(int typ, int siz, int l= 0, int r= 0, int k1= 0, int k2= 0) {
		this->typ= typ, this->siz= siz, this->l= l, this->r= r, this->k1= k1, this->k2= k2;
	}
	inline int operator<(const CP &c2) const {
		return siz > c2.siz;
	}
};
int pai[20], bestans, us3[20], us2[20], us1[20];
vector< CP > v;
void dfs(int nown, int nowa, int ls) {
	if(nowa >= bestans) return;
    // 小剪枝
	bestans= min(bestans, nowa + nown);
    // 更新答案，全部单打（没什么用）
	if(!nown) return;
	int res= 0, us[4][20];
	memset(us, 0, sizeof(us));
	for(int i= 2; i <= 16; i++) res+= (pai[i] != 0);
	if(pai[15] && pai[16]) --res;
    // 15、16为大小王，主程序中有，大小王可以王炸
	bestans= min(bestans, nowa + res);
    // 再次更新答案（剪枝）
	for(int i= 14, cnt= 0; i >= 2; i--) {
		if(pai[i] < 1) continue;
		us[1][i]= us[1][i + 1] + 1;
		if(pai[i] < 2) continue;
		us[2][i]= us[2][i + 1] + 1;
		if(pai[i] < 3) continue;
		us[3][i]= us[3][i + 1] + 1;
	}
    // DP出可行的顺子长度
	for(int i= ls; i < v.size(); i++) {
		if(v[i].siz > nown) continue;
		switch(v[i].typ) {
			case SHUNZI: {
				if(v[i].r - v[i].l + 1 > us[v[i].k1][v[i].l]) break;
				for(int j= v[i].l; j <= v[i].r; j++) pai[j]-= v[i].k1;
				dfs(nown - v[i].siz, nowa + 1, i + 1);
				for(int j= v[i].l; j <= v[i].r; j++) pai[j]+= v[i].k1;
                // 判断顺子
				break;
			}
			case SANDAI: {
				if(pai[v[i].l] < 3 || pai[v[i].k1] < v[i].r) break;
				pai[v[i].l]-= 3, pai[v[i].k1]-= v[i].r;
				dfs(nown - v[i].siz, nowa + 1, i + 1);
				pai[v[i].l]+= 3, pai[v[i].k1]+= v[i].r;
                // 判断三带
				break;
			}
			case SIDAI: {
				if(pai[v[i].l] < 4) break;
				if(pai[v[i].k1] < 1 || pai[v[i].k2] < 1) break;
				if(v[i].r == 2 && (pai[v[i].k1] < 2 || pai[v[i].k2] < 2)) break;
                // 都需要两张
				if(v[i].r == 2 && v[i].k1 == v[i].k2 && pai[v[i].k1] < 4) break;
                // 两对相同数码
				if(v[i].r == 1 && v[i].k1 == v[i].k2 && pai[v[i].k1] < 2) break;
                // 两张相同数码
				pai[v[i].l]-= 4;
				pai[v[i].k1]-= v[i].r;
				pai[v[i].k2]-= v[i].r;
				dfs(nown - v[i].siz, nowa + 1, i + 1);
				pai[v[i].l]+= 4;
				pai[v[i].k1]+= v[i].r;
				pai[v[i].k2]+= v[i].r;
                // 判断四带
			}
			default: break;
		}
	}
	return;
}
int main() {
	scanf("%d%d", &T, &n);
	while(T--) {
		memset(pai, 0, sizeof(pai)), bestans= 0x3f3f3f3f;
		for(int i= 1; i <= n; i++) {
			scanf("%d%d", &ps[i].num, &ps[i].col);
			if(ps[i].num == 1) ps[i].num= 14;
            // 1 当 14
			if(ps[i].num == 0) ps[i].num= ps[i].col + 14;
            // 大小王当15、16
			++pai[ps[i].num];
		}
		memset(us3, 0, sizeof(us3)), memset(us2, 0, sizeof(us2)), memset(us1, 0, sizeof(us1));
		v.clear();
		for(int i= 14; i >= 3; i--) {
			if(pai[i] < 1) continue;
			us1[i]= us1[i + 1] + 1;
			if(pai[i] < 2) continue;
			us2[i]= us2[i + 1] + 1;
			if(pai[i] < 3) continue;
			us3[i]= us3[i + 1] + 1;
		}
        // DP出顺子长度
		for(int i= 2; i <= 16; i++) {
			for(int j= 5; j <= us1[i]; j++) v.push_back(CP(SHUNZI, j, i, i + j - 1, 1));
			for(int j= 3; j <= us2[i]; j++) v.push_back(CP(SHUNZI, j * 2, i, i + j - 1, 2));
			for(int j= 2; j <= us3[i]; j++) v.push_back(CP(SHUNZI, j * 3, i, i + j - 1, 3));
            // i 当左端点的顺子
			if(pai[i] < 3) continue;
			for(int j= 2; j <= 16; j++) {
				if(i == j || !pai[j]) continue;
				v.push_back(CP(SANDAI, 4, i, 1, j));
				if(pai[j] < 2) continue;
				v.push_back(CP(SANDAI, 5, i, 2, j));
			}
            // 三带
			if(pai[i] < 4) continue;
			for(int j= 2; j <= 16; j++) {
				if(i == j || !pai[j]) continue;
				for(int k= j + 1; k <= 16; k++) {
					if(i == k || !pai[k]) continue;
					v.push_back(CP(SIDAI, 6, i, 1, j, k));
					if(pai[j] < 2 || pai[k] < 2) continue;
					v.push_back(CP(SIDAI, 8, i, 2, j, k));
				}
				if(pai[j] == 4) v.push_back(CP(SIDAI, 8, i, 2, j, j));
				if(pai[j] > 2) v.push_back(CP(SIDAI, 6, i, 1, j, j));
			}
            // 四带
		}
		sort(v.begin(), v.end());
        // 排序
		dfs(n, 0, 0);
		cout << bestans << endl;
	}
	return 0;
}
# , , ,
NOIP2001 - 统计单词个数
LuoguP1282 - 多米诺骨牌

评论

关注我

链接

分类

标签云

Cpp GCD HTML JavaScript LCA STL ST表 alpha-beta剪枝 主席树 二分查找 分块 前缀和 动态规划 块状链表 字典树 字符串 左偏树 并查集 技巧 搜索 数论 整除分块 模拟 比赛 爬虫 状压DP 码风 离散化 粤语 线段树 背包 莫比乌斯反演 莫队 解释器 记忆 记忆化搜索 语录 边压Trie 闲聊 随机化搜索 项目 颓废 题解

最新文章

归档

标签

Cpp 29
GCD 1
HTML 1
JavaScript 1
LCA 1
STL 2
ST表 1
alpha-beta剪枝 1
主席树 1
二分查找 1
分块 3
前缀和 1
动态规划 5
块状链表 1
字典树 1
字符串 1
左偏树 1
并查集 2
技巧 3
搜索 6
数论 1
整除分块 1
模拟 4
比赛 1
爬虫 3
状压DP 2
码风 1
离散化 1
粤语 1
线段树 1
背包 1
莫比乌斯反演 1
莫队 1
解释器 1
记忆 1
记忆化搜索 1
语录 1
边压Trie 1
闲聊 7
随机化搜索 2
项目 3
颓废 6
题解 22

最新文章

归档

标签

Cpp 29
GCD 1
HTML 1
JavaScript 1
LCA 1
STL 2
ST表 1
alpha-beta剪枝 1
主席树 1
二分查找 1
分块 3
前缀和 1
动态规划 5
块状链表 1
字典树 1
字符串 1
左偏树 1
并查集 2
技巧 3
搜索 6
数论 1
整除分块 1
模拟 4
比赛 1
爬虫 3
状压DP 2
码风 1
离散化 1
粤语 1
线段树 1
背包 1
莫比乌斯反演 1
莫队 1
解释器 1
记忆 1
记忆化搜索 1
语录 1
边压Trie 1
闲聊 7
随机化搜索 2
项目 3
颓废 6
题解 22
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×