[atAGC050A]AtCoder Jumper

考虑二叉树的结构，但并不容易构造从叶子返回的边

（以下为了方便，将所有点编号为$[0,n)$）

对于$i$，选择$2i\ mod\ n$和$(2i+1)\ mod\ n$这两条出边

从二叉树的角度并不容易证明正确性，可以先将取模去掉，那么两点相同当且仅当模$n$后相同

而10步以内，$i$可以走到$1024i+j$（其中$0\le j<1024$），必然存在一个与目标同余的点

1 #include<bits/stdc++.h>

2 using namespace std;

3 int n;

4 int main(){

5     scanf("%d",&n);

6     for(int i=0;i<n;i++)printf("%d %d\n",2*i%n+1,(2*i+1)%n+1);

7 }

巴特西

[atAGC050A]AtCoder Jumper

最新文章

热门文章