30求救样例没过(悬赏一个冠珠)
查看原帖
30求救样例没过(悬赏一个冠珠)
594257
sad_desert楼主2022/8/1 22:01
// 0代表未判断1代表确定是2代表确定不是 
//1-7周几,10-100 a-10是犯人 100-1000 a-100不是犯人 1001-1007今天不是周a-1000
#include<iostream>
using namespace std;
int zuifanshu,kong,is[30],yan[30][120],k,zushu,zu[190000][21],n,m,p,b[30],zhou[10],zheng1[30];
string zuifan,a[30],y,ming;
bool zheng,I,ywzui;
int zhouji(string day){
    if(day=="Monday")return 1;
    if(day=="Tuesday")return 2;
    if(day=="Wednesday")return 3;
    if(day=="Thursday")return 4;
    if(day=="Friday")return 5;
    if(day=="Saturday")return 6;
    if(day=="Sunday")return 7;
    return 0;
}
int souming(string ming){
    for(int i=1;i<=n;++i)
        if(a[i]==ming)
            return i;
    if(ming=="I")
        return 1000000;
    if(ming=="Today")
        return 100000000;
    return -999;
}
void bfs(int lt,int c){
    if(c>n){
        for(int i=1;i<=n;++i){
            zu[k][i]=b[i];
        }
        ++k;
        return;
    }
//  cout<<lt+1<<' ';
    for(int i=lt+1;i<=m;i++){
        b[c]=i;
        bfs(i,c+1);
    }
}
int zuhe(int m,int n){
    long long zuheshu=1,i=m;
    for(;i>=m-n+1;--i){
        zuheshu*=i;
    }
    for(i=2;i<=n;++i){
        zuheshu/=i;
    }
    return zuheshu;
} 
bool huang(int zu1,int ren){
    for(int i=1;i<=n;i++){
        if(zu[zu1][i]==ren)
            return 1;
    }
    return 0;
}
//有m人n人撒谎p句证言 
int main(){
    int i;
    cin>>m>>n>>p;
    zushu=zuhe(m,n);
    bfs(0,1);
    for(i=1;i<=m;++i)
        cin>>a[i];
    for(i=1;i<=p;++i){
        getline(cin,y);
        int kong=0;
        if(y.size()-1=='.'){
            for(k=0;k<y.size();++k){
                if(y[k]==' ')
                    ++kong;
            }
            if(kong==3||kong==4){
                int l=0,r=0,ming;
                int fri=0,zhiren;
                string name="",zhi="";
                for(k=0;k<y.size();++k,++r){
                    if(y[k]==' '&&fri==0){
                        r-=2;
                        ++fri;
                        for(int j=l;j<=r;j++){
                            name+=y[j];
                        }
                        ming=souming(name);
                    }
                    if(y[k]==' '&&fri==1){
                        r-=1;
                        ++fri;
                        zhiren=-0x3f3f;
                        for(int j=l;j<=r;j++){
                            name+=y[j];
                        }
                        zhiren=souming(zhi);
                        if(zhiren==-999)
                            continue;
                    }
                    if(y[k]==' '&&fri==2){
                        r-=1;
                        ++fri;
                        for(int j=l;j<=r;j++){
                            name+=y[j];
                        }
                        if(name.size()!=2||(name!="am"&&name!="is"))
                            continue;
                        if(zhiren==1000000&&name=="is")
                            continue;
                        if(zhiren!=1000000&&name=="am"&&zhiren!=1000000&&a[zhiren]!="I")
                            continue;
                        if(name=="am")I=1;
                        else I=0;
                    }
                    if(y[k]==' '&&fri==3){
                        r-=1;
                        ++fri;
                        for(int j=l;j<=r;j++){
                            name+=y[j];
                        }
                        if(name!="not")
                            continue;
                    }
                    if(y[k]=='.'&&fri==3){
                        r-=1;
                        ++fri;
                        for(int j=l;j<=r;j++){
                            name+=y[j];
                        }
                        if(name!="guilty"&&ming!=1000000)
                            continue;
                        if(I==1)yan[ming][zheng1[ming]++]=ming+10;
                        if(ming==1000000&&zhouji(name)==0)
                            continue; 
                        if(ming==1000000&&zhouji(name))
                            yan[ming][zheng1[ming]++]=zhouji(name);
                        if(ming!=1000000&&zhiren<30&&souming(a[zhiren]))
                            yan[ming][zheng1[ming]++]=souming(name)+10;
                    }
                    if(y[k]=='.'&&fri==4){
                        r-=1;
                        ++fri;
                        for(int j=l;j<=r;j++){
                            name+=y[j];
                        }
                        if(name!="guilty"&&ming!=1000000)
                            continue;
                        if(ming==1000000)
                            continue;
                        if(I==1)yan[ming][zheng1[ming]++]=ming+100;
                        if(ming!=1000000&&zhiren<30&&souming(a[zhiren]))
                            yan[ming][zheng1[ming]++]=souming(name)+100;
                    }
                }
            }
        }
    }
    for(i=0;i<zushu;++i){
        for(int j=1;j<=m;j++){//第j个人的证言 
            if(huang(i,j)){//他说谎 
                for(int p=0;p<zheng1[j];p++){
                    if(yan[j][p]<10){
                        if(zhou[yan[j][p]]==1){
                            for(int j=0;j<30;j++)is[j]=0;
                            for(int j=0;j<10;j++)zhou[j]=0;
                            continue;
                        }
                        zhou[yan[j][p]]=2;
                    }else if(yan[j][p]<100){
                        if(is[yan[j][p]-10]==1){
                            for(int j=0;j<30;j++)is[j]=0;
                            for(int j=0;j<10;j++)zhou[j]=0;
                            continue;
                        }is[yan[j][p]-10]=2;
                    }else{
                        if(is[yan[j][p]-100]==2){
                            for(int j=0;j<30;j++)is[j]=0;
                            for(int j=0;j<10;j++)zhou[j]=0;
                            continue;
                        }is[yan[j][p]-100]=1;
                    }
                }
            }else{
                for(int p=0;p<zheng1[j];p++){
                    if(yan[j][p]<10){
                        if(zhou[yan[j][p]]==2){
                            for(int j=0;j<30;j++)is[j]=0;
                            for(int j=0;j<10;j++)zhou[j]=0;
                            continue;
                        }
                        zhou[yan[j][p]]=1;
                    }else if(yan[j][p]<100){
                        if(is[yan[j][p]-10]==2){
                            for(int j=0;j<30;j++)is[j]=0;
                            for(int j=0;j<10;j++)zhou[j]=0;
                            continue;
                        }is[yan[j][p]-10]=1;
                    }else{
                        if(is[yan[j][p]-100]==1){
                            for(int j=0;j<30;j++)is[j]=0;
                            for(int j=0;j<10;j++)zhou[j]=0;
                            continue;
                        }is[yan[j][p]-100]=2;
                    }
                }
            }
        }
        for(int j=1;j<=m;j++){
            if(is[j]!=2&&ywzui==0)ywzui=1;
            if(is[j]!=2&&ywzui){
                for(int j=0;j<30;j++)is[j]=0;
                for(int j=0;j<10;j++)zhou[j]=0;
                continue;
            }
        }
        for(int j=1;j<=m;j++){
            if(is[j]!=2){
                zuifan=a[j];
            //  cout<<zuifan<<endl;
                zuifanshu++;
            }
        }
        for(int j=0;j<30;j++)is[j]=0;
        for(int j=0;j<10;j++)zhou[j]=0;//恢复原样 
    }
    if(zuifanshu==1)
        cout<<zuifan;
    if(zuifanshu==0)
        cout<<"Impossible";
    if(zuifanshu>2)
        cout<<"Cannot Determine";
    return 0;
}
2022/8/1 22:01
加载中...