POJ1478HDU1470ZOJ1252UVA592UVALive5625IslandofLogic

[复制链接]
查看1 | 回复0 | 2020-5-6 06:01:43 | 显示全部楼层 |阅读模式
Kruskal算法的C语言程序weixin_43809189:[reply]tigerisland45[/reply]你好,我需要计算180x180的矩阵,改了数组大小以后还是算不了呢,是数太多了吗DescriptionTheIslandofLogichasthreekindsofinhabitants:divinebeingsthatalwaystellthetruth,evilbeingsthatalwayslie,andhumanbeingsthataretruthfulduringthedayandlieatnight.Everyinhabitantrecognizesthetypeofeveryotherinhabitant.Asocialscientistwantstovisittheisland.Becauseheisnotabletodistinguishthethreekindsofbeingsonlyfromtheirlooks,heasksyoutoprovideacommunicationanalyzerthatdeducesfactsfromconversationsamonginhabitants.Theinterestingfactsarewhetheritisdayornightandwhatkindofbeingsthespeakersare.InputTheinputcontainsseveraldescriptionsofconversations.Eachdescriptionstartswithanintegern,thenumberofstatementsintheconversation.Thefollowingnlineseachcontainonestatementbyaninhabitant.Everystatementlinebeginswiththespeaker’sname,oneofthecapitallettersA,B,C,D,E,followedbyacolon`:’.Nextisoneofthefollowingkindsofstatements:Iam[not](divine|human|evil|lying).Xis[not](divine|human|evil|lying).Itis(day|night).Squarebrackets[]meanthatthewordinthebracketsmayormaynotappear,roundbrackets()meanthatexactlyoneofthealternativesseparatedby|mustappear.XstandsforsomenamefromA,B,C,D,E.Therewillbenotwoconsecutivespacesinanystatementline,andatmost50statementsinaconversation.Theinputisterminatedbyatestcasestartingwithn=0.OutputForeachconversation,firstoutputthenumberoftheconversationintheformatshowninthesampleoutput.Thenprint“Thisisimpossible.”,iftheconversationcannothappenaccordingtotherulesor``Nofactsarededucible.’’,ifnofactscanbededuced.Otherwiseprintallthefactsthatcanbededuced.Deducedfactsshouldbeprintedusingthefollowingformats:Xis(divine|human|evil).Itis(day|night).Xistobereplacedbyacapitalletterspeakername.Factsaboutinhabitantsmustbegivenfirst(inalphabeticalorder),thenitmaybestatedwhetheritisdayornight.Theoutputforeachconversationmustbefollowedbyasingleblankline.SampleInput1A:Iamdivine.1A:Iamlying.1A:Iamevil.3A:Bishuman.B:Aisevil.A:Bisevil.0SampleOutputConversation#1Nofactsarededucible.Conversation#2Thisisimpossible.Conversation#3Aishuman.Itisnight.Conversation#4Aisevil.Bisdivine.HintTomakethingsclearer,wewillshowthereasoningbehindthethirdinputexample,whereAsays``Iamevil.’’.Whatcanbededucedfromthis?ObviouslyAcannotbedivine,sinceshewouldbelying,similarlyAcannotbeevil,sinceshewouldtellthetruth.Therefore,Amustbehuman,moreover,sincesheislying,itmustbenight.Sothecorrectoutputisasshown.Inthefourthinputexample,itisobviousthatAislyingsincehertwostatementsarecontradictory.So,Bcanbeneitherhumannorevil,andconsequentlymustbedivine.Balwaystellsthetruth,thusAmustbeevil.Voila!SourceSouthwesternEuropeanRegionalContest1997Regionals1997Europe-Southwestern问题链接:POJ1478HDU1470ZOJ1252UVA592UVALive5625IslandofLogic问题简述:(略)问题分析:逻辑推理问题,用暴力解决,逻辑有点复杂。对于说的每一句话,用特征来识别。程序说明:(略)参考链接:(略)题记:(略)AC的C++程序如下:/*POJ1478HDU1470ZOJ1252UVA592UVALive5625IslandofLogic*/#includeiostream#includecstdio#includecstringusingnamespacestd;constchar*NAMES[]={"divine","evil","human"};constintDIVINE=0,EVIL=1,HUMAN=2;//神,恶魔,人constintDAY=0,NIGHT=1;constintM=5;//最多说话人数,说话者A-EconstintN=3*3*3*3*3*2;//3*3*3*3*3*2=486(A类数*B类数*...*E类数*白天或黑夜)constintL=48;intcaseno=0;boolstate[N];intpossible[M];chars[L];inttype(intstate,intp)state=1;while(p--)state/=3;return(state%3);//谎话判定intjudge(intstate,intp)intt=type(state,p);return(t==EVIL||(t==HUMAN(state1)==NIGHT));voidsolve()gets(s);intspeaker=s[0]-'A';if(s[3]=='I's[4]=='t'){//有关白天和黑夜的处理(Itisdayornight.)for(inti=0;iN;i++){//枚举所有组合,注意每个state对应一条不同的语句intflag=((i1)==DAYs[9]=='d')||((i1)==NIGHTs[9]=='n');if(judge(i,speaker)==flag)state=false;//谎话判定}else{//其他句子处理inttarget=(s[5]=='a'?speaker:s[3]-'A');//谈论对象intneg=(s[8]=='n');//is"not"?intt=0;switch(s[8+4*neg])case'd':t=DIVINE;break;case'e':t=EVIL;break;case'h':t=HUMAN;break;case'l':for(inti=0;iN;i++)if(judge(i,speaker)==(neg^judge(i,target)))state=false;//谎话判定return;for(inti=0;iN;i++)if(judge(i,speaker)==(neg^(type(i,target)==t)))state=false;//谎话判定voidoutput()intdaynight=-1;booldeduction=false;memset(possible,-1,sizeof(possible));for(inti=0;iN;i++)if(state){if(daynight!=-1daynight!=(i1))daynight=-2;//出现多种可能elseif(daynight==-1)daynight=i1;for(intj=0;jM;j++)if(possible[j]!=-1possible[j]!=type(i,j))///出现多种可能possible[j]=-2;elseif(possible[j]==-1)possible[j]=type(i,j);printf("Conversation#%dn",++caseno);if(daynight==-1)puts("Thisisimpossible.");else{for(inti=0;iM;i++)if(possible=0){printf("%cis%s.n",i+'A',NAMES[possible]);deduction=true;if(daynight=0){printf("Itis%s.n",daynight==DAY?"day":"night");deduction=true;if(!deduction)puts("Nofactsarededucible.");putchar('n');intmain()intn;while(~scanf("%d",n)n){getchar();memset(state,true,sizeof(state));for(inti=0;in;i++)solve();output();return0;
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则