Shelter
0%

2022杭电杯超级联赛05

发表于 更新于
详细题解 我与队友一起在比赛 2022杭电杯超级联赛05 完成的题目

1010-Bragging Dice

来源: 杭电杯超级联赛5 算法: 博弈论 题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1048&pid=1010 补完: Yes

题目链接

题意简述

A和B两个人进行骰子游戏，这个游戏的规则是两个人分别摇两个装了\(n\)个骰子的骰蛊，之后从A开始喊点。可以任意喊” \(x(x≥1)\)个\(y(1≤y≤6)\)，B可以选择开点，即双方展示骰点，如果确实有\(x\)个及以上的\(y\)点骰子，A获胜，反之B获胜；B也可以选择继续喊点，但要比A的严格，即喊\(x_2（x_2≥x)\)个\(y_2(1≤y_2≤6)\)，或者\(x\)个\(y_2(y_2>y)\)。A同样有这两种选择，喊点要比B这轮的更严格，直到有人选择开点，游戏结束。

特别地，①1点如果没有被提到，它可以充当任何数；②一个蛊内是清一色的骰子，可以视为这种骰子有多一个，比如n=5时，一个蛊内有5个6，视为蛊内有6个6；③如果蛊内所有点不重复，视为蛊内没有骰子。

但是。高贵的A和B不喜欢”愚蠢的机会游戏“，所以他们要在知道所有骰子点数结果的情况下游戏，问你在双方使用最优策略的情况下A是否获胜。

题目分析

不喜欢机会游戏不要玩骰子！

题目详细介绍了这个游戏的规则（虽然没提能不能看对方点数但是正常游戏当然不能啊），然后告诉你这两个玩家他们不完全遵守规则。

那么题目里有用的是什么呢。

第一，是这个游戏大致的规则，回看题意即可。

第二，喊点必须一次比一次严格。

第三，所有点不重复的花色视为蛊内没有骰子。

那么，在知道所有骰点结果的情况下，先手的A当然喊符合点数结果的，最严格的骰点情况。这时，B不论怎么选都是必输的：开点的话，A喊的是符合的，A赢了；喊点的话，A喊的已经是符合条件的最严格骰点了，B不管喊什么，A开点之后都是A赢。

差点考虑直接输出Win了呢。

但虽然这题极其离谱，倒也没有离谱到A纯纯必赢。

注意，所有点不重复的花色是视为无骰子的。也就是如果这两个人手气好得出奇，两个骰蛊都骰出了蛊内完全不重复的花色，这个情况是相当于整个场上没有骰子。

那无论A喊什么点都不可能满足，这个情况A是必输的。

完整代码

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
#include<iostream>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int pointA[10],pointB[10];
		for(int i=1;i<=6;i++){
			pointA[i]=0;
			pointB[i]=0;
		}
//↓统计骰点结果
		for(int i=0;i<n;i++){
			int a;
			cin>>a;
			pointA[a]++;
		}
		for(int i=0;i<n;i++){
			int a;
			cin>>a;
			pointB[a]++;
		}
		int flag=0;
		for(int i=1;i<=6;i++){
			if(pointA[i]>1||pointB[i]>1){
				//有重复点，即存在一个蛊有有效点，A必赢
				flag=1;
				break;
			}
		}
		if(flag==1){
			cout<<"Win!\n";
		}
		else {
			cout<<"Just a game of chance.\n";	
		}
	}
	return 0;
}