求助NOIPT2的前两个点
  • 板块学术版
  • 楼主lishuhang001
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/21 21:20
  • 上次更新2023/11/22 17:34:09
查看原帖
求助NOIPT2的前两个点
546335
lishuhang001楼主2023/11/21 21:20

写T2前两个点用的搜索,两个样例过了,但是前两个点在有的平台上过了,在洛谷和一些平台上挂掉了,不是很理解,求指错

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int c,t,n,m;
int chuzhi[1000010];//初值 
int houzhi[1000010];//操作过的值 
struct jilu{
	char v;
	int t1,t2;
}caozuo[100010];
int ans=100000000; 
bool checkdd();//判断执行前后是否相等 
int youU[100010];//标记是否有U 
void doit();//执行操作 
void sssearch(int numU,int sl);//搜索,numU表示U的数量,sl表示正在搜索的长度 
//T=1,F=-1,U=0
int main()
{
	//freopen("tribool.in","r",stdin);
	//freopen("tribool.out","w",stdout);
	scanf("%d%d",&c,&t);//测试点编号和组数 
	if (c!=3&&c!=4)//特殊点 
	for (int i=1;i<=t;i++)//t次询问 
	{
		memset(caozuo,0,sizeof(caozuo));
		//memset(houzhi,0,sizeof(houzhi));
		scanf("%d%d",&n,&m);//n是长度,m是次数 
		ans=100000000;
		for (int j=1;j<=m;j++)//m个语句
		{
			getchar();//读取换行符
			scanf("%c",&caozuo[j].v);//读取字符
			if (caozuo[j].v=='T'||caozuo[j].v=='F'||caozuo[j].v=='U')
			{
				scanf("%d",&caozuo[j].t1);
				
			} 
			else scanf("%d%d",&caozuo[j].t1,&caozuo[j].t2);
		} 
		sssearch(0,1);//暴力搜索 
		printf("%d\n",ans);
	}
	else//只要看最后又多少个U就行了 
	{
		for (int i=1;i<=t;i++)//t次询问 
		{
			ans=0;
			scanf("%d%d",&n,&m);//n是长度,m是次数
			for (int i=1;i<=n;i++)
				youU[i]=0;
			for (int j=1;j<=m;j++)//m个语句
			{
				getchar();//读取换行符
				char tmpppppp;
				scanf("%c",&tmpppppp);//读取字符
				int tmppint;
				scanf("%d",&tmppint);
				if (tmpppppp=='U')
					youU[tmppint]=1000;
				else youU[tmppint]=0;
			} 
			for (int i=1;i<=n;i++)
				if (youU[i]==1000)
					
					{
						ans++;
					}
			printf("%d\n",ans);
		}
	}
	return 0;
}
void sssearch(int numU,int sl)//暴力搜索 
{
	if (ans==0)
		return;//有最佳答案就停止搜索 
	if (numU>=ans)//已经有比它少的就不搜了 
		return;
	if (sl==n+1)//初值搜索完了
	{
		doit();//执行操作 
		if (checkdd()==true)//相同
		{
			ans=ans<numU?ans:numU;//找更小答案 
		} 
		return;//结束本次搜索 
	} 
	for (int i=-1;i<=1;i++)//三种:-1,0,1 
	{
		if (ans==0)
			return;//有最佳答案就停止搜索 
		if (i==-1)//值定为F
		{
			chuzhi[sl]=-1;//值定为F
			sssearch(numU,sl+1);//继续搜索 
		}
		if (i==1)//值定为T
		{
			chuzhi[sl]=1;//值定为T
			sssearch(numU,sl+1);//继续搜索 
		}
		if (i==0)//值定为U
		{
			chuzhi[sl]=0; 
			sssearch(numU+1,sl+1);
		}
	}
}
void doit()//执行操作
{
	for (int i=1;i<=n;i++)
		houzhi[i]=chuzhi[i];
	for (int i=1;i<=m;i++)
	{
		if (caozuo[i].v=='T')
				houzhi[caozuo[i].t1]=1;	
			else if (caozuo[i].v=='F')
				houzhi[caozuo[i].t1]=-1;
			else if (caozuo[i].v=='U')
				houzhi[caozuo[i].t1]=0;

		else if (caozuo[i].v=='+')
		{
			houzhi[caozuo[i].t1]=chuzhi[caozuo[i].t2];
		}
		else if (caozuo[i].v=='-')
		{
			houzhi[caozuo[i].t1]=0-chuzhi[caozuo[i].t2];
		}
	}
} 
bool checkdd()
{
	
	for (int i=1;i<=n;i++)
	{
		if (chuzhi[i]!=houzhi[i])
			return false;
	}
	return true;
}
2023/11/21 21:20
加载中...