[国家集训队2011]拆迁队 解题报告

题目: http://cogs.pro/cogs/problem/problem.php?pid=1859 lanxisi带领着他的拆迁队来整治一个街道。这个街道由N个旧房子组成,从左到右编号为1..N。每个旧房子i有一个正整数的美观度Ai。 lanxisi希望整个街道从左到右美观度严格递增,也就是保证Aij(i 现在,请你求出lanxisi最多能保留多少旧房子和整治这个街道所需要的最少总花费(当 … 继续阅读“[国家集训队2011]拆迁队 解题报告”

[国家集训队2011]种树 解题报告

题目: http://cogs.pro/cogs/problem/problem.php?pid=1862 A城市有一个巨大的圆形广场,为了绿化环境和净化空气,市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后,初步规划出n个种树的位置,顺时针编号1到n。并且每个位置都有一个美观度Ai,如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳,两棵树决不能种在相邻的位置(i号位置和i+1 … 继续阅读“[国家集训队2011]种树 解题报告”

[国家集训队2011]happiness(吴确)…

题目: http://cogs.pro/cogs/problem/problem.php?pid=1873 高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的 … 继续阅读“[国家集训队2011]happiness(吴确)…”

[国家集训队2011]公交路线 解题报…

题目: http://cogs.pro/cogs/problem/problem.php?pid=1877 Z市交通不发达,所有公交路线覆盖的边竟然一个环也不包含,甚至该市的公交路线有可能会分为几个互不连通的块,这可真是不可思议。有一天,你突然听到一条消息,说你的M个同学被困在了Z市里,他们分别要从他们当前所在的点ai移动到他们想去的点bi.于是你立刻调集资料,了解了Z市的形状和公交路线的分布,现 … 继续阅读“[国家集训队2011]公交路线 解题报…”

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

题目: http://cogs.pro/cogs/problem/problem.php?pid=1883 为了提高自己的实力,gx想要制定一个合理的刷题计划。这里我们用实数来表示题目的难度,并且把刷题计划中由题目难度组成的序列称为刷题序列。gx刷题最喜欢循序渐进的方式,最理想的情况莫过于刷题序列是个等差数列了。但是这很难做到,于是我们定义一个刷题序列a的偏离值  新放进去这些题目的难度 … 继续阅读“[国家集训队2011]刷题计划 解题报…”

[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)。 … 继续阅读“[CF 325E]The Red Button解题报告”

TopCoder SRM496 Div1 YetAnotherHamiltonianPath解题报告

题意: 有N “aac” -> “ab” -> “ccf” -> “cd” -> “aab”就一定是一个最短的哈密尔顿回路。 在讨论如何让0和1相邻之前,先看一下如何实现这个“划分”的细节; step 1:设i,j两个指针,让i从”aab”开始扫描。 st … 继续阅读“TopCoder SRM496 Div1 YetAnotherHamiltonianPath解题报告”