2 u010510549 u010510549 于 2013.12.31 23:12 提问

好像不难的算法题acm求解答

描述

去长春的飞机上,Bear Kids队跟One Piece队的队员深感无聊,于是,他们6个人玩起了一个很简单的游戏。
游戏规则是这样的,简化版狼人游戏,游戏中,身份只有两种,平民跟狼人。
游戏分为天黑阶段跟天亮阶段,天黑的时候,狼人们会统一杀死一个平民,记住,是统一,随机,而已只有一个!
天亮的时候,所有人会出来投票杀死一个人,平民的话,会随机投一个人,当然,他不会投自己,狼人的话,他们会统一意见,集中投死一个平民,当然,也是随机。
得票最高的人就要被处死,如果有多人票数相同,则编号小的那个人被处死。
当游戏成员只剩平民时,平民胜利;当游戏成员只剩狼人时,狼人胜利。
那天,这六个人约好,输的一方请吃饭。六个人中,有两个狼人,四个平民,YYS跟WYH是狼人,LY,LYS,胖子,小马哥是平民,他们的游戏ID分别是1,2,3,4,5,6。
第一轮天黑的时候,YYS跟WYH就把LYS杀了,天亮的时候,YYS投了小马哥,WYH当然也投了小马哥,LY投了YYS,胖子投了LY,小马哥投了YYS(平民是随机投票的),
这时,由于YYS跟小马哥的票数相同,都是两票,但是,YYS是1号,小马哥是6号,因此,YYS挂了;
又一轮天黑,WYH把胖子杀了,天亮的时候,英明神武的LY跟小马哥都投了WYH(再强调一次,他们是随机投票的!),不用说了,WYH2票必须出局,平民胜利!
好了,未来的ACMER,现在你需要设计一个程序,要求是这样的:给出游戏人数,游戏轮数,接着再给出每一轮里面,天黑的时候谁死了,天亮的时候,
他们分别投票投了谁,最后是狼人胜利还是平民胜利。你根据这些条件,判断出有多少人可能是狼人。这题很简单,相信难不倒你!

输入格式

第一行输入一个数T(T<=100),表示CASE数,第二行,两个数n(2<=n<=1000),k(1<=k<n),分别表示游戏人数和游戏轮数,
注意,参与游戏的人员的编号是1到n,接着,有k行,每行第一个数x,表示天黑的时候,x被狼人杀死了,后面紧跟n个数,
分别代表n个人这一轮投票投了谁(编号),-1则表示该人已死,无投票权利,当然,最后一轮的时候,可能出现天黑狼人杀人后,
游戏直接结束了,那么,天亮的投票阶段则用n个0代替。最后一行,是字符串,“haha”表示狼人胜利,“hehe”表示平民胜利。
输出格式

每组数据输出一行,一个数res(res>0),表示有多少人可能是狼人。
输入样例

1
6 2
4 6 6 1 -1 3 1
5 -1 3 2 -1 -1 2
hehe
输出样例

2

我就暴力解 错了
我是先标记那些能够直接知道身份的
其他默认是狼人,然后进行判断,没有矛盾就是
就错了
#include

using namespace std;
int a[1001][1001],c[1001],vote2[1001];
int vote[1001];
bool victory;
string s;
int last;
int countn(int n,int k){
for(int i =1;i<=n;i++)
if(c[i]==0){
int j=0;
for(;j<k;j++){
if(a[j][i]==-1){j=k;break; }
if(a[j][i]!=a[j][last]) break;
}
c[i]=j==k;

}

int num=0;
for(int i =1;i<=n;i++)
if(c[i]==1) {num++;
}
return num;
}

int deal(int n,int k)
{
for(int i=0; i<k; i++)
c[a[i][0]]=-1;
for(int i=1; i<=n; i++)if(a[k-1][i]!=-1)
vote[a[k-1][i]]++;

if(victory)
{

    int maxn=0;
    for(int i=1; i<=n; i++)
        if(vote[i]>vote[maxn])  maxn=i;

    if(maxn!=0)
    {
  c[maxn]=-1;

        for(int i=1; i<=n; i++)
        {
            if(a[k-1][i]!=-1&&i!=maxn){ c[i]=1;
            last=i;

            }
        }
    }
    else
    {   int maxn=0;
        for(int i=1; i<=n; i++)if(a[k-2][i]!=-1)
        vote2[a[k-2][i]]++;

         for(int i=1; i<=n; i++)
          if(vote2[i]>vote2[maxn])  maxn=i;


        for(int i=1; i<=n; i++)
        {
            if(a[k-2][i]!=-1&&i!=a[k-1][0]&&i!=maxn) {c[i]=1;

            last=i;

            }
        }




        }
}
    else
    {

    int maxn=0;
    for(int i=1; i<=n; i++)
        if(vote[i]>vote[maxn])  maxn=i;

  c[maxn]=1;

last=maxn;
for(int i=1;i<=n;i++)
if(a[k-1][i]!=-1&&i!=maxn) c[i]=-1;

    }




    return countn(n,k);
}



int main()
{
    int t,n,k;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        memset(c,0,sizeof(c));
        memset(vote,0,sizeof(vote));
         memset(vote2,0,sizeof(vote2));
        for(int i=0; i<k; i++)
            for(int j=0; j<=n; j++)
                cin>>a[i][j];
        cin>>s;
        victory=(s=="haha");

       cout<< deal(n,k)<<endl;

    }
    return 0;
}
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!