输入求条>-<
查看原帖
输入求条>-<
1152154
Chinami_Nagisa楼主2024/9/26 21:27

第一次做大模拟,条了老半天,结果锣鼓输出与本地输出不一致,只有40pts,加了prb[i].erase(prb[i].end()-1);之后好像把句号都删了,全都RE

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;
int M,N,P;
int num;  //罪犯个数(必须等于一)
int gid;  //罪犯id
int day;  //星期几
int numlie;
string prb[105];  //证词
string content[5]=
{
    "I am guilty.",
    "I am not guilty.",
    "is guilty.",
    "is not guilty.",
    "Today is"
};
struct Name{
    string name;
    int islier; //0为初始状态,-1为确定过不说谎,1为确定过说谎
    int sayday; //该学生说今天是星期几
    bool useless;  //初始均没用(因为没说话也不知道是不是说谎者)
} stu[21];
map<string,int> ma;  //名字->id

string take23(string h)
{
    string temp;
    short flag=0;
    for(int i=0;;i++)
    {
        if(flag==2)
        {
            for(int j=i;h[j]!=' ';j++)
                temp+=h[j];
            return temp;
        }
        if(h[i]==':') flag++;
        if(flag==1&&h[i]==' ') flag++;
    }
    return "还是赤石大佬";
}

string takename(string h)
{
    string temp;
    for(int i=0;h[i]!=':';i++)
        temp+=h[i];
    return temp;
}

int takeday(string h)
{
    int i=0;
    while(h[i]!='s') i++;
    string temp;
    for(int j=i+2;h[j]!='.';j++)
    temp+=h[j];
    if(temp=="Monday") return 1;
    if(temp=="Tuesday") return 2;
    if(temp=="Wednesday") return 3;
    if(temp=="Thursday") return 4;
    if(temp=="Friday") return 5;
    if(temp=="Saturday") return 6;
    if(temp=="Sunday") return 7;
    return -114514;
}

bool judgelier1(int id1,int idb,int id)  //id1说idb是罪犯,而id是真正罪犯
{
    if(idb!=id) //如果ta不是罪犯,ta就在说谎
    {
        if(stu[id1].islier==0)   //没确认过,确认一下,标记身份,统计人数
        {
            numlie++;
            stu[id1].islier=1;
        }
        else if(stu[id1].islier==-1)  //确定过不说谎却又说谎
        return false;
    }
    else //是罪犯,没说谎
    {
        if(stu[id1].islier==0) stu[id1].islier=-1;
        else if(stu[id1].islier==1) return false;
    }
    return true;
}

bool judgelier2(int id1,int idb,int id)  //id1说idb不是罪犯
{
    if(idb==id) //如果ta是罪犯,ta就在说谎
    {
        if(stu[id1].islier==0)   //没确认过,确认一下,标记身份,统计人数
        {
            numlie++;
            stu[id1].islier=1;
        }
        else if(stu[id1].islier==-1)  //确定过不说谎却又说谎
        return false;
    }
    else //不是罪犯,没说谎
    {
        if(stu[id1].islier==0) stu[id1].islier=-1;
        else if(stu[id1].islier==1) return false;
    }
    return true;
}

bool judge(int id)  //判断当id为罪犯时是否成立
{
    numlie=0;
    day=0;
    for(int i=0;i<M;i++) stu[i].islier=0; //别忘了stu数组初始化
    for(int i=0;i<P;i++)
    {
        int k;
        if(numlie>N) return false; //已经大于了剪枝
        for(int j=0;j<5;j++)
        {
            k=prb[i].find(content[j]);
            if(k==-1) continue;
            string gname=takename(prb[i]);  //名字
            int tgid=ma[gname];   //标号
            switch(j)
            {
                case 0:  //说自己是罪犯
                	if(judgelier1(tgid,tgid,id)==false) return false; break;
                case 1:  //说自己不是罪犯
                	if(judgelier2(tgid,tgid,id)==false) return false; break;
                case 2: //说XX是罪犯
                {
                    string pname=take23(prb[i]);
                    int pid=ma[pname];
                    if(judgelier1(tgid,pid,id)==false) return false;
                }break;
                case 3: //说XX不是罪犯
                {
                    string pname2=take23(prb[i]);
                    int pid2=ma[pname2];
                    if(judgelier2(tgid,pid2,id)==false) return false;
                }break;
                case 4: //说今天星期几(待处理)
                {
                    if(stu[tgid].sayday==0) stu[tgid].sayday=takeday(prb[i]);  //如果没被更新就更新(因为只用更新一次)
                }break;
                default:break;
            }
            break;  //发现了就content没必要再循环了
        }
    }
    int n=0;
    for(int m=0;m<M;m++)  //判断星期几是否冲突(先判断不说谎的明确事实)
    {   //考虑:如果说了两次不一样的星期呢?
        int pday=stu[m].sayday;//换元(
        if(pday==0) continue;  //别忘了重要的剪枝!!!
        if(stu[m].islier==-1) //不说谎,跟真正星期几是否冲突
        {
            if(day==0) day=pday;
            else if(day!=pday) return false;
            else continue;
        }
    }
    for(int m=0;m<M;m++)
    {  
        int pday=stu[m].sayday;//换元(
        if(pday==0) continue; 
        if(stu[m].islier==0)
        {
        	if(day!=pday)
        	{
        		stu[m].islier=1;
        		numlie++;
			}
		}
        if(stu[m].islier==1)
        {
            if(day==pday) return false;
            else continue;
        }
    }
    for(int m=0;m<M;m++)    //numlie是一个范围,有人不能确定即islier=0,人数设为n,对于i=0~n,存在numlie+i==N就行了
    {
    	if(stu[m].islier==0) n++;
    	if(numlie+n==N) return true;
	}
    return false;
}
int main(){
    cin>>M>>N>>P;
    for(int i=0;i<M;i++)
    {
        cin>>stu[i].name;
        ma[stu[i].name]=i;
    }
    getchar();
    for(int i=0;i<P;i++)
    {
    	getline(cin,prb[i]);
    	prb[i].erase(prb[i].end()-1);
	}
    int ans=0;
    for(int i=0;i<M;i++)  //枚举每个罪犯
    {
        if(judge(i)) ans++,gid=i;
        if(ans>1) break;
    }
    if(ans==1) cout<<stu[gid].name;
    else if(ans>1) cout<<"Cannot Determine";
    else if(ans==0) cout<<"Impossible";
    return 0;
}
2024/9/26 21:27
加载中...