2015
04-16

# 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.

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;
}



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指针是否为空，若为空，则出队指针即为所求。