集训队作业第一阶段ahyangyis2nd contest

1、Overview题目名称寻找 yyyyCosmic StackerWAV-MIDI题目代号Prob1Prob2Prob3Prob4输入文件名Prob1.inProb2.inProb3.inProb4_0.in Prob4_9.in输出文件名Prob1.outProb2.outProb3.outProb4_0.out Prob4_9.out每个测试点时限3 秒2 秒10 秒N/A测试点数目10101010每个测试点分值10101010是否有部分分无无无有题目类型传统传统传统结果提交1、寻找 YYYY 跑到了一个森林里藏了起来。这下可急坏了 BB。“Y”是这样的形状：以一个点为“根”，根上连接着三

2、条长度不为 0 的链，且这三条链除了根以外没有其它公共顶点。顾名思义，“YY”就是两个不包含公共节点的“Y”了。不是一个Y是一个 Y 是一个Y不是一个Y是一个 YY不是一个YY任务就是，给定一个森林（森林就是一张无环的无向图），让你在里面找到 YY。BB 认真观察了一下森林的形状，发现里面包含了好多 YY。好在还有一个线索，YY 的体积比较大，所以各条边长度和最大的 YY 最可能是 BB 要找的 YY。别忘了 YY 喜欢去“大榕树”，因此有可能整个森林就是一颗树。 YY 的两个“Y”可能分布在两棵树上，也可能在同一棵树上。 输入格式：第一行两个正整数N 和 M，分别表示森林里的点数和边数。0M

3、N=106。后面 M 行，每行有三个整数 A,B,C，表示 A 和 B 之间有一条长度为 C 的边。顶点到 N。边的长度不超过 103。输出格式：从 1输出文件只有一行，这行只有一个正整数，即森林中 YY 的各条边长度和的最大值。如果森林中没有YY，输出一行：“POOR BB”（不包括引号）。样例输入：11 91 2 33 4 64 5 54 6 56 7 36 8 48 9 39 10 99 11 7样例输出：38样例说明：样例输入输出对应下图：5365 43379寻找 YY的题解算法一（我出此题时的算法，即标程算法）首先，毋庸置疑的，森林当然是一棵棵树考虑，要么 YY 出现在某棵树上，要么

4、两个 Y 分别出现在两棵树上，不管是哪一种情况，在每棵树上的情况考虑完以后就不难处理了。因此只需要考虑一棵树的情况。一棵树上的Y：对每个节点 i 计算 3 个值 Ai,Bi,Ci，分别表示以下 3 种情况的总长度：iiiiBCAA 是向下引了一条链，而 B 是已经向下引了两条链，并且上面还可以连接。C 是自己的儿子中连出了一个 Y 型，但并不与自己相连接，或虽然与自己相连接，确不能继续向上连。 转移的过程：A：由某个儿子的A 得到。即 Ai=maxAj+disti,j,fatherj=i。B：可以由两个儿子各拉一条链（即两个A）得到，也可以由某个儿子的 B 得到。C：可以由 3 个儿子各拉一条

5、链（即 3 个 C）得到，或者一个儿子的 B 及一个儿子的A，或者一个儿子的 C 得到，当然，如果是由一个儿子的 C 得到，是不能加上这一条边的长度的。Croot还是 maxBroot,Croot？后者肯定不对，因为有这样的情最后的结果是况也算作 B：root但是如果选择前者，好像前者并不能涵盖所有情况。的确，刚才对 C 的定义是：已经形成了一个 Y，且不能往上继续连接。因此如果“还能继续向上连接”就不被考虑了。解决办法就是，把这种情况也考虑进去！小结：3 个状态，递推关系：如果觉得这个算法不算过于的话，那么就开始直接的扩展吧！如果在一个树中出现了两个Y，可以分 6 种情况，前 3 种与刚才介

6、绍的一致，后三种 D，E，F 分别类似于 A，B，C 但中都比原来多包含了一个完整的Y。AAj+disti,jBAj+disti,j+Ak+disti,kBj+disti,jCAj+disti,j+Ak+disti,k+Al+disti,lBj+disti,j+Ak+ disti,kBj+disti,jCj它们的递推关系：这个动态规划的复杂程度大大超出了来。应该注意以下几点：的预期，然而在关系之后还是有可能写得出1、n 很大，要注意时间复杂度要控制在 O(n)。注意到需要的无非是 Aj+disti,j，Bj+disti,j，Cj，Dj+disti,j，Ej+disti,j，Fj最大的几个儿子节

7、点，更准确的说，仅仅需要算出这 6 个数前 4 名的儿子节点。2、要注意儿子的问题，上面给出的各个式子中 j,k,l,m 都表示 i 的不同儿子节点，因此转移的时候不能选取重复的儿子，比如选择了Aj+disti,j，又选择了 Bj+disti,j，这显然是错误的。为此，需要专门使用循环来判断。好在只保存前 4 名，这都只是常数，而且可以进行一些必要的常数优化。3、和第 4 次比赛的 l需要使用栈模拟等办法。s 一样：1000000 个节点的树如果使用递归遍历会栈溢出。不难看出，如果只有一个 Y 的话，这样的动态规划还算令人接受，但是有两个 Y 的情况就让人受不了了。能不能避免考虑两个Y 的情况

8、呢？是能！DCj注：Cj不能直接往上连接，但是 j 的父亲 i 可以继续往上连接以第二个yDj+disti,jAj+disti,j+Ck+disti,kEEj+disti,jAj+disti,j+Ak+disti,k+ ClAj+disti,j+Dk+disti,kBj+disti,j+Ck+disti,kFFjEj+disti,j注：这个的理由和 Ci可取 Bj+disti,j一样Cj+CkAj+disti,j+Ak+disti,k+Al+disti,l+CmAj+disti,j+Ak+disti,k+Dl+disti,lAj+disti,j+Ek+disti,kBj+disti,j+CkB

9、j+disti,j+Dk+disti,kAj+disti,j+Bk+disti,k+Cl+disti,l替代算法这个是样例中的主要的那棵树。可以看到，中间有一条没有被选取的边。而且，只要两个 Y在同一个树上，就必然会存在某个边，在删除这条边之后两个Y 属于不同的。这样，任何一个函数 f(i)就可以改成每条边(i,j)计算两个状态：f(i,j)和 f(j,i)。f(j,i)表示以 j 节点作为 i 的父亲节点时，以 i 为根的的f(i)。这样，只要对于每条边(i,j)计算 A(i,j), B(i,j), C(i,j), A(j,i), B(j,i), C(j,i)即可。然后，对于计算 maxC(

10、i,j)+C(j,i)，就是这个树上的两个 Y 的最大的总长度。：时间复杂度在情况是 O(n2)的！为什这个办法看似简洁，但是又遇到了一个新么？考虑一个度很大的结点 v，它的度数大到了与节点数 n 同阶。v那么对于每一个(i,v)，都需要分析所有的(v,i)才能得出。这样，时间复杂度就是 O(D2)=O(n2)的了。而事实上，我在制作数据的时候考虑了这一点，有不少数据点都强化了点的度数。而 O(n2)在时间上的缺陷也充分了出来。能不能找出一个既相对简洁，又能在 O(n)时间内完成的算法呢？还是能！算法二这个算法有点像冬令营中的例题 4 的子问题 2。不妨去参见那篇。不同点只是那篇是对Hash

11、函数的递推，而这里是动态规划的状态转移。简要地介绍一下，随便找一个节点作为根节点，然后dfs，则可以在O(n)时间内求出所有满足 dist(i)=dist(j)-1 且(i,j)E 的A(i,j),B(i,j)和 C(i,j)。换句话说，有了根之后，这棵树有了“上下”的概念，对于所有 i 在 j“上面”的状态已经可以计算出来了。然后再进行第二次 dfs，和第一次从同一个根节点出发。不同的是第一次 dfs 是后序的（处理完儿子节点才能再处理自身），而这一次是先序地先处理自己再处理儿子节点。第二次 dfs 时，每个节点 v 时对于所有与 v 相连的点 u，A(v,u), B(v,u)和 C(v,u

12、)都已被计算出了。这样，可以分别保存使 A(v,u), B(v,u)和 C(v,u)取到的前 4 大结果的 u。然后可以计算出所有的形如 f(u,v)的状态，因为可以4 名的列表里去掉和 v 有关的，得到“和 v 无关的前 3 名”，然后利用它算出 A(u,v), B(u,v)和 C(u,v)。这一步的总时间复杂度还是O(n)。至此，用可以接受的时间复杂度和编程复杂度完成了此题。尽管代码还是较长，但是出错的几率和思维的复杂程度都大大降低了。2、YY做了 AHOI2006 的 Board 一题，YY 觉得天昏地暗，回肠荡气，绕梁YY 也就想出了一个问题：对于一个完全二分图，有多少种不同的完备匹配

13、？结果 YY 发现这个问题太简单了，根本难不倒大家。YY 就改进了一下，对于一个有 2N 个节点的完全二分图，包含边数为 0，为 1，为 2为 N 的匹配分别有多少？YY 经过研究，发现此题存在 N 种解法，甚至可以交表！绝望的 YY 心想，这下子伤自尊了，题目没法出了。好在他这时突然又想起了 Board 那题。“对啊！”YY 说，“我在图中删去 M 条边，再问匹配分别有多少，这样就没办法交表了。”包含边数为 0，为 1，为 2为N 的于是，问题就出来了。可惜的是，这下子 YY 真的不会做了大家会做的话帮一下YY 吧。输入格式：第一行两个整数 N 和 M，定义见上文。1=N=500，0=M=对

14、于一个给定的局面，YY 想知道能否将所有圈圈消除。因此，请你设计一个程序帮他判断。注：1、消除的时候，只要移动后是三个同色圆环相套即可。可以是移动一个圆环到两个圆环的位置上，也可以是移动两个圆环到一个圆环的位置上。2、移动和消除造成的空隙会自动因为圆圈的移动而弥补。3、移动的时候，是先把待移动的圆圈拿起来（这时与它相邻的圆圈就接触了），然后再放在目的地上。因此，这样的移动会导致这一排全部消除：输入格式：每个输入文件包含了若干组数据。因此输入文件第一行有一个正整数 T，表示数据的组数。（1=T=10）。对于每组数据：第一行是两个正整数 N 和 C。表示现在一共有 N 个圆圈，包括了 C 种颜色。

15、1=N=15，1=C=5。后面有 N 行，第 i 行有两个正整数 Ai 和 Bi，Ai 表示这个圆圈的尺寸（0 是最小号的，1 是中等的，2 是那种最大的），Bi 表示这个圆圈的颜色（1=Bi MIDIYY 喜欢MIDI。MIDI 容量小，音质好，而且不会有讨厌的歌词（这也算是优点？）。因此，YY 超级喜欢听 MIDI。现在能弄到的音乐文件大多不是 MIDI 格式的，而往往是 MP3或者 WMA 格式的。YY 把它们处理成了 WAV 格式，希望你帮个忙。问题简化以后是这样的：认为 MIDI 中有K 种乐器，波形都是已知的。一段乐谱了若干个音符，整个音乐的波形就是各个音符的波形的叠加。这里，“波

16、形”都是由一连串的非负整数表示的。对于长度为 L 的一个波形，时刻 1、时刻 2时刻L 的波幅都是非负整数。相邻时刻之间的波形是一条线段（因此，比较两个波形是否相同只需要比较整数时刻的波幅是否相同即可）。在时刻 1 之前和时刻 L 之后的所有整数时刻的波幅都是 0。对于给定的音乐波形和乐器波形，请输出一段正确的乐谱，乐谱的长度应尽量短。输入格式：第一行一个K，表示乐器的种类数。后面一行是整个音乐的波形。然后 K 行是 K 种乐器的波形。每个波形的格式都是这样的：第一个数字表示这个波形的长度 L，后面 L 个非负整数，表示这个波形。为了保证有解，YY 保证存在某种乐器的波形是长度和幅度都为一。输

17、出格式：第一行一个N，即音符个数。（N MIDI题解首先，由于本题题目描述比较冗长，第一步要做的应该是理解题意。由题目描述不难发现，其实本题问题本身很简单，就是给定一些数字串，可以进行任意的偏移以后进行相加，而目标是用最少的数字串拼出给定的目标串。由于很显然不可能搜索出全部数据的结果，只能求助于近似算法。随机化贪心，作为兼具贪心的“智能”特点和随机化算法可以多次求解以求更优的特点的算法，成为选择。的最佳然后还有一些优化可以使用：1、虽然保证提供一个乐器的波形是 1 1，但是很显然这种乐器使用多了会使解变差，因此我们得到第一个来自的想法：尽可能先选择数字和比较大的串。2、从边缘入手。观察第 2 组，第 9 组等比较“稀疏”的数据的两端，不难发现很容易“猜”到应该选择哪些串效果比较好