P1039 [NOIP2003 提高组] 侦探推理题解

__S08577__ · 2024-02-23 16:18:28 · 题解

题意

简简单单，自己看题去。

题目传送门

思路

注：不知道某变量数组干什么用时请看定义。

定义

定义一个数组 week,记录编号从 1 到 7 日期的句子。

string weeks[10]={
    "11451411",
    "Today is Monday.",
    "Today is Tuesday.",
    "Today is Wednesday.",
    "Today is Thursday.",
    "Today is Friday.",
    "Today is Saturday.",
    "Today is Sunday."
};

定义一个 map nameid 存名字的编号。

定义一个结构体数组 names，id 存名字的编号，zh 存证词。

定义一个数组 dis 判断第 i 句话是否是真的。

若 dis_i 为 -1，则第 i 句话不确定真假。

若 dis_i 为 0，则第 i 句话是假的。

若 dis_i 为 1，则第 i 句话是真的。

定义两个变量 tr 和 fs，分别记录真话个数和假话个数。

定义一个变量 chiefid 记录凶手编号。

定义一个变量 pos 记录题目中要求的5个字符串是否出现过，若 pos 等于 -1 ，说明此字符串没有出现过，否则就是出现过（因为pos=s.find("...");)

传入 check 的一个参数 na，代表 main 中枚举的犯人编号。

传入 check 的一个参数 day, 代表 main 中枚举的日期。

传入 judge 的一个参数 i，代表 check 中枚举的犯人编号。

传入 judge 的一个参数 f, 代表 check 中，根据题意是否符合要求。

main 函数

首先我们能看出这是一道纯纯的模拟题。

这道题细节很多，有些还有坑人的地方。

我们先可以记录说话的人以及他的编号。再记录证词。

注意：输入人名时，要用 erase函数删去人名后面的冒号，输入证词时用getline，要删去开头的一个空格。

我们遍历每一个人，每一个日子（从周一到周天），将它们放入check函数中进行判断查找，并记录犯人编号。

如果犯人编号记录了，也就是犯人编号不是0，就可以输出，负责输出 Impossible。

注：要在输入完证词猴判断后面是否有换行符，（不是谁做题回想这个，还不是看题解，无语了，亲测，不加此句只得50分）

main代码

signed main(){
    cin>>m>>n>>p;
    for(int i=1;i<=m;i++){
        cin>>name[i];
        nameid[name[i]]=i;
    }
    for(int i=1;i<=p;i++){
        string na;
        cin>>na;
        na.erase(na.size()-1,1);
        //cout<<na;
        //char kong;
        //cin>>kong;//读入中间的空格
        string zh;//证词
        getline(cin,zh);
        zh.erase(0,1);
        if(zh[zh.size()-1]=='\n'||zh[zh.size()-1]=='\r')
                zh.erase(zh.size()-1,1);
        //cout<<zh<<endl;
        names[i].id=nameid[na];
        names[i].zh=zh;

    }
    //cout<<endl;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=7;j++){
            check(i,j);
        }
    }
    if(chiefid==0){
        cout<<"Impossible";
        return 0;
    }
    cout<<name[chiefid]<<endl;
    return 0;
}

check 函数

将 tr,fs 初始化为 0。

将 dis 初始化为 -1。

遍历每一条证词，寻找题目要求的五句话：

I am guilty.
I am not guilty.
(此处为空格)is guilty.
(此处为空格)is not guilty.
Today is(此处为空格)

如果找到了，那么进入 judge 函数，判断此句是否为真。

如果 judge 为真，那么直接结束 check。

在 check 的倒数第二步，判断 chiefid 是否是第二次出现（即chiefid \ne 0 and chiefid \ne na )

最后，将 chiefid 赋为 na。

check 代码

void check(int na,int day){
    //cout<<chiefid;
    tr=0;
    fs=0;
    memset(dis,-1,sizeof(dis));
    for(int i=1;i<=p;i++){
        int pos;
        pos=names[i].zh.find("I am guilty");
        if(pos!=-1){
            //cout<<114514;
            bool f=names[i].id==na;
            if(judge(names[i].id,f)){
                //cout<<1919810;

                return ;
            }
        }
        pos=names[i].zh.find("I am not guilty");
        if(pos!=-1){
            bool f=names[i].id!=na;
            if(judge(names[i].id,f)){

                return ;
            }
        }
        pos=names[i].zh.find(" is guilty.");
        //cout<<"pos: "<<pos<<endl;
        if(pos!=-1){

            string nam=names[i].zh;
            nam.erase(pos,11);//截掉后面的只保留前面名字
            bool f=nameid[nam]==na;
            if(judge(names[i].id,f)){

                return ;
            }
        }
        pos=names[i].zh.find(" is not guilty.");
        //cout<<"pos: "<<pos<<endl;
        if(pos!=-1){
            string nam=names[i].zh;
            nam.erase(pos,15);//同上
            bool f=nameid[nam]!=na;
            if(judge(names[i].id,f)){

                return ;
            }
        }
        pos=names[i].zh.find("Today is ");
        if(pos!=-1){
            bool f=names[i].zh==weeks[day];
            if(judge(names[i].id,f)){

                return;
            }
        }
    }
    if(chiefid!=0&&chiefid!=na){
        //cout<<endl<<na<<" "<<day<<" "<<chiefid<<endl;
        cout<<"Cannot Determine";
        exit(0);
    }
    chiefid=na;

    return ;
}

judge 函数

分两个角度判断：

若 dis_i=-1

2.其他情况

情况1：将 dis_i 赋值为 f。如果 f 为真，tr 加一；反之，fs 加一。

情况2：如果 dis_i 等于 f,返回假，否则返回真。

最后判断一下真话个数和假话个数是否合法，合法返回假，否则返回真。

注：judge 返回真就是在 check 中直接return。

judge 代码

bool judge(int i,bool f){
    //cout<<endl<<"T "<<tr<<"  F "<<fs<<endl<<endl;
    //cout<<endl<<i<<" "<<f<<endl;
    if(dis[i]==-1){
        dis[i]=f;
        if(f){
            tr++;
        }
        else{
            fs++;
        }
    }
    else{
        if(dis[i]==f){
            return 0;
        }
        else return 1;
    }
    if(fs<=n&&tr<=m-n){
        return 0;
    }
    return 1;
}

总代码

#include<iostream>
#include<cstring>
#include<string>
#include<map>
#define int long long
using namespace std;
const int N=5005;
string weeks[10]={
    "11451411",
    "Today is Monday.",
    "Today is Tuesday.",
    "Today is Wednesday.",
    "Today is Thursday.",
    "Today is Friday.",
    "Today is Saturday.",
    "Today is Sunday."
};
int a[N];
int f[2][N];
int b[N];
int n,m,p;
int dis[N];
string name[N];
map<string,int> nameid;//每个名字的下标
struct namess{
    string zh;
    int id;
}names[N];
int tr,fs;
bool judge(int i,bool f){
    //cout<<endl<<"T "<<tr<<"  F "<<fs<<endl<<endl;
    //cout<<endl<<i<<" "<<f<<endl;
    if(dis[i]==-1){
        dis[i]=f;
        if(f){
            tr++;
        }
        else{
            fs++;
        }
    }
    else{
        if(dis[i]==f){
            return 0;
        }
        else return 1;
    }
    if(fs<=n&&tr<=m-n){
        return 0;
    }
    return 1;
}
int chiefid;
void check(int na,int day){
    //cout<<chiefid;
    tr=0;
    fs=0;
    memset(dis,-1,sizeof(dis));
    for(int i=1;i<=p;i++){
        int pos;
        pos=names[i].zh.find("I am guilty");
        if(pos!=-1){
            //cout<<114514;
            bool f=names[i].id==na;
            if(judge(names[i].id,f)){
                //cout<<1919810;

                return ;
            }
        }
        pos=names[i].zh.find("I am not guilty");
        if(pos!=-1){
            bool f=names[i].id!=na;
            if(judge(names[i].id,f)){

                return ;
            }
        }
        pos=names[i].zh.find(" is guilty.");
        //cout<<"pos: "<<pos<<endl;
        if(pos!=-1){

            string nam=names[i].zh;
            nam.erase(pos,11);
            bool f=nameid[nam]==na;
            if(judge(names[i].id,f)){

                return ;
            }
        }
        pos=names[i].zh.find(" is not guilty.");
        //cout<<"pos: "<<pos<<endl;
        if(pos!=-1){
            string nam=names[i].zh;
            nam.erase(pos,15);
            bool f=nameid[nam]!=na;
            if(judge(names[i].id,f)){

                return ;
            }
        }
        pos=names[i].zh.find("Today is ");
        if(pos!=-1){
            bool f=names[i].zh==weeks[day];
            if(judge(names[i].id,f)){

                return;
            }
        }
    }
    if(chiefid!=0&&chiefid!=na){
        //cout<<endl<<na<<" "<<day<<" "<<chiefid<<endl;
        cout<<"Cannot Determine";
        exit(0);
    }
    chiefid=na;

    return ;
}
signed main(){
    cin>>m>>n>>p;
    for(int i=1;i<=m;i++){
        cin>>name[i];
        nameid[name[i]]=i;
    }
    for(int i=1;i<=p;i++){
        string na;
        cin>>na;
        na.erase(na.size()-1,1);
        //cout<<na;
        //char kong;
        //cin>>kong;//读入中间的空格
        string zh;//证词
        getline(cin,zh);
        zh.erase(0,1);
        if(zh[zh.size()-1]=='\n'||zh[zh.size()-1]=='\r')
                zh.erase(zh.size()-1,1);
        //cout<<zh<<endl;
        names[i].id=nameid[na];
        names[i].zh=zh;

    }
    //cout<<endl;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=7;j++){
            check(i,j);
        }
    }
    if(chiefid==0){
        cout<<"Impossible";
        return 0;
    }
    cout<<name[chiefid]<<endl;
    return 0;
}

撒花完结。

P1039 [NOIP2003 提高组] 侦探推理 题解

题意

思路

定义