题解：P15057 [UOI 2023 II Stage] Roads of Potokolandiya

Warren1022 · 2026-01-26 15:55:34 · 题解

题解：P15057 [UOI 2023 II Stage] Roads of Potokolandiya

瞪眼观察可得

通过分析样例和数学推导，我们可以发现：

1. 当 n 是 2 的幂时（即 n = 1, 2, 4, 8, 16, \dots），图是连通的。
2. 当 n 不是 2 的幂时，图不连通。
3. 当图不连通时，城市 1 和城市 n 总是不可达的。

   代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    if ((n & (n - 1)) == 0) {// 判断 n 是否为 2 的幂
        cout << "YES\n";
    } else {
        cout << "NO\n";
        cout << 1 << " " << n << "\n";
    }
    return 0;
}