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