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

哈哈人生 · 2026-01-26 13:44:01 · 题解

题外话

这题标签为啥是数学啊？可能是我太纯度了吧。

思路

第一感觉肯定是暴力建图，然后使用并查集判断连通性。然后，就没有然后了（所以我实在不明白怎么会有人想到数学）。时间复杂度 O(n)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,fa[1000005];
int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)fa[find(i)]=find(i+i>n?i+i-n:i+i);
    for(int i=2;i<=n;i++){
        if(find(i)!=find(1)){
            cout<<"NO\n"<<i<<" "<<1<<"\n";
            return 0;
        }
    }
    cout<<"YES";
    return 0;
}