【作业向】程序设计思维与实践 Week6 限时大模拟

发表于 | 分类于 ，
字数统计: 1.7k | 阅读时长 ≈ 7

【作业向】程序设计思维与实践 Week6限时大模拟

♔掌握魔法の东东 II

♔Problem

从瑞神家打牌回来后，东东痛定思痛，决定苦练牌技，终成赌神！
东东有 A × B 张扑克牌。每张扑克牌有一个大小(整数，记为a，范围区间是 0 到 A - 1）和一个花色（整数，记为b，范围区间是 0 到 B - 1。
扑克牌是互异的，也就是独一无二的，也就是说没有两张牌大小和花色都相同。
“一手牌”的意思是你手里有5张不同的牌，这 5 张牌没有谁在前谁在后的顺序之分，它们可以形成一个牌型。 我们定义了 9 种牌型，如下是 9 种牌型的规则，我们用“低序号优先”来匹配牌型，即这“一手牌”从上到下满足的第一个牌型规则就是它的“牌型编号”（一个整数，属于1到9）：

  1. 同花顺: 同时满足规则 2 和规则 3.
  2. 顺子 : 5张牌的大小形如 x, x + 1, x + 2, x + 3, x + 4
  3. 同花 : 5张牌都是相同花色的.
  4. 炸弹 : 5张牌其中有4张牌的大小相等.
  5. 三带二 : 5张牌其中有3张牌的大小相等，且另外2张牌的大小也相等.
  6. 两对: 5张牌其中有2张牌的大小相等，且另外3张牌中2张牌的大小相等.
  7. 三条: 5张牌其中有3张牌的大小相等.
  8. 一对: 5张牌其中有2张牌的大小相等.
  9. 要不起: 这手牌不满足上述的牌型中任意一个.

现在, 东东从A × B 张扑克牌中拿走了 2 张牌！分别是 (a1, b1) 和 (a2, b2). （其中a表示大小，b表示花色）
现在要从剩下的扑克牌中再随机拿出 3 张！组成一手牌！！
其实东东除了会打代码，他业余还是一个魔法师，现在他要预言他的未来的可能性，即他将拿到的“一手牌”的可能性，我们用一个“牌型编号（一个整数，属于1到9）”来表示这手牌的牌型，那么他的未来有 9 种可能，但每种可能的方案数不一样。
现在，东东的阿戈摩托之眼没了，你需要帮他算一算 9 种牌型中，每种牌型的方案数。

♔Input

第 1 行包含了整数 A 和 B (5 ≤ A ≤ 25, 1 ≤ B ≤ 4).

第 2 行包含了整数 a1, b1, a2, b2 (0 ≤ a1, a2 ≤ A - 1, 0 ≤ b1, b2 ≤ B - 1, (a1, b1) ≠ (a2, b2)).

♔Output

输出一行，这行有 9 个整数，每个整数代表了 9 种牌型的方案数（按牌型编号从小到大的顺序）

♔Example

♔Input

1
2
25 4
0 0 24 3

♔Output

1
0 0 0 2 18 1656 644 36432 113344

♔解题思路

看到这一题第一反应是NOIP2015的斗地主 😭，但还是有不同之处的斗地主是把牌发给你让你出，这个题是整副牌都可以用，然后凑五张就可以。

不过基本思路差不多，这一题可以直接枚举各种剩下的三张牌的所有可能性，复杂度也不高，100的三次方，完全可以跑过的。这一题的点在于如何判断，我们发现如果被选出的五张牌是排好序的，那么判断会简单的多，但是在dfs还需要恢复现场，那怎么办？再开个数组复制一下呗，反正就五张牌，复杂度又不高。这个问题解决之后还有一个问题，就是判断的顺序，一定要严格按照优先级进行判断并且思路一定要清晰，不要漏了情况。（但总有一种在写太吾绘卷的感觉，一万个if else ​

（ps：听说还有用排列组合公式算的同学，可怕

♔代码

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
struct data
{
	int p,h;
}p[105];
int card[25][4],sum[10];
data xu[6],xuw[6];
int a,b,pcnt;

int wly(data x,data y)
{
	if(x.p<y.p) return 1;
	else if(x.p==y.p && x.h<y.h) return 1;
	return 0;
}

void dfs(int x,int t)
{
	if(x==6)
	{
		for(int i=1;i<=5;i++) xuw[i]=xu[i];
		sort(xuw+1,xuw+6,wly);
		if(xuw[1].h==xuw[2].h && xuw[2].h==xuw[3].h && xuw[3].h==xuw[4].h && xuw[4].h==xuw[5].h)
		{
			if(xuw[2].p==xuw[1].p+1 && xuw[3].p==xuw[2].p+1 && xuw[4].p==xuw[3].p+1 && xuw[5].p==xuw[4].p+1)
				sum[1]++;
			else sum[3]++;
		}
		else if(xuw[2].p==xuw[1].p+1 && xuw[3].p==xuw[2].p+1 && xuw[4].p==xuw[3].p+1 && xuw[5].p==xuw[4].p+1)
			sum[2]++;
		else if(xuw[1].p==xuw[2].p && xuw[2].p==xuw[3].p && xuw[3].p==xuw[4].p)
			sum[4]++;
		else if(xuw[2].p==xuw[3].p && xuw[3].p==xuw[4].p && xuw[4].p==xuw[5].p)
			sum[4]++;
		else if(xuw[1].p==xuw[2].p && xuw[2].p==xuw[3].p)//123 45
		{
			if(xuw[4].p==xuw[5].p) sum[5]++;
			else sum[7]++;
		}
		else if(xuw[2].p==xuw[3].p && xuw[3].p==xuw[4].p)//1 234 5
		{
			if(xuw[1].p==xuw[5].p) sum[5]++;
			else sum[7]++;
		}
		else if(xuw[3].p==xuw[4].p && xuw[4].p==xuw[5].p)//12 345
		{
			if(xuw[1].p==xuw[2].p) sum[5]++;
			else sum[7]++;
		}
		else if(xuw[1].p==xuw[2].p)//12 3 4 5
		{
			if(xuw[3].p==xuw[4].p || xuw[4].p==xuw[5].p) sum[6]++;
			else sum[8]++;
		}
		else if(xuw[2].p==xuw[3].p)//1 23 4 5
		{
			if(xuw[1].p==xuw[4].p || xuw[4].p==xuw[5].p) sum[6]++;
			else sum[8]++;
		}
		else if(xuw[3].p==xuw[4].p)//1 2 34 5
		{
			if(xuw[1].p==xuw[2].p || xuw[2].p==xuw[5].p) sum[6]++;
			else sum[8]++;
		}
		else if(xuw[4].p==xuw[5].p)//1 2 3 45
		{
			if(xuw[1].p==xuw[2].p || xuw[2].p==xuw[3].p) sum[6]++;
			else sum[8]++;
		}
		else sum[9]++;
		return;
	}
	for(int i=t;i<=pcnt;i++)
	{
		if(!card[p[i].p][p[i].h])
		{
			card[p[i].p][p[i].h]=1;
			xu[x]=p[i];
			dfs(x+1,i+1);
			card[p[i].p][p[i].h]=0;
		}
	}
}

int main()
{
	int i,j;
	scanf("%d%d",&a,&b);
	scanf("%d%d%d%d",&xu[1].p,&xu[1].h,&xu[2].p,&xu[2].h);
	card[xu[1].p][xu[1].h]=1;
	card[xu[2].p][xu[2].h]=1;
	if(xu[1].p>xu[2].p) swap(xu[1],xu[2]);
	else if(xu[1].p==xu[2].p && xu[1].h>xu[2].h) swap(xu[1],xu[2]);
	for(i=0;i<a;i++)
	{
		for(j=0;j<b;j++)
			if(!card[i][j])
			{
				p[++pcnt].p=i;
				p[pcnt].h=j;
			}
	}
	dfs(3,1);
	for(i=1;i<=9;i++)
		printf("%d ",sum[i]);
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！