[国家集训队2011]刷题计划 解题报…

题目: http://cogs.pro/cogs/problem/problem.php?pid=1883 为了提高自己的实力,gx想要制定一个合理的刷题计划。这里我们用实数来表示题目的难度,并且把刷题计划中由题目难度组成的序列称为刷题序列。gx刷题最喜欢循序渐进的方式,最理想的情况莫过于刷题序列是个等差数列了。但是这很难做到,于是我们定义一个刷题序列a的偏离值  新放进去这些题目的难度一定均分了a~a之间的部分(图画的不太平均,不要在意这些细节)。 为什么呢? 假设某一段的长度为c,我们试图在中间加一道题,把它分成两段a,b,自然a+b=c。 其代价为: 如果分成k+1段,代... 查看更多

[CF 325E]The Red Button解题报告

题意: 翻译后题面见:http://cogs.pro/cogs/problem/problem.php?pid=1920 给一个0~N-1的图,点i向点(2*i)%N和点(2*i+1)%N连有向边。求从0到0的哈密尔顿回路。 (怎么又是一道哈密尔顿回路) 做法: 首先明确一点:如果N是奇数那么无解。 为什么无解呢?原因很简单:0的唯一入边是int(N/2),但N-1的唯一入边也是int(N/2)。例如,当N=5时,0的唯一入边是2(0->0的自环不算),而4的唯一入边也是2(4->4的自环不算)。那么问题来了,哈密尔顿回路里时2->0还是2->4呢……显然都不行,所以无解。 然后看N是... 查看更多

TopCoder SRM496 Div1 YetAnotherHamiltonianPath解题报告

题意: 有N “aac” -> “ab” -> “ccf” -> “cd” -> “aab”就一定是一个最短的哈密尔顿回路。 在讨论如何让0和1相邻之前,先看一下如何实现这个“划分”的细节; step 1:设i,j两个指针,让i从”aab”开始扫描。 step 2:让j指向i的下一个位置,顺序遍历后面的城市名称,如果首字母和 i 指向的城市相同,就将它和 j 指向的城市交换,并把 j 指针加1. step 3:如此扫描一遍后,数组变成了{“... 查看更多