暴力DFS求调
  • 板块P6691 选择题
  • 楼主Crab_Tang
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/20 16:27
  • 上次更新2024/7/20 17:26:56
查看原帖
暴力DFS求调
1021365
Crab_Tang楼主2024/7/20 16:27
#include<bits/stdc++.h>
using namespace std;
const int N=10+10,mod=998244353;
int n,ans,minp,maxp;
bool p[N];
int vis[N];//p[i]代表问题i的真假,vis[i]代表问题i的p是否被赋值
int pq[N];//pq[i]代表i个问题的内容1
bool qp[N];//qp[i]代表i个问题的内容2
void dfs(int x,int sum){
	//问到第x个问题,对了的个数是sum
	/*
	puts("\n---");
	printf("x:%d sum:%d ans:%d max:%d min:%d\n",x,sum,ans,maxp,minp);
	for(int i=1;i<=n;++i)
		printf("vis[i]:%d,p[i]:%d\n",vis[i],p[i]?1:0);
	puts("---\n");
	*/
	if(vis[x]){
		++vis[pq[x]];
		p[pq[x]]=((p[x])?(qp[x]):(!qp[x]));
		dfs(x+1,sum+p[x]); 
		--vis[pq[x]];
		return ;
	}
	if(x==n+1){
		++ans;
		minp=min(minp,sum);
		maxp=max(maxp,sum);
		return ;
	}
	if(vis[pq[x]]==0||p[pq[x]]!=qp[x]){
		++vis[x],++vis[pq[x]];
		p[pq[x]]=!qp[x];
		dfs(x+1,sum);//认为错 
		--vis[x],--vis[pq[x]];
	}
	if(vis[pq[x]]==0||p[pq[x]]==qp[x]){
		++vis[x],++vis[pq[x]];
		p[x]=1;
		p[pq[x]]=qp[x];
		dfs(x+1,sum+1);//认为对
		--vis[x],--vis[pq[x]];
	}
	return ;
}
int main(){
	int x,y;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d %d",&x,&y);
		pq[i]=x;
		qp[i]=y;
	}
	minp=n,maxp=0;
	dfs(1,0);
	if(ans==0)
		printf("No answer\n");
	else
		printf("%d %d %d",ans,maxp,minp);
	return 0;
}

第二个样例废了

2024/7/20 16:27
加载中...