百度NOIP吧编程挑战赛 解题报告

测试数据：点此下载

作弊名单：点击查看

比赛成绩：点此查看

第二题 Special Judge 程序下载：点此查看

（解题报告由出题人或选题人提供。）

1、这也叫破译？

problem：输入n个字符串，统计权值，按权值降序排序，输出字符串和权值。

analyze： 作为模拟赛的第一题，难度很easy啊。没有什么难的地方，很基本的算法，ac不成问题。

project：加强字符串的读入和统计能力，快速排序的能力和记录类型的运用。

用table数组表示字母表,直接定义成常量数组：table:array[97..122] of integer=();这样在可以定义一个函数cost，表示每个单词的权值。

a[i].data记录每个字符串，a[i].cost记录每个字符串的权值，通过1个qsort(用随机化快排还是很棒的（随机化快排是什么？百度一下），进行排序，排完序输出。

2、联络

本题很明显属于图论中的求最小生成树，只需要注意把存在的边权值赋为0即可。

3、冲锋

菜鸟：NPC_T

Charge这道题准确的说并不是我的原创（我的原创部分由于和第二题的考察范围冲突和谐掉了），而是改编自CTSC`98的题目选课（score）。唯一不同的是，由于时代的进步，本题大大增加了数据范围，由原题的n、c小于400大大增加。

先简单地说一下题目的建模分析：题目已经阐述得很清晰，这明显是一个树，从树中选出若干个点（选这些点的充要条件是他们的父亲被选）并最大化点权之和。很容易想到这是一个树形DP，物品就是这些节点，其重量为1，价值为点权。

用传统的树形DP（如DDengi牛在《背包九讲》一文中所讲述）可以做到O

(n*C^2)，其基本思想是引入“泛化物品”的概念，即f[i,j]表示在以点i为根的子树中耗费重量j所能得到的最大价值；由于该方法简单容易理解且大多数人都已经看过，加上n*C^2的算法明显对于这道题会死的很惨（60~80分），我谈一下树形DP的O(nC)算法（该算法复杂度已经达到树形DP问题的理论下界，证明略）。

首先鸣谢2008年的noi金牌第九名，现就读于徐持衡(xc_bb)大牛，是他的WC2009国家集训队论文《浅谈几类背包题》让我首次认识这种优秀而简洁的算法，这次命题也得到了他本人的帮助，核心思想也来自他的论文。

如果说DDengi的“泛化物品和”算法已经深入挖掘了“背包”这一名词的本质，那么xc_bb的“泛化物品并”算法就是对“最优化”的细细推敲。其基本思想是，如果有f[i],f[k]两个泛化物品，那么他们的最优泛化物品并应该是

f[i,j]=max{f[i,j],f[k,j]}

这个关系简洁而明显，在此不需要多说。而接下来的结论显然更惊艳一些：对于一个节点i和它的一个儿子x，我们先将f[i]强制赋给f[x]，然后递归地解决x，最后f[i]就是原来的f[i]和而今的f[x]的泛化物品并。

当然这个描述过于“泛化”，鉴于本菜鸟水平有限，无法将其特别明晰地表述清楚（其实我理解这个也花了整整一节历史一节地理的时间），现附上xc_bb大牛的《浅谈几类背包题》神文地址，相信大家从中可以学到很多，不仅仅是树形背包，对于其他各类背包也会有一个更深刻的理解。

以下是神文的度娘文库地址：

http://wenku.baidu.com/view/8ab3daef5ef7ba0d4a733b25.html 【pdf】

http://wenku.baidu.com/view/3fd4138884868762caaed5a8.html 【ppt】

感谢国家，感谢党，感谢noip贴吧提供给我这次命题的机会，感谢父母，感谢xc_bb大牛，感谢各位来参加模拟赛的oier们！

4、开灯关灯

这个题看起来好你是bfs，但是对于普通的bfs来说，数据过大一定超时。这里我们注意到终结状态是一定的，于是我们考虑把所有可能的初始状态都求出来，记录每一个点到达终结状态的过程，然后打表输出，那么整体的时间效率就看求初始状态的时间了，当然我们就不能直接bfs了，但是我们可以从终结状态向回查找，每回一步得到的状态都进行记录，这样就完成了查找过程。

可能我写的不太好，大家不太好理解，大家都看一下程序就好了……