首页 > ACM题库 > HDU-杭电 > HDU 4068-SanguoSHA-模拟-[解题报告]HOJ
2015
04-16

HDU 4068-SanguoSHA-模拟-[解题报告]HOJ

SanguoSHA

问题描述 :

Sanguosha has a singled version. Two players each select N heroes and start fighting. If a hero dies, the next follows. If one player’s heroes are all dead, he loses.
Random Maze

There’re restraints among heroes. For example, YuJi restricts Zhu Geliang, LuXun restricts DaQiao, ZhangJiao restricts MaChao, WeiYan restricts XiaoQiao.
Today I play with friends. I know the heroes and the restraints.(If opponent’s hero restraint my hero, my hero will be beaten, others my hero will beat opponent’s hero)
Can you arrange my heroes’ order,no matter what order of opponent’s heroes, so that I can win the game?

输入:

The first line is a number T(1<=T<=50), represents the number of case. The next T blocks follow each indicates a case.
The first line is N(3<=N<=6).
The second line has N names(shorter than 20 letter).
The following N lines each contains a restraints. Restraints are given as “k b1 b2 … bk”, which means the opponent’s hero restricts my hero b1, b2 … bk. (0<=K<=N)

输出:

The first line is a number T(1<=T<=50), represents the number of case. The next T blocks follow each indicates a case.
The first line is N(3<=N<=6).
The second line has N names(shorter than 20 letter).
The following N lines each contains a restraints. Restraints are given as “k b1 b2 … bk”, which means the opponent’s hero restricts my hero b1, b2 … bk. (0<=K<=N)

样例输入:

2
3
ZhugeLiang HuangYueying ZhenJi
1 ZhugeLiang
2 HuangYueying ZhenJi
2 ZhugeLiang ZhenJi
4
MaChao YanLiangWenChou YuJin XiaoQiao
2 MaChao XiaoQiao
2 YanLiangWenChou YuJin
1 XiaoQiao
0

样例输出:

Case 1: No
Case 2: Yes
MaChao YanLiangWenChou XiaoQiao YuJin

HDU-4068-SanguoSHA

http://acm.hdu.edu.cn/showproblem.php?pid=4068

字符串模拟,枚举自己和对手的牌的全排列即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int map[10][10];
char str[10][25];
int a[10],b[10];
int n,flag;
int check(int a[10],int b[10])
{
	int num1=1,num2=1;
	while(num1<=n&&num2<=n)
	{
		if(map[b[num2]][a[num1]])
		num1++;
		else
		num2++;
	}
	if(num2>num1)
	return 1;
	return 0;
}
int main()
{
	int k,t,i,tt,j;
	char s[25];
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		scanf("%s",str[i]);
		memset(map,0,sizeof(map));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&tt);
			while(tt--)
			{
				scanf("%s",s);
				for(j=1;j<=n;j++)
				if(strcmp(s,str[j])==0)
				{
					map[i][j]=1;
					break;
				}
			}
		}
		for(i=1;i<=n;i++)
		a[i]=i;
		do
		{
			flag=1;
			for(i=1;i<=n;i++)
			b[i]=i;
			do
			{
				if(!check(a,b))
				{
					flag=0;
					break;
				}
			}while(next_permutation(b+1,b+n+1));
			if(flag)
			break;
		}while(next_permutation(a+1,a+n+1));
		printf("Case %d: ",k);
		if(flag==0)
		printf("No\n");
		else
		{
			printf("Yes\n");
			for(i=1;i<=n;i++)
			{
				if(i==n)
				printf("%s\n",str[a[i]]);
				else
				printf("%s ",str[a[i]]);
			}
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/cambridgeacm/article/details/7821914


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。