百度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了,但是我们可以从终结状态向回查找,每回一步得到的状态都进行记录,这样就完成了查找过程。

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

当前页阅读量为: