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