Minimum Euler Cycle(找规律+模拟)

\(给你一个nnn个结点的完全有向图，求其字典序最小的欧拉回路，输出lll到rrr之间的结点为多少。\)

模拟一下n=5的时候

开始肯定是1-2-1-3-1-4-1-5

注意这个时候不能再从5到1，否则无路可走。那么5出发贪心就是

2-3-2-4-2-5

其实规律已经出来了，剩下就靠模拟了。

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn=1e6+9;

ll n,t,l,r,pre[maxn];

ll judge(ll x)

{

	if(x>pre[n-1])	return 1;

	ll a=lower_bound(pre+1,pre+n,x)-pre;

	ll b=x-pre[a-1];

	return (b&1?a:b/2+a);

}

void sovle()

{

	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;

}

/*

1 2 1 3 1 4 1 5 ... 1 n

2 3 2 4 2 5 2 6 ... 2 n

3 4 3 5 3 6 3 7 ... 3 n

...

1

*/

int main()

{

	cin>>t;

	while(t--)

		sovle();

}