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