D - Minimum Euler Cycle
题意
有一个n个点的完全图 编号从1 到n
每两个点之间有两条路 所以共 n*(n-1)条边
n<1e5
要求找到一条字典序最小的欧拉路
并输出 在第l到r时刻经过的点
构造 找规律 前缀和 二分
结合样例找规律容易发现路径为
1 2 1 3 1 4 1 5 … 1 n
2 3 2 4 2 5 … 2 n
3 4 3 5 3 6 … 3 n
…
1
这里要用到前缀和+二分了，先前缀和到每个区间末尾有多少个数，然后二分找在哪个区间再结合规律输出即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| # include<bits/stdc++.h>
using namespace std;
# define endl "\n"
# define TurnoffIO std::ios::sync_with_stdio(false)
typedef long long ll;
const double eps = 1e-8;
const ll maxn = 1e6 + 5;
const int N = 1e5 + 5;
ll n,l,r,pre[N];
ll judge(ll x){
if(x>pre[n-1]) return 1;
int a=lower_bound(pre+1,pre+n,x)-pre;
int b=x-pre[a-1];
return (b&1?a:b/2+a);
}
int main(){
int T;cin>>T;
while(T--){
cin>>n>>l>>r;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+2*(n-i);
}
for(ll i=l;i<=r;i++){
cout<<judge(i)<<" ";
}
cout<<endl;
}
}
|