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

· · 题解

先打个表

n= 道路情况 是否连通
1 (1,1) 1
2 (1,2),(2,2) 1
3 (1,2),(2,1),(3,3) 0
4 (1,2),(2,4),(3,2),(4,4) 1
5 (1,2),(2,4),(3,1),(4,3),(5,5) 0
6 (1,2),(2,4),(3,6),(4,2),(5,4),(6,6) 0
7 (1,2),(2,4),(3,6),(4,1),(5,3),(6,5),(7,7) 0
8 (1,2),(2,4),(3,6),(4,8),(5,2),(6,4),(7,6)(8,8) 1

猜想：当 n=2^k(k \ge 0) 时，连通。

我们尝试证明一下：

当 n=2^k(k \ge 0) 时，对于任意的城市 x，若 x 是偶数，那么一定存在边 (x,\frac{x}{2})，因此一定有办法连通城市 x 和一个奇数城市 y。

对于任意一个 y，我们都可以通过边 (2y,y+\frac{n}{2}) 或边 (y,2y) 连通整个图。

至于给出一组不连通的点，这很好想，由于 n\ne 2^k(k \ge 0)，所以点 n 一定不能通过不断除以 2 得到 1，所以直接输出 1 和 n 即可。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    if((n&(n-1))==0) printf("YES\n");
    else{
        printf("NO\n");
        printf("1 %d\n",n);
    }
    return 0;
}