侦探推理

先上链接,各位可以先去尝试一下:P1039 侦探推理 - 洛谷

这是一道难度标记为: 提高+/省选- 的题目,但个人感觉处理好字符串后并不难。

题目描述

明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中的一个人充当罪犯(在明明不知情的情况下),明明的任务就是找出这个罪犯。接着,明明逐个询问每一个同学,被询问者可能会说:

证词.png

证词中出现的其他话,都不列入逻辑推理的内容。

明明所知道的是,他的同学中有NN个人始终说假话,其余的人始终说真。

现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一个!

解题思路

刚刚拿到题就发现证词内容可能会比较难处理!(这里说的CPP,其他语言会好很多)

最初想到:枚举出每个玩家是囚犯的可能性,然后再检查是否合理。

尝试以后,发现这种方法只能处理指认罪犯和证明谁不是罪犯,一到说日期相关的时候就会出问题。

后来,想到一种更好的方法,只需在基础上增加日期的枚举,既然无法确定日期,就假设一个日期。

输入格式

由于换行符问题,直接使用 getline 函数无法取得准确的证词!

请将以下代码放置在输入前(本地测试不需要):

char ch=getchar();
while(ch==10)ch=getchar();getchar();

以及在取得输入数据后使用以下方法处理证词:

talks[i].erase(talks[i].end() - 1);

使用以上方法即可在洛谷正常运行代码(否则全WA!!)

语法解析

我的想法是将语法解析为一个 map<string, int> 它会存放一条证词的状态信息。

typedef map<string, int> statf; // 单个证词的各种状态信息
vector<statf> cons; // 这里将存放所有证词的信息

statf tmp;
tmp["player"] = userid; // 证词发布者的 ID
tmp["ensure"] = -1; // 指认的目标ID (-1 代表证词未指认)
tmp["ensure"] = -1; // 证明谁不是罪犯的目标ID (-1 代表证词未证明)
tmp["date"] = 1; // 证词说明的日期 (-1 代表未说明日期)

cons.push_back(tmp);

上方是我存放证词信息的方法(个人感觉还是比较通俗易懂的)

// 整体的语法转换
void grammerAnalysis(string talk)
{
    string name = "";   // 证词发表人名
    int talk_start = 0; // 证词正文起点

    for (int i = 0; i < talk.length(); i++)
    {
        // 识别证词发表人的名字 (到 : 结束)
        if (talk[i] == ':' && talk[i + 1] == ' ')
        {
            talk_start = i + 2; // 取得证词正文起点
            break;
        }
        name += talk[i];
    }

    // 取得发表人 ID号
    int uid = -1;
    for (int i = 0; i < m; i++)
    {
        if (players[i] == name)
        {
            uid = i;
            break;
        }
    }
    if (uid == -1)
    {
        return; //人物不存在,结束后续操作
    }

    string content = "";

    // 取得证词全文
    for (int i = talk_start; i <= talk.length(); i++)
    {
        if (talk[i] != 0)
        {
            content += talk[i];
        }
    }

    map<string, int> tmp;
    tmp["player"] = uid;
    int anay = 0;

    // 识别对自己提供的证词
    // cout << (int)content[content.length() - 1] << endl;
    if (content == "I am guilty.")
    {
        tmp["ensure"] = uid;
        tmp["denial"] = -1;
        tmp["date"] = -1;
        anay = 1;
    }
    else if (content == "I am not guilty.")
    {
        tmp["ensure"] = -1;
        tmp["denial"] = uid;
        tmp["date"] = -1;
        anay = 1;
    }
    else
    {
        if (week.find(content) != week.end())
        {
            tmp["ensure"] = -1;
            tmp["denial"] = -1;
            tmp["date"] = week[content];
            anay = 1;
        }
        else
        {
            // 解析是否指正他人
            int target = -1;
            bool forname = true;
            string anct = "";
            string tnam = "";

            for (int i = 0; i < content.length(); i++)
            {
                if (forname)
                {
                    if (content[i] == ' ')
                    {
                        for (int i = 0; i < m; i++)
                        {
                            if (players[i] == tnam)
                            {
                                target = i;
                                forname = false;
                                break;
                            }
                        }
                    }
                    else
                    {
                        tnam += content[i];
                    }
                }
                else
                {
                    anct += content[i];
                }
            }

            if (target != -1)
            {
                if (anct == "is guilty.")
                {
                    tmp["ensure"] = target;
                    tmp["denial"] = -1;
                    tmp["date"] = -1;
                    anay = 1;
                }
                else if (anct == "is not guilty.")
                {
                    tmp["ensure"] = -1;
                    tmp["denial"] = target;
                    tmp["date"] = -1;
                    anay = 1;
                }
            }
        }
    }

    // 如果为合法证词则将数据存入
    if (anay == 1)
    {
        cons.push_back(tmp);
    }
}

上面是个人的语法解析代码(还可进行优化)

PS:这里的日期信息初始化需要先调用

map<string, int> week; // 日期对应表

// 初始化日期信息
void initData()
{
    week["Today is Monday."] = 1;
    week["Today is Tuesday."] = 2;
    week["Today is Wednesday."] = 3;
    week["Today is Thursday."] = 4;
    week["Today is Friday."] = 5;
    week["Today is Saturday."] = 6;
    week["Today is Sunday."] = 7;
}

这里的语法转换函数我是在每输入一个证词时就对证词处理一次,可以减少循环的使用。

判断结果

为了判断结果,需要使用三层的循环:

  1. 玩家遍历(假设每个人是罪犯)
  2. 日期遍历(周一到周天的日期)
  3. 证词遍历(依次处理每一条证词)

博主在枚举每一天情况处初始化了两个变量:[整数数组]uinfo[布尔类型]error

这两个变量分别存放了用户的信息(未知、诚实、撒谎)和 是否出现冲突

在进入第三次遍历(证词遍历)时,就需要对证词的属性进行判定(指认他人,否认他人,日期声明)

这里我们只需要进行简单的对比就可以知道此人是否撒谎:

// 判断日期是否和今天日期相同
if(talk["date"] == day){}

// 判断指认的人是不是假设的罪犯
if (talk["ensure"] == who){}

// 判断否认的人是不是假设的罪犯
if (talk["denial"] != who){}

// 通过上面三种简单的方法就能判断一个人是否撒谎!

你以为简单的三次判断就结束了?其实还有一个很关键的点被忽略了!

我们现在做的一切都是假设,假设一定会存在不合理!

如果直接给一个人下定义他是否撒谎,那将会大错特错!我们需要检查是否出现了不合理!

给一个案例自己体会一下:

3 1 4
Sam
Jack
Kevin
Sam: Today is Sunday.
Jack: Today is Friday.
Sam: I am guilty.
Kevin: I am not guilty.

如果不检查合理性,当我们来到假设:Jack是罪犯且今天是Sunday时,一个问题就会出现。

Sam说是Sunday[没有问题],但他又说自己是罪犯!(这里就发生冲突了)

你说Sam撒谎了,但Sunday确实没毛病。你说他没撒谎,但他也不是罪犯啊!

解决方法其实很简单:判断是否撒谎后,再和此人之前的信息对比,如果这次撒谎了但上次没有,则说明这次假设本身就有问题,直接把它跳过就行了(这就是 error 变量的用处)

证词矛盾可过滤掉百分之九十的错误假设!另外一种需要限制的就是撒谎人数,当撒谎人数超过案例给的撒谎人数,这条假设也可以直接跳过了。

最后,没有 矛盾和超出人数 就说明这条假设已经成立了!可以确定为罪犯了。

注意事项

本题有一个测试样例如下:

2 2 4
HELLO
GUILTY
HELLO: What is your name?
GUILTY: I am GUILTY.
GUILTY: Are you guilty?
HELLO: I am not guilty.

本样例有两个玩家,且有两个人说谎。

但可以看到 GUILTY 一直在说废话(无效证词),而真正撒谎但只有 HELLO 一人!

经过程序分析,GUILTY 的类型为0(未知),HELLO 则为2(撒谎)

既然不知道 GUILTY 有没有撒谎,且撒谎人数差一个,就可以把不确定的人定义为撒谎的人。

不知道撒谎没,就把他当作撒了谎的人!

特殊情况

本题除了正常输出罪犯的名字外,还有可能输出“Cannot Determine”“Impossible”

  • Cannot Determine: 不止一个人是罪犯,就是在程序依次假设玩家是罪犯时,有多条假设是成立的。
  • Impossible: 没有人可能是罪犯,也就是在程序枚举出所有情况后,没有一种假设是成立的。

为了准确识别这两种可能性,我使用了一个 int 变量 offender 储存确定的罪犯信息。

这个变量默认值为 -1 即代表目前没有任何人可被确定为罪犯。

完整代码

#include <iostream>
#include <algorithm>

#include <string>
#include <map>
#include <vector>

#include <cstdio>

// 题目:  LuoGu P1039 侦探推理
// 难度: 提高+/省选-

using namespace std;

int m, n, p;

string players[21];
string talks[101];

// 解析器数据
map<string, int> week; // 日期对应表
string ansdict[6];     // 回复对应表

typedef map<string, int> statf;
vector<statf> cons;

// 初始化日期信息
void initData()
{
    week["Today is Monday."] = 1;
    week["Today is Tuesday."] = 2;
    week["Today is Wednesday."] = 3;
    week["Today is Thursday."] = 4;
    week["Today is Friday."] = 5;
    week["Today is Saturday."] = 6;
    week["Today is Sunday."] = 7;
}

// 语法解析器
void grammerAnalysis(string talk)
{
    string name = "";   // 证词发表人名
    int talk_start = 0; // 证词正文起点

    for (int i = 0; i < talk.length(); i++)
    {
        // 识别证词发表人的名字 (到 : 结束)
        if (talk[i] == ':' && talk[i + 1] == ' ')
        {
            talk_start = i + 2; // 取得证词正文起点
            break;
        }
        name += talk[i];
    }

    // 取得发表人 ID号
    int uid = -1;
    for (int i = 0; i < m; i++)
    {
        if (players[i] == name)
        {
            uid = i;
            break;
        }
    }
    if (uid == -1)
    {
        return; //人物不存在,结束后续操作
    }

    string content = "";

    // 取得证词全文
    for (int i = talk_start; i <= talk.length(); i++)
    {
        if (talk[i] != 0)
        {
            content += talk[i];
        }
    }

    map<string, int> tmp;
    tmp["player"] = uid;
    int anay = 0;

    // 识别对自己提供的证词
    // cout << (int)content[content.length() - 1] << endl;
    if (content == "I am guilty.")
    {
        tmp["ensure"] = uid;
        tmp["denial"] = -1;
        tmp["date"] = -1;
        anay = 1;
    }
    else if (content == "I am not guilty.")
    {
        tmp["ensure"] = -1;
        tmp["denial"] = uid;
        tmp["date"] = -1;
        anay = 1;
    }
    else
    {
        if (week.find(content) != week.end())
        {
            tmp["ensure"] = -1;
            tmp["denial"] = -1;
            tmp["date"] = week[content];
            anay = 1;
        }
        else
        {
            // 解析是否指正他人
            int target = -1;
            bool forname = true;
            string anct = "";
            string tnam = "";

            for (int i = 0; i < content.length(); i++)
            {
                if (forname)
                {
                    if (content[i] == ' ')
                    {
                        for (int i = 0; i < m; i++)
                        {
                            if (players[i] == tnam)
                            {
                                target = i;
                                forname = false;
                                break;
                            }
                        }
                    }
                    else
                    {
                        tnam += content[i];
                    }
                }
                else
                {
                    anct += content[i];
                }
            }

            if (target != -1)
            {
                if (anct == "is guilty.")
                {
                    tmp["ensure"] = target;
                    tmp["denial"] = -1;
                    tmp["date"] = -1;
                    anay = 1;
                }
                else if (anct == "is not guilty.")
                {
                    tmp["ensure"] = -1;
                    tmp["denial"] = target;
                    tmp["date"] = -1;
                    anay = 1;
                }
            }
        }
    }

    if (anay == 1)
    {
        cons.push_back(tmp);
    }
}

// 结果计算器
void analyzer()
{
    int offender = -1;

    // 枚举出每个人是罪犯的情况
    for (int who = 0; who < m; who++)
    {
        // 枚举每一天的信息
        for (int day = 1; day <= 7; day++)
        {

            int uinfo[21] = {0};
            bool error = false;

            for (int tki = 0; tki < cons.size(); tki++)
            {
                statf talk = cons[tki];
                int sender = talk["player"];

                if (talk["ensure"] == -1 && talk["denial"] == -1)
                {
                    if (talk["date"] == day)
                    {
                        if (uinfo[sender] == 2)
                        {
                            // 出现矛盾,假设失效
                            error = true;
                            break;
                        }
                        uinfo[sender] = 1;
                    }
                    else
                    {
                        if (uinfo[sender] == 1)
                        {
                            // 出现矛盾,假设失效
                            error = true;
                            break;
                        }
                        uinfo[sender] = 2;
                    }
                }
                else if (talk["date"] == -1 && talk["denial"] == -1)
                {
                    if (talk["ensure"] == who)
                    {
                        if (uinfo[sender] == 2)
                        {
                            // 出现矛盾,假设失效
                            error = true;
                            break;
                        }
                        uinfo[sender] = 1;
                    }
                    else
                    {
                        if (uinfo[sender] == 1)
                        {
                            // 出现矛盾,假设失效
                            error = true;
                            break;
                        }
                        uinfo[sender] = 2;
                    }
                }
                else if (talk["date"] == -1 && talk["ensure"] == -1)
                {
                    if (talk["denial"] != who)
                    {
                        if (uinfo[sender] == 2)
                        {
                            // 出现矛盾,假设失效
                            error = true;
                            break;
                        }
                        uinfo[sender] = 1;
                    }
                    else
                    {
                        if (uinfo[sender] == 1)
                        {
                            // 出现矛盾,假设失效
                            error = true;
                            break;
                        }
                        uinfo[sender] = 2;
                    }
                }
            }

            int faker = 0;
            for (int i = 0; i < m; i++)
            {
                if (uinfo[i] == 2)
                {
                    faker++;
                }
            }
            if (faker > n)
            {
                error = true;
            }else if(faker < n){
                for (int i = 0; i < m; i++)
                {

                    if(faker == n){
                        break;
                    }

                    // 如果无法定义玩家信息,可设他为撒谎
                    if(uinfo[i] == 0){
                        uinfo[i] = 2;
                        faker ++;
                    }
                }
                if(faker < n){
                    error = true;
                }
            }

            // cout << "当今天是星期" << day << "且罪犯是" << players[who] << "时: ";
            // for (int i = 0; i < m; i++)
            // {
            //     cout << players[i] << "状态为" << uinfo[i] << " ";
            // }
            // if (error)
            // {
            //     cout << "注意: 假设失效 ";
            // }

            // cout << "总计:" << faker << "个人撒谎" << endl;

            if (!error)
            {
                if (offender == -1 || offender == who)
                {
                    offender = who;
                }
                else
                {
                    cout << "Cannot Determine" << endl;
                    return;
                }
            }
        }
    }

    if (offender == -1)
    {
        cout << "Impossible" << endl;
    }
    else
    {
        cout << players[offender] << endl;
    }
}

int main()
{

    // freopen("P1039.in", "r", stdin);
    // freopen("P1039.out", "w", stdout);

    initData();

    cin >> m >> n >> p;

    for (int i = 0; i < m; ++i)
    {
        cin >> players[i];
    }

    // 提交时需解开
    // char ch = getchar();
    // string eget = "";

    // while (true)
    // {
    //     if (ch == 10)
    //     {
    //         ch = getchar();
    //     }
    //     else
    //     {
    //         eget = ch;
    //         break;
    //     }
    // }

    char ch=getchar();
    while(ch==10)ch=getchar();getchar();


    for (int j = 0; j < p; ++j)
    {
        getline(cin, talks[j]);

        // if (eget != "")
        // {
        //     talks[j] = eget + talks[j];
        //     eget = "";
        // }
        talks[j].erase(talks[j].end() - 1);
        grammerAnalysis(talks[j]); // 解析语句到分析数组
    }

    analyzer();

    return 0;
}
Last modification:September 2nd, 2020 at 06:55 pm
如果觉得我的文章对你有用,请随意赞赏