cf代码16-0是什么意思（CF1709A Three Doors 题解）

题目大意

有 \(3\) 个门
    
    
    
，有两个门后面会有一个钥匙     


     


     


，你现在手中有一把钥匙 




 




 




 ，问你能不能打开所有的门
    
    
    
。

题目分析

我们可以一步一步推导

   

   

   
，既然给了我们一把钥匙编号为 \(x\)     

     

     

，也就是可以打开编号为 \(x\) 的门  




  




  




 ，我们用 \(a_x\) 表示这扇门后面钥匙的编号


  


  


  
，将可以打开的门标记起来     
     
     
，然后产生分类讨论：

如果是 \(a_x\) 等于 \(0\) 的话   




   




   




 ，就没有钥匙



 



 



 
，不用标记               ，直接输出 NO     


     


     


。

如果 \(a_x\) 不等于 \(0\) 的话    




    




    




 ，就说明可以打开下一个门















，用 \(f\) 数组标记               ，然后可以继续讨论     



     



     



 ，不过讨论时变成了判断 \(a_{a_x}\)














，以此类推 




 




 




 。

但是到达最后一次的时候
    
    
    
，不管 \(a_{a_{a_x}}\) 是否等于 \(0\)     


     


     


，都可以打开 




 




 




 ，都可以来标记

   

   

   
，最后判断 \(f\) 数组的标记     

     

     

，输出答案  




  




  




 ，这样分析完后


  


  


  
，这道题就很简单了

   

   

   
。

AC Code

#include<bits/stdc++.h> using namespace std; #define ull unsigned long long const int MAX = 1e+4; inline int read() { int x = 0; char c = getchar(); while (c < 0 || c > 9) c = getchar(); while (c >= 0 && c <= 9) x = x * 10 + c - 0, c = getchar(); return x; } int t = read(), x, a[5]; bool f[5]; int main() { while (t--) { x = read(), a[1] = read(), a[2] = read(), a[3] = read(); if (a[x])f[x] = 1; else { cout << "NO" << endl; continue; } if (a[a[x]])f[a[x]] = 1; else { cout << "NO" << endl; continue; } if (a[a[a[x]]] == 0)f[a[a[x]]] = 1; if (f[1] == 1 && f[2] == 1 && f[3] == 1)cout << "YES" << endl; else cout << "NO" << endl; } return 0; }