1334 - D. Minimum Euler Cycle（思维）

旧城等待， 2021-07-17 02:19 315阅读 0赞

[题目][Link 1]

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

如下:  
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 << " ";
    	}
    }

[Link 1]: https://codeforces.ml/contest/1334/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，315人围观）

还没有评论，来说两句吧...

相关阅读

相关 AIX 关闭Writesrv 1334端口

startsrc -s writesrv & netstat -an | grep 1334 \ netstat -an | grep 1334 tcp4 0 0 \

比眉伴天荒/ 2023年10月18日 19:19/ 0 赞/ 86 阅读

相关思维+贪心——cf1042D

/ 首先考虑从后往前计算lis，显然0的在很多情况下的贡献要大于1 如果遇上0，那么lis++，如果遇上1，那么cnt1++，并且用cnt1更新lis

一时失言乱红尘/ 2023年10月11日 09:09/ 0 赞/ 60 阅读

相关 The Euler function

题目描述： Problem Description The Euler function phi is an important kind of function in n

﹏ヽ暗。殇╰゛Y/ 2022年03月18日 02:50/ 0 赞/ 163 阅读

相关 project euler Problem 13

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] str="""37107287533902102

素颜马尾好姑娘i/ 2022年01月16日 03:24/ 0 赞/ 186 阅读

相关 Project Euler：Problem 1

problem: Multiples of 3 and 5 If we list all the natural numbers below 10 that are m

快来打我*/ 2021年11月09日 23:36/ 0 赞/ 266 阅读

相关 HDU - 6322 - Problem D. Euler Function 【欧拉函数 + 规律】题解

目录 1.题目 2.代码 1.题目 In number theory, Euler’s totient fu

叁歲伎倆/ 2021年07月25日 00:07/ 0 赞/ 360 阅读

相关 1334 - D. Minimum Euler Cycle（思维）

[题目][Link 1] 思路：其实构造起来还是不难的，要使形成一条字典序最小的欧拉回路。如下: n=5 12131415 232425

旧城等待，/ 2021年07月17日 02:19/ 0 赞/ 315 阅读

相关 D. Divide and Summarize(思维)

[题目][Link 1] 思路：其实想一想不难看出我们只需要将所有的情况得到的值存储起来，然后在之后的问询阶段判断是否有这个值就可以了。然后注意一下当值都相同时进行特殊判

「爱情、让人受尽委屈。」/ 2021年07月16日 18:07/ 0 赞/ 409 阅读

相关 1469D - Ceil Divisions （思维）

[题目][Link 1] 思路：首先对于1 2 3 4 . . . 2e5 我想啊，让 i=3 到 2e5-1的数全部 i/2e5 那么这些数就全为1了，1 2 1 1

淩亂°似流年/ 2021年07月16日 16:32/ 0 赞/ 291 阅读

相关 1199D - Welfare State（思维）

[题目][Link 1] 题意：对于n个公民，我们知道其一开始的各自的金钱。现在我们有两种操作：1.直接将各个钱数小于k的公民的钱数转变为k。2.将第p个人的钱数抓变为k

我就是我/ 2021年07月16日 15:04/ 0 赞/ 520 阅读