规则/ruler 题解

题目分析

难度：

\text{\color{#81C784}普及+/提高}

。
算法：图论、图遍历、DFS 深度优先搜索。

题目思路

声明

下文中所提到的“不确定”合法变量bhf是摆设，忘删了。

第一层

想到了从

q

开始观察，然后不断指向点

q

的后继（指指向），设点

q

为

a

点，点

q

的后继为

b

点，点

q

说点

q

的后继是

y

的。
则：

$a$ 为正确：
- $y=0$ 则 $b$ 为正确。
- $y=1$ 则 $b$ 为错误。
$b$ 为错误：
- $y=1$ 则 $b$ 为正确。
- $y=0$ 则 $b$ 为错误。

最后记录正确、错误的编号。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
vector<int>p[N];
int a[N];
int nxt[N];
int n,q,flag=0;
int fac[N],fwa[N],fbh[N],fbz[N];
//记录AC,WA，不确定合法，不确定正误
int vis[N];
int qq;
int main(){
	cin>>n>>q;
	qq=q;
	for(int i=1;i<=n;i++){
		int u=i,v;
		cin>>v>>a[i];
		nxt[u]=v;
		p[v].push_back(u);
	}
	fac[q]=1;
	flag=a[q];
	q=nxt[q];
	while(1){
		if(flag==0){//dui 
			if(fac[q]==1)break;
			else if(fwa[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fac[q]=1;flag=a[q];q=nxt[q];}
		}
		else{//bu dui
			if(fwa[q]==1)break;
			else if(fac[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fwa[q]=1;flag=(a[q]==0);q=nxt[q];}
		}
	}
	for(int i=1;i<=n;i++)if(fac[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fwa[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbz[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbh[i]==1)cout<<i<<" ";
	cout<<endl;
	return 0; 
}

测试情况

\text{\color{#81C784}AC in 1,2}

。

\text{\color{red}WA}

12

分。

第二层

想到点

a

是对的，那么点

b

说点

a

是正确所以点

b

正确。同理，则：

$a$ $a$ 正确：
- $b$ 说 $a$ 正确，则 $b$ 正确。
- $b$ 说 $a$ 错误，则 $b$ 错误。
$a$ $a$ 错误：
- $b$ 说 $a$ 正确，则 $b$ 错误。
- $b$ 说 $a$ 错误，则 $b$ 正确。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
vector<int>p[N];
int a[N];
int nxt[N];
int n,q,flag=0;
int fac[N],fwa[N],fbh[N],fbz[N];
int vis[N];
int qq;
bool check(int q){
	return fac[q]==1||fwa[q]==1||fbh[q]==1||fbz[q]==1;
}
void dfs(int u){//yi zhi he fa xing fu gai
//cout<<u<<" ";
	vis[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]==1)continue;
		if(a[v]==0){//v say u if AC
			if(fac[u]==1){fac[v]=1;}
			if(fwa[u]==1){fwa[v]=1;}
		}
		else{
			if(fac[u]==1){fwa[v]=1;}
			if(fwa[u]==1){fac[v]=1;}
		}
		dfs(v);
	}
}
int main(){
	cin>>n>>q;
	qq=q;
	for(int i=1;i<=n;i++){
		int u=i,v;
		cin>>v>>a[i];
		nxt[u]=v;
		p[v].push_back(u);
	}
	fac[q]=1;
	flag=a[q];
	q=nxt[q];
	while(1){
		if(flag==0){//dui 
			if(fac[q]==1)break;
			else if(fwa[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fac[q]=1;flag=a[q];q=nxt[q];}
		}
		else{//bu dui
			if(fwa[q]==1)break;
			else if(fac[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fwa[q]=1;flag=(a[q]==0);q=nxt[q];}
		}
	}
	dfs(qq);
	for(int i=1;i<=n;i++)if(fac[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fwa[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbz[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbh[i]==1)cout<<i<<" ";
	cout<<endl;
	return 0; 
}

测试情况

\text{\color{#81C784}AC in 1,2,3,7,8}

。

\text{\color{red}WA}

30

分。

第三四层

第三层

如果有 $a$ $a$ 说 $a$ $a$ 是正确的。
- 那么假设 $a$ 正确， $a$ 说 $a$ 正确，则 $a$ 正确。
- 假设 $a$ 是错误的， $a$ 说 $a$ 正确，则 $a$ 是错误的。
- 则不确定正不正确。
如果有 $a$ $a$ 说 $a$ $a$ 是错误的。
- 那么假设 $a$ 正确， $a$ 说 $a$ 错误，则 $a$ 错误，不合法。
- 那么假设 $a$ 错误， $a$ 说 $a$ 错误，则 $a$ 正确，不合法。
- 则不合法。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
vector<int>p[N];
int a[N];
int nxt[N];
int n,q,flag=0;
int fac[N],fwa[N],fbh[N],fbz[N];
//zheng,   cuo,
//  bu que ding zheng cuo,he fa
int vis[N];
int qq;
bool check(int q){
	return fac[q]==1||fwa[q]==1||fbh[q]==1||fbz[q]==1;
}
void dfs(int u){//yi zhi he fa xing fu gai
//cout<<u<<" ";
	vis[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]==1)continue;
		if(a[v]==0){//v say u if AC
			if(fac[u]==1){fac[v]=1;}
			if(fwa[u]==1){fwa[v]=1;}
		}
		else{
			if(fac[u]==1){fwa[v]=1;}
			if(fwa[u]==1){fac[v]=1;}
		}
		dfs(v);
	}
}
int main(){
	cin>>n>>q;
	qq=q;
	for(int i=1;i<=n;i++){
		int u=i,v;
		cin>>v>>a[i];
		nxt[u]=v;
		p[v].push_back(u);
	}
	fac[q]=1;
	flag=a[q];
	q=nxt[q];
	//mu qian:q he fa de zhang tai wei flag 
	while(1){
		if(flag==0){//dui 
			if(fac[q]==1)break;
			else if(fwa[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fac[q]=1;flag=a[q];q=nxt[q];}
		}
		else{//bu dui
			if(fwa[q]==1)break;
			else if(fac[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fwa[q]=1;flag=(a[q]==0);q=nxt[q];}
		}
	}
	dfs(qq);// yi zhi he fa xing fu gai
	//bu que ding he fa
	for(int i=1;i<=n;i++){
		if(nxt[i]==i){
			if(a[i]==1){
				cout<<"NO!"<<endl;return 0;
			}
			else{
				if(!check(i)){
					fbz[i]=1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)if(fac[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fwa[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbz[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbh[i]==1)cout<<i<<" ";
	cout<<endl;
	return 0; 
}

测试情况

\text{\color{#81C784}AC in 1,2,3,4,6,7,8}

。

\text{\color{red}WA}

42

分。

第四层

既然想到了不确定

a

正不正确，那么说

a

正确或错误的

b

也不知道正确或错误。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
vector<int>p[N];
int a[N];
int nxt[N];
int n,q,flag=0;
int fac[N],fwa[N],fbh[N],fbz[N];
//zheng,   cuo,
//  bu que ding zheng cuo,he fa
int vis[N];
int qq;
bool check(int q){
	return fac[q]==1||fwa[q]==1||fbh[q]==1||fbz[q]==1;
}
void dfs(int u){//yi zhi he fa xing fu gai
//cout<<u<<" ";
	vis[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]==1)continue;
		if(a[v]==0){//v say u if AC
			if(fac[u]==1){fac[v]=1;}
			if(fwa[u]==1){fwa[v]=1;}
		}
		else{
			if(fac[u]==1){fwa[v]=1;}
			if(fwa[u]==1){fac[v]=1;}
		}
		dfs(v);
	}
}
void dfshf(int u){
	vis[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]==1)continue;
		fbz[v]=1;
		dfs(v);
	}
}

int main(){
	cin>>n>>q;
	qq=q;
	for(int i=1;i<=n;i++){
		int u=i,v;
		cin>>v>>a[i];
		nxt[u]=v;
		p[v].push_back(u);
	}
	fac[q]=1;
	flag=a[q];
	q=nxt[q];
	//mu qian:q he fa de zhang tai wei flag 
	while(1){
		if(flag==0){//dui 
			if(fac[q]==1)break;
			else if(fwa[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fac[q]=1;flag=a[q];q=nxt[q];}
		}
		else{//bu dui
			if(fwa[q]==1)break;
			else if(fac[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fwa[q]=1;flag=(a[q]==0);q=nxt[q];}
		}
	}
	dfs(qq);// yi zhi he fa xing fu gai
	//bu que ding he fa
	for(int i=1;i<=n;i++){
		if(nxt[i]==i){
			if(a[i]==1){
				cout<<"NO!"<<endl;return 0;
			}
			else{
				if(!check(i)){
					fbz[i]=1;
					dfshf(i);
				}
			}
		}
	}
	
	for(int i=1;i<=n;i++)if(fac[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fwa[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbz[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbh[i]==1)cout<<i<<" ";
	cout<<endl;
	return 0; 
}

测试信息

\text{\color{#81C784}AC in 1,2,3,4,5,7,8,9}

。

\text{\color{red}WA}

48

分。

在点 $4$ 后面插入了一个点。

第五六层

第五层

剩下所有的点都是环状或者指向环状。

对于环状的部分（只考虑 $2,3$ ），举个例子：

2

说

3

是正确，

3

说

2

是正确。
那么：

假设 $2$ 正确，且所有指向都说正确，经推导， $2,3$ 都正确。
假设 $2$ 错误，且所有指向都说正确，经推导， $2,3$ 都错误。
假设 $2$ 正确，且所有指向都说错误，经推导， $2$ 都正确 $3$ 错误。
假设 $2$ 错误，且所有指向都说错误，经推导， $2$ 错误 $3$ 正确。
如果 $2$ 指 $3$ 与 $3$ 指 $2$ 其中有一个说正确或错误和另一个不一样（ $2$ 说 $3$ 错， $3$ 说 $2$ 对），则不合法。

将环增大（

1

->

2

2

->

3

3

->

4

...

n

->

1

）。

可以发现：若其中说正确的个数和说错误的个数有一个不是偶数，则不合法，否则不确定对错。

我们可以通过标记 vis 来实现，如果发现指向其的点已经被标记过，则算奇偶个数。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
vector<int>p[N];
int a[N];
int nxt[N];
int n,q,flag=0;
int fac[N],fwa[N],fbh[N],fbz[N];
//zheng,   cuo,
//  bu que ding zheng cuo,he fa
int vis[N];
int qq;
bool check(int q){
	return fac[q]==1||fwa[q]==1||fbh[q]==1||fbz[q]==1;
}
void dfs(int u){//yi zhi he fa xing fu gai
//cout<<u<<" ";
	vis[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]==1)continue;
		if(a[v]==0){//v say u if AC
			if(fac[u]==1){fac[v]=1;}
			if(fwa[u]==1){fwa[v]=1;}
		}
		else{
			if(fac[u]==1){fwa[v]=1;}
			if(fwa[u]==1){fac[v]=1;}
		}
		dfs(v);
	}
}
void dfshf(int u){
	vis[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]==1)continue;
		fbz[v]=1;
		dfs(v);
	}
}
void dfszchf(int u,int ji,int ou){//u,ji shu ge shu,ou shu ge shu
	vis[u]=1;
	fbz[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]==1){
			//huan
			if(a[v]==0){
				if((ou+1)%2==0&&(ji)%2==0){
					fbz[v]=1;continue;
				}
				else{
					cout<<"NO!"<<endl;
					exit(0);
				}
			}
			else{
				if((ji+1)%2==0&&ou%2==0){
					fbz[v]=1;continue;
				}
				else{
					cout<<"NO!"<<endl;
					exit(0);
				}
			}
		}
		if(a[v]==0){
			dfszchf(v,ji,ou+1);
		} 
		else{
			dfszchf(v,ji+1,ou);
		}
	}
}
int main(){
	cin>>n>>q;
	qq=q;
	for(int i=1;i<=n;i++){
		int u=i,v;
		cin>>v>>a[i];
		nxt[u]=v;
		p[v].push_back(u);
	}
	fac[q]=1;
	flag=a[q];
	q=nxt[q];
	//mu qian:q he fa de zhang tai wei flag 
	while(1){
		if(flag==0){//dui 
			if(fac[q]==1)break;
			else if(fwa[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fac[q]=1;flag=a[q];q=nxt[q];}
		}
		else{//bu dui
			if(fwa[q]==1)break;
			else if(fac[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fwa[q]=1;flag=(a[q]==0);q=nxt[q];}
		}
	}
	dfs(qq);// yi zhi he fa xing fu gai
	//bu que ding he fa
	for(int i=1;i<=n;i++){
		if(nxt[i]==i){
			if(a[i]==1){
				cout<<"NO!"<<endl;return 0;
			}
			else{
				if(!check(i)){
					fbz[i]=1;
					dfshf(i);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfszchf(i,0,0);//dfs zheng cuo he fa
		}
	}
	
	for(int i=1;i<=n;i++)if(fac[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fwa[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbz[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbh[i]==1)cout<<i<<" ";
	cout<<endl;
	return 0; 
}

测试信息

\text{\color{#81C784}AC in all}

。

\text{\color{#81C784}AC}

80

分。

第六层

可以发现代码是从小的编号开始便利的，如下图：

CPP

遍历

5

时，由于

2

已经被遍历过了且说正确的个数为

1

，是奇数，故会输出 NO!。

但实际是，

4,5

不确定对错，

2,3

也不知道对错。

改进的方法就是遍历每个点时，增加形式参数

X

，代表目前块的名字是

X

（不用考虑其他

vis

赋值是

1

会产生冲突，因为其他产生冲突的点都和该快不连通），然后碰见

vis

被标记时判断是否是第

X

块在行动。

将该点设为点

16

，分值为

10

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
vector<int>p[N];
int a[N];
int nxt[N];
int n,q,flag=0;
int fac[N],fwa[N],fbh[N],fbz[N];
//zheng,   cuo,
//  bu que ding zheng cuo,he fa
int vis[N];
int qq;
bool check(int q){
	return fac[q]==1||fwa[q]==1||fbh[q]==1||fbz[q]==1;
}
void dfs(int u){//yi zhi he fa xing fu gai
//cout<<u<<" ";
	vis[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]==1)continue;
		if(a[v]==0){//v say u if AC
			if(fac[u]==1){fac[v]=1;}
			if(fwa[u]==1){fwa[v]=1;}
		}
		else{
			if(fac[u]==1){fwa[v]=1;}
			if(fwa[u]==1){fac[v]=1;}
		}
		dfs(v);
	}
}
void dfshf(int u){
	vis[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]==1)continue;
		fbz[v]=1;
		dfs(v);
	}
}
void dfszchf(int u,int ji,int ou,int X){//u,ji shu ge shu,ou shu ge shu
	vis[u]=X;
	fbz[u]=1;
	for(int i=0;i<p[u].size();i++){
		int v=p[u][i];
		if(vis[v]!=0&&vis[v]!=X)continue;
		if(vis[v]==X){
			//huan
			if(a[v]==0){
				if((ou+1)%2==0&&(ji)%2==0){
					fbz[v]=1;continue;
				}
				else{
					cout<<"NO!"<<endl;
					exit(0);
				}
			}
			else{
				if((ji+1)%2==0&&ou%2==0){
					fbz[v]=1;continue;
				}
				else{
					cout<<"NO!"<<endl;
					exit(0);
				}
			}
		}
		if(a[v]==0){
			dfszchf(v,ji,ou+1,X);
		} 
		else{
			dfszchf(v,ji+1,ou,X);
		}
	}
}
int main(){
	cin>>n>>q;
	qq=q;
	for(int i=1;i<=n;i++){
		int u=i,v;
		cin>>v>>a[i];
		nxt[u]=v;
		p[v].push_back(u);
	}
	fac[q]=1;
	flag=a[q];
	q=nxt[q];
	//mu qian:q he fa de zhang tai wei flag 
	while(1){
		if(flag==0){//dui 
			if(fac[q]==1)break;
			else if(fwa[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fac[q]=1;flag=a[q];q=nxt[q];}
		}
		else{//bu dui
			if(fwa[q]==1)break;
			else if(fac[q]==1){cout<<"NO!"<<endl;return 0;}
			else{fwa[q]=1;flag=(a[q]==0);q=nxt[q];}
		}
	}
	dfs(qq);// yi zhi he fa xing fu gai
	//bu que ding he fa
	for(int i=1;i<=n;i++){
		if(nxt[i]==i){
			if(a[i]==1){
				cout<<"NO!"<<endl;return 0;
			}
			else{
				if(!check(i)){
					fbz[i]=1;
					dfshf(i);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfszchf(i,0,0,i);//dfs zheng cuo he fa
		}
	}
	
	for(int i=1;i<=n;i++)if(fac[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fwa[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbz[i]==1)cout<<i<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)if(fbh[i]==1)cout<<i<<" ";
	cout<<endl;
	return 0; 
}

测试信息

\text{\color{#81C784}AC in all}

\text{\color{#81C784}AC}

90

分

可以发现

n

的范围太小了，固设置

3

个

n=10^5

的数据。

经出题人（AI_god）本人考虑，若

17,18,19

均

AC

则按前

16

个点正常计分，否则按前

16

个点的总分除以

2

再加上

17,18,19

对的点个数

\times 20

。

文章操作

题目分析

题目思路

第一层

第二层

第三四层

第五六层

相关推荐

评论

规则/ruler 题解