1334 - D. Minimum Euler Cycle（思维）

题目

思路：其实构造起来还是不难的，要使形成一条字典序最小的欧拉回路。

如下:
n=5

12131415
232425
3435
45
1

从这不难发现规律，我们只需找到它的起始位置，然后开始模拟，假设是第i行，i i+1 i i+2 i i+3…n每次到了n时到下一行i+1开始，正好模拟r-l+1步即可，细节见代码。

Code:

#include<iostream>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;

int main()
{
   
	FAST;
	int t;cin >> t;
	while (t--)
	{
   
		ll n, l, r;cin >> n >> l >> r;
		ll sum = r - l + 1;
		if (r == (n - 1) * n + 1)sum--;
		for (ll i = 0;i <= n - 1;i++)
		{
   
			if ((n * 2 - 2 - i) * (i + 1) >= l)
			{
   
				l -= ((n * 2 - 2 - i + 1) * (i));
				ll k = l / 2, num = 0, f = 0;
				i = i + 1;
				if (l % 2 == 0) f = 1;
				else k++;
				while (num < sum)
				{
   
					if (i + k == n + 1)
					{
   
						i++;k = 1;continue;
					}
					if (f == 0)
					{
   
						cout << i << " ";f = 1;
					}
					else
					{
   
						cout << i + k << " ";
						k++;f = 0;
					}
					num++;
				}
				break;
			}
		}
		if (r == (n - 1) * n + 1)cout << 1 << " ";
	}
}