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();
}

Minimum Euler Cycle(找规律+模拟)

原文：https://www.cnblogs.com/iss-ue/p/12795188.html