规则/ruler 题解

· · 休闲·娱乐

题目分析

难度：\text{\color{#81C784}普及+/提高}。
算法：图论、图遍历、DFS 深度优先搜索。

题目思路

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

第一层

::::success[第一层] 想到了从 q 开始观察，然后不断指向点 q 的后继（指指向），设点 q 为 a 点，点 q 的后继为 b 点，点 q 说点 q 的后继是 y 的。
则：

最后记录正确、错误的编号。 ::::success[代码]

#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; 
}

::::success[测试情况]

$\text{\color{red}WA}$ $12$ 分。 ![](https://cdn.luogu.com.cn/upload/image_hosting/pkg4a92a.png) :::: #### 第二层 ::::success[第二层] 想到点 $a$ 是对的，那么点 $b$ 说点 $a$ 是正确所以点 $b$ 正确。同理，则： - $a$ 正确： - $b$ 说 $a$ 正确，则 $b$ 正确。 - $b$ 说 $a$ 错误，则 $b$ 错误。 - $a$ 错误： - $b$ 说 $a$ 正确，则 $b$ 错误。 - $b$ 说 $a$ 错误，则 $b$ 正确。 ::::success[代码] ``` #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; } ``` ::::success[测试情况] $\text{\color{#81C784}AC in 1,2,3,7,8}$。 $\text{\color{red}WA}$ $30$ 分。 ![](https://cdn.luogu.com.cn/upload/image_hosting/kl4r0mu0.png) :::: #### 第三四层 ::::success[第三层] - 如果有 $a$ 说 $a$ 是正确的。 - 那么假设 $a$ 正确，$a$ 说 $a$ 正确，则 $a$ 正确。 - 假设 $a$ 是错误的，$a$ 说 $a$ 正确，则 $a$ 是错误的。 - 则**不确定正不正确**。 - 如果有 $a$ 说 $a$ 是错误的。 - 那么假设 $a$ 正确，$a$ 说 $a$ 错误，则 $a$ 错误，不合法。 - 那么假设 $a$ 错误，$a$ 说 $a$ 错误，则 $a$ 正确，不合法。 - 则**不合法**。 :::success[代码] ``` #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; } ``` ::::success[测试情况] $\text{\color{#81C784}AC in 1,2,3,4,6,7,8}$。 $\text{\color{red}WA}$ $42$ 分。 ![](https://cdn.luogu.com.cn/upload/image_hosting/oqt2ipjf.png) ::: ::::success[第四层] 既然想到了不确定 $a$ 正不正确，那么说 $a$ 正确或错误的 $b$ 也不知道正确或错误。 ::::success[代码] ``` #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; } ``` ::::success[测试信息] $\text{\color{#81C784}AC in 1,2,3,4,5,7,8,9}$。 $\text{\color{red}WA}$ $48$ 分。 **在点 $4$ 后面插入了一个点**。 ![](https://cdn.luogu.com.cn/upload/image_hosting/f5ne9py1.png) :::: #### 第五六层 ::::success[第五层] 剩下所有的点都是环状或者指向环状。 ![](https://cdn.luogu.com.cn/upload/image_hosting/nc6byvue.png) **对于环状的部分（只考虑 $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` 来实现，如果发现指向其的点已经被标记过，则算奇偶个数。 :::success[代码] ``` #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; } ``` :::success[测试信息] $\text{\color{#81C784}AC in all}$。 $\text{\color{#81C784}AC}$ $80$ 分。 ![](https://cdn.luogu.com.cn/upload/image_hosting/fllx91s9.png) ::: ::::success[第六层] 可以发现代码是从小的编号开始便利的，如下图： ![](https://cdn.luogu.com.cn/upload/image_hosting/w1wmeidz.png) ``` 5 1 1 0 5 0 4 0 5 0 4 0 ``` 遍历 $5$ 时，由于 $2$ 已经被遍历过了且说正确的个数为 $1$，是奇数，故会输出 `NO!`。 但实际是，$4,5$ 不确定对错，$2,3$ 也不知道对错。 改进的方法就是遍历每个点时，增加形式参数 $X$，代表目前块的名字是 $X$（不用考虑其他 $vis$ 赋值是 $1$ 会产生冲突，因为其他产生冲突的点都和该快不连通），然后碰见 $vis$ 被标记时判断是否是第 $X$ 块在行动。 将该点设为点 $16$，分值为 $10$。 :::success[代码] ``` #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; } ``` ::::success[测试信息] $\text{\color{#81C784}AC in all} ![](https://cdn.luogu.com.cn/upload/image_hosting/nuune9rx.png) ::: 可以发现 $n$ 的范围太小了，固设置 $3$ 个 $n=10^5$ 的数据。 经出题人（AI_god）本人考虑，若 $17,18,19$ 均 $AC$ 则按前 $16$ 个点正常计分，否则按前 $16$ 个点的总分除以 $2$ 再加上 $17,18,19$ 对的点个数 $\times 20$。 ::::