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

题目：

lanxisi带领着他的拆迁队来整治一个街道。这个街道由N个旧房子组成，从左到右编号为1..N。每个旧房子i有一个正整数的美观度Ai。

lanxisi希望整个街道从左到右美观度严格递增，也就是保证Aij（i

现在，请你求出lanxisi最多能保留多少旧房子和整治这个街道所需要的最少总花费（当然是在保留旧房子最多这个前提下的）。
分析：
首先这种题一看要么贪心要么DP，对吧……贪心估计不靠谱，所以往DP上想。

因为需要尽可能保留旧房子，所以先考虑一个问题：假设我们保留的房子中，有两[……]

继续阅读

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

题目：


A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出n个种树的位置，顺时针编号1到n。并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。

最终市政府给园林部门提供了m棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上，给出无解信息。

[……]

继续阅读

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

题目：

高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
分析：
首先不用想，这肯定是个最小割……不妨将其解题过程记录下来，以作为一个典型的最小割模型题。
“最小割”求的是一个“最小”的值，而本题需要最大化喜悦值之和，所以很显然[……]

继续阅读

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

题目：

Z市交通不发达，所有公交路线覆盖的边竟然一个环也不包含，甚至该市的公交路线有可能会分为几个互不连通的块，这可真是不可思议。有一天，你突然听到一条消息，说你的M个同学被困在了Z市里，他们分别要从他们当前所在的点ai移动到他们想去的点bi.于是你立刻调集资料，了解了Z市的形状和公交路线的分布，现在你要算出每个人到达目的地最少要换多少次车，或者告知那个人不能仅用公交车达到目的地。
分析：
先考虑一个询问。假设我们想要从A走到B，像这样：
[国家集训队2011]公交路线 wbr解题报告
大概的路线是：从A向上走，然后经过LCA(A,B[……]

继续阅读

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

题目：

http://cogs.pro/cogs/problem/problem.php?pid=1883

为了提高自己的实力，gx想要制定一个合理的刷题计划。这里我们用实数来表示题目的难度，并且把刷题计划中由题目难度组成的序列称为刷题序列。gx刷题最喜欢循序渐进的方式，最理想的情况莫过于刷题序列是个等差数列了。但是这很难做到，于是我们定义一个刷题序列a的偏离值 ，其中L是给定的一个常数。

现在gx的老师已经布置给了他n道必做题，同时他还有空余时间从OJ上找m道题目来刷。他不希望改变这n道必做题的相对顺序，但是选做题的难度以及在数列中的位置都是任意的（OJ上的题目太多了，随你怎么挑）[……]

继续阅读

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

题意：

给一个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：如此扫描一遍后，数组变成了{“aab”,”ab”,”aac”,”ccf”,”cd”}，j指向”ccf”。

step 4：将i赋值为j，回到step 2进行下一次循环。

如何让0和1相邻呢？设0号[……]

继续阅读