浅谈数据的合理组织53807.docx

《浅谈数据的合理组织53807.docx》由会员分享，可在线阅读，更多相关《浅谈数据的合理组织53807.docx（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、浅谈数据的合理组织【摘要】信息学是一一门高深深的学科科，它正正在高速速的发展展。随着着信息学学的发展展，其题题目中的的关系也也变得越越来越错错宗复杂杂，给我我们解题题带来困困难。对对数据进行行合理地组织，正正是我们们面对上上述题目目时的一一种有效效手段。本文用几个个经典例例题从数数据的结结构和顺顺序两个个方面进进行合理理组织，达达到优化化模型或或是提升升算法效效率的目目的。介介绍了“合合理组织织数据”在在信息学学中建立立模型和和优化算算法方面面的一些应用用，例题题包含了了动态规规划、数数据结构构、图论论类型的的题目。目的在在于引起起读者对于于数据的的合理组组织的关关注，并并在今后后的解题题中能

2、积极并灵灵活地运运用这一一手段。【关键字】组织数据数据结结构动动态规划划图树序序列【正文】【引言】一个简单的的例子：给出N个数数字(数字会会比较大大)，然后给给出一些些询问，询询问一个个数字有有没有在在给出的的N个数字字当中。当然我们有有很多已已知的办办法：HASH表表、TRRIE、预预排序+二分查查找这些算法都都是通过过对数据据进行合合理的组组织而起起到了减减少工作作量的作作用。不同的是HHASHH表和TRRIE是是利用数数据形式式的重新新组织，而而预排序序二分分查找是是通过对对数据顺顺序的重重新组织织来达到到优化算算法的目目的的。我我们组织织数据，主主要就是是通过从从“形式式”和“顺顺序”

3、这这两个角角度来考考虑。事事实上，这这两个方方面在实实际运用用中往往往不是独独立的，通通常需要要联合运运用。我们已经学学习了很很多经典典的数据据结构，它它们都是是合理组组织数据据的表现现。在优优化算法法中有很很好表现现。对数数据组织织的合理理化，不不仅在我我们设计计算法时时能起到到优化程程序效率率的作用用，有时时，我们们在建立立解题模模型时，合合理地组组织数据据可能给给我们提提供新的的思考角角度，从从而优化化解题模模型，例例一就是是这样的的一个例子子。例一金金明的预预算方案案及其加加强版金明的预算算方案【题意描述述】给出N个物物品，每每个物品品都有一一个权值值(5500000)和和一个价价格(

4、100000)。我们们称可以以直接被被购买的的物品为为主件，称称不能被被直接购购买的物物品为附附件，附附件只有有当其主主件被购购买了才才能被购购买，一一个主件件最多有有两个附附件，附附件没有有下一级级附件。任务购买一一些物品品，总价价格不超超过M，使得得被购买买的物品品的权值值之和最最大。N32000 MM600【简要分析析】我们很容易易联想到到经典的的动态规规划之00-1背包问问题。但是题目与与背包却却有一些些差别：附件不不能被直直接购买买。【对数据的的初步组组织】主件与附件件之间是是树形的的关系。组组织一下下数据，如如下图：（图1）如图所示：主件1没有有附件，主主件2有两个个附件，主主件3

5、只有一一个附件件。【数据组织织方案一一】假设我们忽忽略数据据的特殊殊性，单单从树结结构考虑虑，我们们容易想想到的一一个算法法是：给所有主件件加上一一个“级级超主件件”，把把原来的的所有主主件都变变成“超超级主件件”的附附件，如如下图： (图2)【算法一】这样，在这这棵树上上，我们们可以设设计一个个动态规规划算法法：定义：costa表表示a节点所所代表的的物品的的价格scoreea表示a节点所所代表的的物品的的得分状态faabb表示示以节点点a为根的的子树，总总共花费费不超过过b元的最最多得分分。状态转移方方程：fab=Maxxfc1b11+ffc22bb2+fcc3b3.fcckbk+ssco

6、rreaa;其中ci为为a的子节节点；bi=b-ccostta;这样枚举的的效率显显然不高高！我们可以用用左儿子子右兄弟弟表示法法来表示示这一棵棵树，将将原树转转化成二二叉树，则则我们在在进行状状态转移移的时候候只用考考虑给左左儿子分分配多少少钱。lefta表表示a的左儿儿子rightta表示a的右儿儿子fab=MaxxMaaxffleeftablleftt+ffriighttabb-coosta-bleeft+sscorreaa,ffriighttabb这样我们可可以得到到一个理理论 参见算法艺术与信息学竞赛贪食的九头龙中对算法复杂度的分析复杂杂度为OO(NMM2)的算法法，但是是对于本本题

7、的数数据范围围来说，这这个复杂杂度并不不太理想想。【数据组织织方案二二】上面我们把把本题同同0-1背包进进行了类类比。发发现两道道题之间间的差别别：附件件不能被被直接购购买。显显然，如如果题目目中没有有附件，那那么本题题即为标标准的001背包包问题。我们回到题题目并考考虑其特特殊性：1.附件没没有附件件。2.每个主主件最多多只有22个附件件。这样，显然然对于（图图一）中中每一组组（主件件附件件），可可以作为为整体考考虑。对于每一组组，可能能的购买买方案最最多只有有：1.什么都都不买2.只购买买主件3.购买主主件和附附件14.购买主主件和附附件25.购买主主件和两两个附件件这样，我们们可以借借鉴

8、经典典的011背包动动态规划划，把每每一组看看作一个个对象，取取值和花花费对应应最多五五种。【算法二】costik表表示分组组后第ii个对象象的第kk种购买买方案的的花费。weighhtiikk表示示分组后后第i个对象象的第kk种购买买方案的的总权值值。Fij表表示前ii个对象象最多花花费j元，能能得到的的最大权权值。Fij=maxx(Fi-11jj-coostik+weeighhtiikk);其中1=k=5且cosstiikk=j状态总数：O(NNM)转移代价：O(11)这样，我们们得到了了一个时时间复杂杂度为OO(NMM)的优秀算法法。郁闷的金明明【题意描述述】给出N个物物品，可可以直接接

9、被购买买的称为为主件，而而不能直直接被购购买的称称为附件件，附件件只有当当其主件件被购买买了才能能被购买买，一个个主件可可以有任任意多个个附件，附附件没有有下一级级附件。每每个物品品都有一一个权值值(5500000)。任务购买一一些物品品，总价价格不超超过M，使得得被购买买的物品品的权值值之和最最大。N60M=ccostti),Fi+11jj00情况II：第i个物品品是附件件如果k=11 Fijk= MaaxFFi+1j-ccostti11+wweigghti(j=cosstii),Fii+1j1如果k=00 Fijk= Fi+11jj00状态总数：O(NNM)转移代价：O(11)时间复杂度度

10、同样是是O(NNM)。很郁闷的金金明【题意描述述】给出N个物物品，可可以直接接被购买买的称为为主件，而而不能直直接被购购买的称称为附件件，附件件只有当当其主件件被购买买了才能能被购买买，一个个主件可可以有任任意多个个附件，附附件可以以有多级级，也就就是说如如果某个个物品是是附件，那那么它还还有可能能有附属属于它的的下一级级附件。每个物品都有一个权值(50000)。任务购买一一些物品品，总价价格不超超过M，使得得被购买买的物品品的权值值之和最最大。N60M32000【问题分析析】现在题目在在原题的的基础上上不仅放放宽了附附件的个个数，还还放宽了了附件的的层数，如图所所示：从上图中，我我们可以以对

11、本题题有一个个感性的的认识：关系又又“宽”又又“深”。我们依然试试着从前前面的题题目中寻寻找算法法：我们可以直直接套用用算法11，因为为该算法法正好将将数据作作为树结结构来进进行处理理。而利利用了题题目特殊殊条件的的算法22和算法法3，直接套套用算法法肯定是是行不通通的。但是他们都都很有启启发性：抛弃树树形的结结构，重重新组织织成线形形。现在的题目目是不是是也可以以类似解解决呢？【组织数据据方案四四】算法3相对对来说比比较算法法2更加一一般，所所以现在在我们再再回过头头来研究究一下算算法3，希望望在分析析过程中中找到一一些灵感感。回忆算法33的思路路：把同在一个个组的主主件放在在附件的的前面，

12、利利用动态态规划“加加一维”的的思想，顺顺利地实实现了将将问题转转化到序序列上来来。关键字：主主件在前前序列列动态态规划我们联想到到利用树树的先根根遍历序序，而且且正好满满足上面面的关系系。但是这样有有什么好好处吗？还能进进行动态态规划吗吗？怎样设设计状态态才能传传递父节点的状状态呢？我们再回过过去看算算法3的状态态转移：假设当前状状态是FFijk，且k=0。如果i是附附件，那那么实际际上在到到达下一一个主件件以前，i后面的附件是都不会被购买的。上图中，对对于附件件a，实际际上一个个k=00的状态态传递下下去是没没有意义义的，因因为附件件b和附件件c也必然然不能被被购买。思考并总结结上面的的结

13、论：对于一个主主件，我我们如果果不购买买的话，那那么其附附件我们们都不用用考虑，而而直接“跳跳”到下下一个主主件。我们把它应应用到本本题中来来：重要结论我我们考虑虑一棵子子树的时时候，如如果我们们不购买买其根节节点，那那么其子子树中所所有节点点我们都都不必讨讨论了。这一结论似似乎很显显然，但但是我们们并不是是要在树树结构中中用这一一结论。正正如上面面提到的的，我们们要在树树的先根根遍序上上进行动动态规划划，而这这一结论论正是我我们成功功的关键键。【算法4】根据前面的的思考，我我们先依依次求出出每棵树树的先根根遍历序序，并保保存在同同一个序序列liist中。为了利用上上面的结结论，我我们还要要求

14、出以以节点ii为根的的子树的的节点总总数coountti。现在我们来来设计动动态规划划算法：定义：costi表表示第ii个物品品的价格格weighhtii表示示第i个物品品的权值值Fij表表示从第第i个物品品到第nn个物品品，最多多花费jj元，能能得到的的最大权权值和。状态转移：对于一个节节点，我我们考虑虑是否购购买它：购买：那么么我们继继续考虑虑它后面面的节点点不购买：那那么我们们跳过它它的子孙孙节点方程如下：Fij=MaxxFi+11jj-coostlisstii+weiighttliisti,Fi+ccounntllisttij这个算法依依然是OO(NMM)的，很完完美地解解决了本本题。

15、并并且，这个算算法模型型对于以以前有很很多类似似的树形形动态规规划题目目都适用用，这是是我们在在分析本本题的过过程中的意外外收获。【小结】这是一道很很有启发发性的道道目。反反思这一一题的几几个不同同难度的的版本，不不难发现现我们最最终都用用线形模模型上的的动态规规划取代代了容易易想到的的树形动动态规划划算法。我们再次分析前面的算法，试图发现其中内在的一些东西。其实我们这个题主要就是对于树形结构和线形结构的选择，所以我们对比算法4和算法1:不难发现，相比算法4，算法1其实多出的操作就是枚举分配给左儿子多少钱。而在线形的的序列上上，没有有用的钱钱自然地地被分配配给后面面的元素素。也就就是说：树的形

16、形态决定定了在状状态转移移的时候候要进行行额外的的枚举。这正是树形动态规划算法的瓶颈所在！而我们利用树的先根遍历序将转树形转化为线形序列，成功地避免了树形形态的限制，正是合理地组织数据。我们得到的的启示：凭第一感感觉想出出来的模模型不一一定是最最好的，对对于一个个题目，我我们充分分挖掘其其数据关关系并加加以利用用，合理理地组织织数据并并且尝试试用已有有的知识识来解决决，推陈陈出新，才才能不断断地进步步。前面我们在在树据的的组织结结构上进进行了合合理地安安排，成成功地对对于每一一次加强强的题目目都设计计出了优优秀的算算法，下下面，我我们来看看一看“顺顺序”的的合理安安排的例例子：例二树树的果实实

17、【题意描述述】给出一棵有有N个节点点的有根根树（根根为1号节点点），每每个节点点有权值值。要求对于每每一个节节点，求求：1.其子树树中权值值比该节节点大的的节点总总数2.树上除除其子孙孙节点外外比该节节点大的的节点总总数3.从根节节点到该该节点路路径中比比该节点点大的节节点总数数其中(1=N=1005)【问题分析析】对于要求的的后面两两个值，我我们很容容易想到到O(NNlogg2(N)的算算法：树上除其子子孙节点点外比该该节点大大的节点点总数：直接排排序，在在待统计计节点前前的与该该节点权权值不同同的个数数再减去去问题11的答案案即为所所求。从根节点到到该节点点路径中中比该节节点大的的节点总总

18、数：以以权值为为关键字字构造线线段树(若权值值大可行行离散化化处理)，深度度优先遍遍历树上上节点，用用栈记录录下到节节点的路路径，并并把当前前节点插插入线段段树，在在线段树树中我们们记录区区间的元元素个数数，当前前节点权权值到最最大权值值这个区区间中元元素个数数即为所所求，我我们再递递归处理理子树，在在子树访访问完毕毕后还须须把该节节点从线线段树中中删除。我们最大的的困难在在于求：其子子树中权权值比该该节点大大的节点点总数O(N2)的朴素素统计方方法是很很容易想想到的，但但是本题题的数据据规模达达到1005，O(NN2)的复杂杂度显然然太高。我我们自然然想到利用用线段树树、树状状数组这这些优秀

19、秀的统计计数据结结构来进进行题目目中要求求的统计计任务。但是这这些数据据结构都都是用于于线型序列列统计的的，并且且似乎没没有改造造版本用用于树形形结构。既然没有办办法改造造数据结结构，那那么我们们转换数数据形态态把把树转化化为序列列再进行行统计，先根遍历序即是我们转换后的理想形态。我们给出一一个例子子：同一棵子树树构成一一个连续续的区间间，这正正方便了了我们的的统计。我们定义：一个元素所所在子树树在遍历历序中构构成的区区间叫作作元素所所在区间间。元素相比较较都指其其权值大大小相比比较。现在问题已已经转化化成为：给出一个序序列，每每个元素素有权值值。对于于每一个个元素，统计一个区间中有多少元素比

20、该元素大。这正是我们们比较熟熟悉的序序列上的的统计问问题。下下面我们们研究转转化后的的问题：【数据组织织方案一一】我们不对数数据进行行更深入入的组织织，直接接利用先先根遍历历序，强强制用数数据结构构来进行行统计。当然我们可以构造出一种比较有效的嵌套数据结构以有序表为元素的线段树，如图：其中，线段段树的每每一个节节点是对对应区间间的元素素以权值值为关键键字的有有序表。这样，预处处理可以以用一个个归并排排序，求求得树上上所有区区间的有有序表。时时间复杂杂度为OO(Nllog22(N)。假设现在我我们要统统计一个个区间(长度为为L)。那么我们可可以用llog22(L)的时时间找到到该区间间的所有有分

21、解区区间(不超过过2logg2(L)个)。然后后在对每每个分解解区间进进行处理理：二分分查找在在该区间间中有多多少元素素的权值值比指定定的元素素的权值值大。然后把所有有分解区区间中比比给定元元素大的的元素个个数加起起来，即即为所求求。这样每统计计一个元元素的复复杂度为为O(llog222(N)。总时时间复杂杂度为OO(Nllog222(N)，空间间复杂度度为O(Nloog2(N)。【数据组织织方案二二】我们从特殊殊情况考考虑：假假设我们们在先根根遍历序序中，需需要统计计元素kk，并且k所在区区间里的的元素都都比它大大。显然，这时时比k大的元元素个数数就是kk所在区区间中的的元素个个数。统统计区

22、间间元素个个数我们们可以直直接利用用线段树树和树状状数组。那么我们如如何保证证当前列列表中的的元素权权值都比比k的权值值大呢？我们重新组组织数据据：所有有元素按按从大到到小的顺顺序排序序。然后后依次处处理每一一个元素素：先取取得所在在区间的的元素个个数，再再将该元元素插入入。我们一个很很巧妙的的方法：从大到到小地向向线段树树里面加加入元素素，然后后统计区区间个数数。从大到小保保证了现现有的所所有元素素都比待待插入的的元素大大。所以以区间中中的元素素个数即即为比待待插入元元素大的的元素个个数。按照从大到到小的顺顺序之前前先对其其区间进进行统计计，利用用线段树树或树状状数组。这样，我们们得到了了复

23、杂度度为O(Nloog2(N)的算法法。WC20005何林林同学的的论文中中介绍了了此题的的另一解解法，复复杂度也也为O(Nloog2(N)。主要要思想是是也是利利用树的的前根遍遍历序，不不同的是是他的算算法是基基于容斥斥原理，需需要正反反两次遍遍历树，而而我们这这里介绍绍的算法法是利用用了“组组织数据据的操作作顺序”这一手段来实现的。有兴趣的同学可以参见何林同学2005年的论文。“形态”和和“顺序”这这两种数数据组织织对象在在上面的的两个例例题中分分别对我我们进行行了表演演。下面面我们再再来分析析一个更更经典的的题目：例三航航线规划划【题意描述述】给出一个有有N个点M条边的无无向图，两两点之

24、间间可能有有多条边边，然后后给出QQ个命令令，命令令共有如如下两种种：1 A BB表示删除一一条A到B的边2 A BB表示询问AAB间共共有多少少条关键键边（即即删除改改边后使使得ABB不连通通)数据保证任任意时刻刻图都是是连通的的。1 N 3 * 11041 M 10051 Q 1005【问题分析析】显然，我们们可以轻轻松地设设计出一一个朴素素的算法法：用队列保存存所有边边，当遇遇到删边边操作时时加上删删除标记记（利用用HASSH我们们可以做做到O(1)，遇到到询问操操作时则则枚举删删边然后后用并查查集判断断AB是否否连通。这这个算法法处理删删边的复复杂度为为O(11)，处理询问问的复杂度度

25、为O(M2)，空间间复杂度度为O(M+NN)。我们经过思思考后发发现，事事实上所所谓的关关键边都都是图上上的桥(由题目目中的描描述我们们很容易易想到)。而桥桥的数量量是O(N)级级别的。利用上面的的结论，我我们显然然可以先先用O(E)的的时间求求出图中中所有的的桥，然然后再用用O(NN2)的时间间求出AAB间的的关键边边的数量量。然而，我们们所优化化后的程程序依然然有很高高的时间间复杂度度，根本本不能胜胜任此题题。我们继续思思考：树上的任意意两点间间只有一一条路径径。也就是说树树上的任任意一条条边都是是关键边边。这跟跟我们的的题目有有什么关关系呢？显然，同同一个重重连通分分量(块)中的任任意两

26、点点之间都都没有关关键边。并且，对于于两个不不同的重重连通分分量M11,M22：在进进行删边边操作以以前，询询问任意意分属这这两个分分量的两两点AM11,BMM2，询询问的结结果都是是一样的的，即结结果只跟跟分量间间的边有有关系。也就是说，一个重连通分量可以当作整体来考虑。【初步组织织数据】由前面的思思考，我我们把图图中的重重连分量量都“缩缩”成一一个点。构构成一个个新图，显显然，新新图是一一棵树。如下：这样，对于于AB的的询问：若AB属于于同一个个重连通通分量，则则没有关关键边。若AB属于于不同的的重连通通分量，则则转化为为求两个个树上节节点的距距离。求树上两个个节点的的距离我我们有现现成的

27、办办法，定定义：DepthhA为节点点A的深深度LCA(AA,B)为节点点A和节节点B的的最近公公共祖先先。那么AB间间的距离离Diss(A,B)=DeppthA+DeppthB-2*DDeptthLLCA(A,BB)注意一个细细节，即即我们把把一个重重连通分分量“缩缩”成一一个节点点时，事事实上是是把分量量里面的的所有点点的深度度都设为为它们中中最小的的那个深深度，即即往上提提升(在在同一个个重连通通分量中中以深度度最小的的点作其其它点的的代表)。如此一来，对对于一个个现成的的图，我我们可以以很快地地求出两两点间的的关键边边数量了了。预处理即为为一个求求重连通通分量的的操作，时时间复杂杂度为

28、OO(M)。而对于每一一个询问问我们都都可以OO(1)完成回回答。但事实上这这道题目目中的图图是随时时变化的的(有删删边操作作)，这这样我们们就不太太好处理理了。如果每次都都求一次次块的话话，复杂杂度会很很高。我我们思考考怎么处处理这个个问题：删边操操作会导导致块的的分裂。我我们当然然可以只只对被删删边所在在的块进进行处理理，但是是最坏情情况下还还是和每每次求一一次块是是一样的的。【进一步组组织数据据】现在的问题题是我们们需要快快速地将将一个块块进行重重新求块块，似乎乎是没有有现成的的办法。但但是如果果操作不不是删边边，而是是加边呢呢？显然，在一一棵树上上加上一一条边，必必然产生生环，伴伴随着

29、的的就是新新的重连连通分量量产生。我们只需要要将几个个有关的的块进行行合并。换换句话说说，就是是把一些些点的位位置抬高高，并把把它们合合并成一一个块。如如下图：比如我们加加入一条条边ABB，T=LCAA(A,B)，那那么我们们的环上上的节点点即为AA到T的的路径中中和B到到T的路路径中的的节点。我我们需要要把环上上的节点点的深度度都减小小到DeepthhT，并且且，我们们提升一一个节点点，其子子孙节点点也要一一同被提提升相同同的高度度。我们研究发发现，如如果操作作是加边边的话，我我们似乎乎可以很很高效地地处理。那么我们当当然可以以把操作作反过来来处理(先处理理后面的的操作)，这样样就可以以实现

30、我我们所要要达到我我们所期期望的结结果操作变变为只有有加边和和询问。现在我们来来考虑细细节实现现：我们需要用用到LCCA，当当然可以以用中序序遍历+RMQQ实现。而而且，加加边操作作并不影影响LCCA。然后我们还还有一个个提升一一棵子树树的高度度的操作作。即把把一棵子子树的所所有节点点的Deetphh都减去去同一个个数。显然，我们们可以求求出树的的先根遍遍历序。这这样，同同一棵子子树构成成一个连连续区间间。利用用线段树树或树状状数组我我们就可可以用OO(loog2(N)的时时间完成成这项操操作。【小结】这是一道很很经典的的题目。我我们最初初利用“收收缩”的的思想，把把图整理理成为一一棵树，然然

31、后又巧巧妙地将将数据从从后往前前处理，把把原题中中的“删删边操作作”操作作变成了了“加边边操作”。既有“形态”，又有“顺序”上的考虑。在细节实现中，我们又利用了树的两大遍历序中序遍历和前序遍历，把树上的求LCA操作和提升子树的操作变成了序列上的求RMQ操作和给一个区间所有元素减去一个值的操作。无处不体现出“对数据的合理组织”。【总结】“对数据的的合理组组织”无处不不在，它它不仅仅仅是一种种手段，更更是竞赛赛的一种种思考方方向。在在数据关关系越来来越复杂杂，解题题模型越越来越不不明显的的信息学学竞赛中中，合理理地组织织了数据据，就可可以说离离成功只只有一步步之遥了了。我们在被告告知一个个很巧妙妙

32、的算法法时，感感兴趣的的除了算算法本身身之外，还有就是算法的设计者到底是怎么想到这个算法的。甚至，我们往往对后者所产生的兴趣超过前者。这正是我们前进的动力，思想的源泉。多思考、多多总结、勇于探索、不断创新！【参考资料料】算法艺术术与信息息学竞赛赛刘汝汝佳黄亮亮著2005年年国家集集训队论论文数数据关系系的简化化何林林【感谢】感谢叶诗富富老师对对我的指指导和帮帮助。感谢古楠同同学和王王晓珂同同学对我我的论文文提出了了很好的的建议。【附录】金明的预算算方案 NOIP2006【题目描述述】金明今天很很开心，家家里购置置的新房房就要领领钥匙了了，新房房里有一一间金明明自己专专用的很很宽敞的的房间。更更

33、让他高高兴的是是，妈妈妈昨天对对他说：“你的房房间需要要购买哪哪些物品品，怎么么布置，你你说了算算，只要要不超过过N元钱就就行”。今天天一早，金金明就开开始做预预算了，他他把想买买的物品品分为两两类：主主件与附附件，附附件是从从属于某某个主件件的，下下表就是是一些主主件与附附件的例例子：主件附件电脑打印机，扫扫描仪书柜图书书桌台灯，文文具工作椅无如果要买归归类为附附件的物物品，必必须先买买该附件件所属的的主件。每每个主件件可以有有0个、1个或2个附件件。附件件不再有有从属于于自己的的附件。金金明想买买的东西西很多，肯肯定会超超过妈妈妈限定的的N元。于于是，他他把每件件物品规规定了一一个重要要度

34、，分分为5等：用用整数115表表示，第第5等最重重要。他他还从因因特网上上查到了了每件物物品的价价格（都都是100元的整整数倍）。他他希望在在不超过过N元（可可以等于于N元）的的前提下下，使每每件物品品的价格格与重要要度的乘乘积的总总和最大大。设第jj件物品品的价格格为vj，重重要度为为wjj，共共选中了了k件物品品，编号号依次为为j1，j2，jk，则则所求的的总和为为：vj1*wj1+vj2*wj2+ +vjk*wjk。（其其中*为乘号号）请你帮帮助金明明设计一一个满足足要求的的购物单单。【输入文件件】输入文文件buudgeet.iin 的的第1行，为为两个正正整数，用用一个空空格隔开开：N

35、 m（其其中N（3220000）表示示总钱数数，m（600）为希希望购买买物品的的个数。）从第22行到第第m+11行，第第j行给出出了编号号为j-1的物物品的基基本数据据，每行行有3个非负负整数v p q（其其中v表示该该物品的的价格（v0，表示该物品为附件，q是所属主件的编号）【输出文件件】输出文文件buudgeet.oout只只有一个个正整数数，为不不超过总总钱数的的物品的的价格与与重要度度乘积的的总和的的最大值值（22000000）。【输入样例例】10000 58000 22 04400 5 113000 5 14000 33 05500 2 00【输出样例例】22200树的果实 NOI

36、2004浙江省队选拔赛题目【题目描述述】森林中生长长着许多多奇特的的果树，它它们不仅仅外形独独特，其其果实更更是可口口。这天天，两只只小虫NNileeh和Nixxed决决定一起起分享一一棵果树树。他们们从一直直辛勤工工作到下下午，终终于把这这棵果树树锯倒了了。他们观察着着这棵果果树，果果树开始始端是是露出地地面的根根部，接接着像其其他果树树一样，有有着诸多多分叉（如如图3所示就就是一棵棵果树），在在每个分分叉处生生长着果果实，自自然Niilehh和Nixxeddd的食物物就是这这些果实实了！他他们准备备把果树树分成两两部分，每每个虫虫虫得到各各自的一一部分，两两分果树树的方法法就是选选择一个个

37、分叉点点，虫虫虫将他们们咬断（自自然分叉叉点上的的果实也也被扔掉掉了），这这样果树树就被分分成两部部分（每每个部分分不一定定是连在在一起的的）：分分叉点上上面的部部分和分分叉点的的下面部部分。NNileeh和Nixxed就就会各自自选一个个部分吃吃啦！比比如对于于左边这这棵树，如如果他们们咬掉蓝蓝色的果果子，那那么就被被分为红红色和黄黄色的两两个部分分。考虑到被咬咬掉的果果子会被被浪费，他他们想尽尽可能地地减少浪浪费，于于是虫虫虫给每个个果子一一个美味味值，对对于每个个果子，他他们决定定计算如如果咬掉掉这个果果子，上上面部分分、下面面部分和和从树根根到这个个分叉点点的路径径中比这这个果子子更美

38、味味的果子子各有多多少个。他他们以此此来选择择最终要要被咬掉掉的果子子是哪一一个。遗遗憾的是是果树可可能很庞庞大，而而小虫几几乎是不不会计算算的，身身为程序序员的你你帮帮他他们吧。【输入格式式】输入文件第第一行是是一个整整数n(n=1055)表示示树的分分叉数（包包括树根根）输入文件的的第i行一个个数pii，表示示分叉ii的上一一级分叉叉的编号号(piii)。(号分叉叉即树根根，它没没有上级级分叉点点）输入文件的的第n+i(11=ii=nn)行一一个正数数ai,表示生生长在ii号分叉叉上的果果实的美美味值。（每每个果子子的美味味值不相相等）【输出格式式】输出共n行行，每行行三个数数，分别别表示

39、咬咬掉第ii个果实实后上面面部分、下下面部分分、从树树根到这这个分叉叉点的路路径中比比它美味味的果实实数。【输入样例例】411123413【输出样例例】2 0 000 0 000 3 110 1 11航线规划 NOI2005安徽省队选拔赛题目【题目描述述】对Samuuel星星球的探探险已经经取得了了非常巨巨大的成成就，于于是科学学家们将将目光投投向了SSamuuel星星球所在在的星系系一一个巨大大的由千千百万星星球构成成的Saamueel星系系。星际空间站站的Saamueel III巨型型计算机机经过长长期探测测，已经经锁定了了Sammuell星系中中许多星星球的空空间坐标标，并对对这些星星球

40、从11开始编编号1、2、3。13245一些先遣飞飞船已经经出发，在在星球之之间开辟辟探险航航线。探险航线是是双向的的，例如如从1号星球球到3号星球球开辟探探险航线线，那么么从3号星球球到1号星球球也可以以使用这这条航线线。例如下图所所示：在5个星球球之间，有有5条探险险航线。A、B两星星球之间间，如果果某条航航线不存存在，就就无法从从A星球抵抵达B星球，我我们则称称这条航航线为关关键航线线。显然上图中中，1号与5号星球球之间的的关键航航线有11条：即即为4-5航线线。然而，在宇宇宙中一一些未知知的磁暴暴和行星星的冲撞撞，使得得已有的的某些航航线被破破坏，随随着越来来越多的的航线被被破坏，探探险

41、飞船船又不能能及时回回复这些些航线，可可见两个个星球之之间的关关键航线线会越来来越多。假设在上图图中，航航线4-2（从从4号星球球到2号星球球）被破破坏。此此时，11号与5号星球球之间的的关键航航线就有有3条：1-3，3-44，4-55。小联的任务务是，不不断关注注航线被被破坏的的情况，并并随时给给出两个个星球之之间的关关键航线线数目。现现在请你你帮助完完成。输入：第一一行有两两个整数数N，M。表示示有N个星球球（1 N 3300000），初初始时已已经有MM条航线线（1 MM 10000000）。随随后有MM行，每每行有两两个不相相同的整整数A、B表示在在星球AA与B之间存存在一条条航线。接

42、接下来每每行有三三个整数数C、A、B。C为1表示询询问当前前星球AA和星球球B之间有有多少条条关键航航线；CC为0表示在在星球AA和星球球B之间的的航线被被破坏，当当后面再再遇到CC为1的情况况时，表表示询问问航线被被破坏后后，关键键路径的的情况，且且航线破破坏后不不可恢复复； CC为-1表示示输入文文件结束束，这时时该行没没有A,B的值值。被破破坏的航航线数目目与询问问的次数数总和不不超过4400000。输出：对每每个C为1的询问问，输出出一行一一个整数数表示关关键航线线数目。注意：我们们保证无无论航线线如何被被破坏，任任意时刻刻任意两两个星球球都能够够相互到到达。在在整个数数据中，任任意两个个星球之之间最多多只可能能存在一一条直接接的航线线。【输入样例例】5 51 21 33 44 54 21 1 550 4 221 5 11-1【输出样例例】13