Logo S08577 的博客

博客

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

...
S08577
2025-12-01 12:57:29

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$。

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

  1. I am guilty.

  2. I am not guilty.

  3. (此处为空格)is guilty.

  4. (此处为空格)is not guilty.

  5. 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 函数

分两个角度判断：

  1. 若 $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;
}

撒花完结。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

服务器时间: 2026-03-15 06:25:52 | 开源项目