[JSOI 2007] 麻将

题目大意

考虑一种特殊的麻将:没有字牌,只有一种花色,每种牌没有数量限制,数字的范围是 [1,  n][1, \; n]。现有 3m+13 m + 1 张牌,求所有可能听的牌(加上后使牌有一对将和 mm 个顺子或刻子)。

9n4009 \leqslant n \leqslant 400

4m1,0004 \leqslant m \leqslant 1,000

题目链接

【JSOI 2007】麻将 - Luogu 4050

题解

枚举每一种牌进行判断,再枚举哪种牌做将,最后扫一遍每种牌,如果出现有一种牌消不到 00 个,则失败,否则成功。

暴力枚举题也要做不出来了吗。。。

代码

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
#include <cstdio>
#include <vector>
#include <algorithm>
const int MAXN = 405;
const int MAXM = 1005;
int main() {
int n, m;
scanf("%d %d", &n, &m);
static int cnt[MAXN];
for (int i = 0; i < 3 * m + 1; i++) {
int x;
scanf("%d", &x);
cnt[x]++;
}
std::vector<int> ans;
for (int i = 1; i <= n; i++) {
cnt[i]++;
bool success = true;
for (int j = 1; j <= n; j++) {
if (cnt[j] >= 2) {
static int temp[MAXN];
std::copy(cnt + 1, cnt + n + 1, temp + 1);
temp[j] -= 2;
success = true;
for (int k = 1; k <= n; k++) {
if (temp[k] == 0) continue;
temp[k] %= 3;
int t = std::min(std::min(temp[k], temp[k + 1]), temp[k + 2]);
if (t < temp[k]) {
success = false;
break;
}
temp[k] -= t, temp[k + 1] -= t, temp[k + 2] -= t;
}
if (success) break;
}
}
cnt[i]--;
if (success) ans.push_back(i);
}
if (ans.size() == 0) puts("NO");
else for (int i = 0; i < ans.size(); i++)
printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
return 0;
}