首页 > 其他分享 >P1039[NOIP2003提高组]侦探推理

P1039[NOIP2003提高组]侦探推理

时间:2024-07-10 21:31:15浏览次数:4  
标签:P1039 name NOIP2003 int guilty bh 侦探 && lx

暂时未完成qwq

[NOIP2003 提高组] 侦探推理

(这道题思路很简单,但是细节一大堆qwq,调吐了QAQ

这个题一共就20个人,星期一共就有7种可能,100句证词,所以可以直接暴力枚举,看一看假设第 $i$ 个人是罪犯(guilty),今天是星期 $j$ ,那么一共有几个人说了谎话。

然后就好了awa…………
了吗……

这道题的难点其实一直都不是思路,因为思路十分的简单,这道题最恶心的地方是它的细节QAQ

下面我来分别说一下它的啸细节:

part1:输入部分:

首先是输入,这是整道题最恶心的地方,一不小心就会出一些及其难调的BUG。

虽然说白了就是依托答辩分讨

输入一行,然后还要让程序弄明白输入的意思,就是要判断它到底是哪一种证词(一共5种)。然后因为它是字符串,所以总是会爆一些奇奇怪怪的错误qwq

然后我这里处理的方式是分为5种分别判断(虽然说白了就3种:说某个人是,某个人不是,今天是星期几),判断的方法就是让除了 $ “XXX”$ 以外的就直接字符匹配。

数组定义:

bool kk[25];//这个一会说是怎么回事qwq,这是另外一个坑
int n,m,p,num,bh,nnn,sl;//基本变量

string s,ls_name,ls_p,day;

//用于字符匹配
string duib[13]={"","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday",
"I am guilty.",
"I am not guilty.",
"is guilty.",
"is not guilty.",
"Today is "};

//用于映射
map<string,int>name;
map<int,string>name_out;
map<string,int>dd;
map<int,bool>zy;

//who:谁说的
//bh:1/2/3 说某个人是罪犯/说某个人不是罪犯/说今天是星期几
struct node{
	int who,bh,name,today;
}q[105];

main函数内:

	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)	cin>>s,name[s]=i,name_out[i]=s;//输入名字,然后把名字映射成编号
	for(int i=1;i<=7;i++)	dd[duib[i]]=i;//把日期映射成编号
	for(int i=1;i<=p;i++)
	{
		s=read();
		get_name(s);
		get_p(s);
		nnn++,q[nnn].who=name[ls_name],q[nnn].bh=0;
		if(pd(1,ls_p))		q[nnn].bh=1,q[nnn].name=name[ls_name];
		else if(pd(2,ls_p))	q[nnn].bh=2,q[nnn].name=name[ls_name];
		else if(pd(3,ls_p))	q[nnn].bh=1,q[nnn].name=name[ls_name];
		else if(pd(4,ls_p))	q[nnn].bh=2,q[nnn].name=name[ls_name];
		else if(pd(5,ls_p))	q[nnn].bh=3,q[nnn].today=dd[day];
		if(!q[nnn].bh)	nnn--;
		else	kk[q[nnn].who]=1;
	}

……

…………

…………

……………………

……

………………

啊吧啊吧啊吧啊吧……

最后,完整代码:

#include<bits/stdc++.h>
using namespace std;

string read()
{
	string s="";
	char g=getchar();
	while(!((g>='a'&&g<='z')||(g>='A'&&g<='Z')))	g=getchar();
	while((g>='a'&&g<='z')||(g>='A'&&g<='Z')||(g==' ')||(g==':')||(g=='.'))
	{
		s+=g;
		g=getchar();
	}
	return s;
}

bool kk[25];
int n,m,p,num,bh,nnn,sl;

string s,ls_name,ls_p,day;

string duib[13]={"","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday",
"I am guilty.",//8
"I am not guilty.",//9
"is guilty.",//10
"is not guilty.",//11
"Today is "};//12

map<string,int>name;
map<string,int>dd;
map<int,string>name_out;
map<int,bool>zy;

struct node{
	int who,bh,name,today;
}q[105];

bool pd(int lx,string s)
{
	if(lx==1||lx==2)	return ((bool)(s==duib[lx+7]));
	else if(lx==3||lx==4)
	{
		int i=0;	ls_name="";
		while(s[i]!=' '&&i<s.length())	ls_name+=s[i],i++;
		if((!name.count(ls_name))||
			 duib[lx+7].length()+ls_name.length()+1!=s.length())
			return 0;
		bool kk=1;
		for(i=0;i<duib[lx+7].length()&&i+ls_name.length()+1<s.length();i++)
			kk&=((bool)(s[i+ls_name.length()+1]==duib[lx+7][i]));
		return kk;
	}
	else
	{
		bool kk=1;
		for(int i=0;i<duib[12].length();i++)
			kk&=((bool)(s[i]==duib[12][i]));
		if(!kk)	return kk;
		day="";
		for(int i=duib[12].length();i<s.length()-1;i++)	day+=s[i];
		return 1;
	}
}

void get_name(string s){ls_name="";for(int i=0;i<s.length();i++){if(s[i]==':')	break;ls_name+=s[i];}}
void get_p(string s){ls_p="";for(int i=ls_name.length()+2;i<s.length();i++)	ls_p+=s[i];}

int main()
{
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)	cin>>s,name[s]=i,name_out[i]=s;
	for(int i=1;i<=7;i++)	dd[duib[i]]=i;
	for(int i=1;i<=p;i++)
	{
		s=read();
		get_name(s);
		get_p(s);
		nnn++,q[nnn].who=name[ls_name],q[nnn].bh=0;
		if(pd(1,ls_p))		q[nnn].bh=1,q[nnn].name=name[ls_name];
		else if(pd(2,ls_p))	q[nnn].bh=2,q[nnn].name=name[ls_name];
		else if(pd(3,ls_p))	q[nnn].bh=1,q[nnn].name=name[ls_name];
		else if(pd(4,ls_p))	q[nnn].bh=2,q[nnn].name=name[ls_name];
		else if(pd(5,ls_p))	q[nnn].bh=3,q[nnn].today=dd[day];
		if(!q[nnn].bh)	nnn--;
		else	kk[q[nnn].who]=1;
	}
	for(int i=1;i<=n;i++)
		if(kk[i]==0)
			sl++;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=7;j++)
		{
			zy.clear();
			int nn=0,ck=1;
			for(int k=1;k<=nnn;k++)
			{
				if(q[k].bh==1)
				{
					if(q[k].name==i)
					{
						if(!zy.count(q[k].who))	zy[q[k].who]=1;
						else if(zy.count(q[k].who)&&zy[q[k].who]==0)
						{
							ck=0;
							break;
						}
					}
					else
					{
						if(!zy.count(q[k].who))	zy[q[k].who]=0,nn++;
						else if(zy.count(q[k].who)&&zy[q[k].who]==1)
						{
							ck=0;
							break;
						}
					}
				}
				else if(q[k].bh==2)
				{
					if(q[k].name!=i)
					{
						if(!zy.count(q[k].who))	zy[q[k].who]=1;
						else if(zy.count(q[k].who)&&zy[q[k].who]==0)
						{
							ck=0;
							break;
						}
					}
					else
					{
						if(!zy.count(q[k].who))	zy[q[k].who]=0,nn++;
						else if(zy.count(q[k].who)&&zy[q[k].who]==1)
						{
							ck=0;
							break;
						}
					}
				}
				else
				{
					if(q[k].today==j)
					{
						if(!zy.count(q[k].who))	zy[q[k].who]=1;
						else if(zy.count(q[k].who)&&zy[q[k].who]==0)
						{
							ck=0;
							break;
						}
					}
					else
					{
						if(!zy.count(q[k].who))	zy[q[k].who]=0,nn++;
						else if(zy.count(q[k].who)&&zy[q[k].who]==1)
						{
							ck=0;
							break;
						}
					}
				}
			}
			if(nn<=m&&nn+sl>=m&&ck)
			{
				num++;
				bh=i;
				break; 
			}
		}
	}
	if(num==1)	cout<<name_out[bh]<<'\n';
	else if(num==0)	cout<<"Impossible\n";
	else if(num>1)	cout<<"Cannot Determine\n";
	return 0;
}

标签:P1039,name,NOIP2003,int,guilty,bh,侦探,&&,lx
From: https://www.cnblogs.com/Jack-YT/p/18295058

相关文章

  • P1038 [NOIP2003 提高组] 神经网络
    讲解区下面分几部分再详解一下这道题1.读入+处理注意,因为这是一个拓扑的题所以我们拓展点的时候要借助队列那如何发挥队列的用处呢?由题意,只有最初状态为1的点才会往后传递我们完全可以在读入的时候就把上述点push进队列中楼上大佬也证明过了,阈值u(我的代码中是x)可以一开......
  • [夏夜专属]AU剪辑音乐侦探
    1.打开首先拖动录制好的音频到AU打开接着创建一个多轨文件拖动音频到多轨上只要出现这个弹窗点击确认即可把音频移到后面,插入开头音乐也可以用拖的方式拖进去不能让音频交叉右键拆分将录制音频分为5个部分,“开头”,“第一首歌”,”第二首歌“,”第三首歌“,”结尾“......
  • [NOIP2003 普及组] 乒乓球
    洛谷P1042[NOIP2003普及组]乒乓球题目背景国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革,以推动乒乓球运动在全球的普及。其中 1111 分制改革引起了很大的争议,有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位,他退役之后走上了乒乓球研究工作......
  • #[NOIP2003 普及组] 乒乓球
    传送锚点:https://www.luogu.com.cn/problem/P1042题目背景国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革,以推动乒乓球运动在全球的普及。其中\(11\)分制改革引起了很大的争议,有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位,他退役之后走上了乒乓......
  • CSP历年复赛题-P1044 [NOIP2003 普及组] 栈
    原题链接:https://www.luogu.com.cn/problem/P1044题意解读:一组数入栈、出栈的方案数,如果了解卡特兰数,此题可以秒杀;如果不了解,也可以通过递归或者递推来解决;最次,可以通过DFS暴搜出方案数,当然对于n个数,一共有n次入栈、n次出栈,一共2n次,每次要么入栈要么出栈,总搜索次数在22n规模,n最......
  • CSP历年复赛题-P1045 [NOIP2003 普及组] 麦森数
    原题链接:https://www.luogu.com.cn/problem/P1045题意解读:要计算2p-1的位数和最后500位,实际上只需要计算2p,两者位数一致,前者比后者个位减1即可,且个位肯定不会是0,比较容易处理。解题思路:如果直接采用高精度乘法计算2p,p最大3.1*106,高精度所用数组最长大概9*105,一共最多计算3.......
  • CSP历年复赛题-P1043 [NOIP2003 普及组] 数字游戏
    原题链接:https://www.luogu.com.cn/problem/P1043题意解读:将n个环形数分成任意m组,组内求和再%10、负数转正,组间相乘,求所有分组方案中得到结果的最小值和最大值。解题思路:比赛题的首要目的是上分!此题一看就是DP,但是苦苦思索了半天,想不清楚状态表示,那么可以换换策略,先暴力得分再......
  • CSP历年复赛题-P1042 [NOIP2003 普及组] 乒乓球
    原题链接:https://www.luogu.com.cn/problem/P1042题意解读:分别针对11分制和21分制,输出每局比分。只需要判断一局的结束条件:得分高者如果达到11或者21,且比分间隔大于等于2分,则表示一局结束,可开始下一局,用模拟法即可解决。100分代码:#include<bits/stdc++.h>usingnamespaces......
  • P1044 [NOIP2003 普及组] 栈
    链接:https://www.luogu.com.cn/problem/P1044两种很好的思路:代码:#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<string.h>#include<iomanip>#incl......
  • P1040 [NOIP2003 提高组] 加分二叉树
    原题链接题解计算分数是搜索存储前缀注意细节code#include<bits/stdc++.h>usingnamespacestd;#definelllonglongllsco[35][35]={0};stringpre[35][35];lla[35]={0};queue<ll>q;inlinevoidread(ll&x){x=0;llflag=1;charc=getch......