寒假作业——自创试题——解题报告K2002_12李子星HYPERLINK\l"_【第一题】金链_1"【第一题】金链HYPERLINK\l"_【第二题】公路建设_2"【第二题】公路建设HYPERLINK\l"_【第三题】迷宫_1"【第三题】迷宫HYPERLINK\l"_【第四题】Number_1"【第四题】Number【第一题】金链将这道题的题意看清，就知道题目的意思其实就是要我们求：长度为n的链条怎么分段，使得：分出的各个子链的长度可以凑成1到n之间的每一个整数，这样就可以保证店主在第i天拥有i个金环，即每一天店主都不会多收或少收房钱分出的子链中，长度为1的子链的段数>=子链的总段数div2分出的子链尽量的少明确我们的目标后，就要向目标进攻：我们采用构造法。构造“关卡数”当n<8的时候，我们都可以用枚举知道：只要取出一个金环就可以了。n>8时，看下面：如果我们只取出2个金环，那么我们最多只能得到5段子链假设长度不限的话，我们使另外的三段子链长度分别为；3,6,12，那么我们就可以得到1~23之间的所有整数：1234567891011121314151617181920212223111313113616116361361136121121112312131211312612161211612361213612113612好了，光知道这些还没有用，我们必须要从中找到规律：2个1可以凑成1~2，3就不行了，于是我们最多只能增加一段长度为3的子链多加一个3可以将“最大可以凑成的数”从2上升到5，此时我们若还想提升“最大可以凑成的数”，最多只能增加一段长度为6的子链……直到我们增加了一段长度为12的子链，我们就再也不能提升“最大可以凑成的数”了（因为我们已经增加了3段了）。再看，我们用的子链的总长度也只有23，如果我们的金链总长还没有23是不是也只要取出2个金环就可以了呢？答案是肯定的。比如说金链总长为22的时候，我们只要将最后加进来的子链（长为12的那一段）的长度减去1，就可以了。其实，对于长度大于等于8且小于等于23的金链，取出两个金环都可以完成任务。3个金环可以达到的“最大可以凑成的数”等于63。像8，23，63这样的小于等于它和大于它至少要取出的金环数不同的数，就叫做“关卡数”。那么，关卡数要怎么求呢？我们又来看取出2个金环的情况：1，1可以凑成1~2，这时加一段长度为3的子链，1，1，3可以凑成1~5，这时加一段长度为6的子链1，1，3，6可以凑成1~11，这时加一段长度为12的子链……..也就是说取出x个金环的情况一定是：先加一段x+1，在加一段x+(x+1)，在加一段x+(x+1)+(x+(x+1))…..直到加了x+1次所以取出x个金环可以达到的“最大可以凑成的数”就等于(x+1)*2(x+1)-1，所以x个金环的“关卡数”就是(x+1)*2(x+1)-1，用Gate[x]=(x+1)*2(x+1)-1“关卡数”出来了，问题的解又是多少呢？不要紧，马上就出来了。对于长度为n的金链，我们只要求出i使得：Gate[i]<n<=Gate[i+1]那么，最少要取出的金环数就是i。当n=1016时，i=46，而Gate[47]不比1016大很多，因此我们只要求出这47个关卡数，然后保存在const里面就可以了，要注意的就是要用comp存。【第二题】公路建设这道题看起来很复杂，其实就是要求你对一个最小生成树进行动态维护。处理的方法如下：读入一条a到b的边之后，先不将这一条边加入图中，检查a到b之间是否有路径相连，>若相连则找到路径上权值最大的一条边e(u,v)>若e(u,v)的权值比新读入的这条边的权值要小或相等，则去掉新读入的边>若e(u,v)的权值比新读入的这条边的权值要大，则去掉e(u,v)，加入新读入的边>若不相连则直接将新读入的边这样，每次读入一条边后，仍能使图保持为最小树形图。这个算法的时空复杂度是多少呢？>时间复杂度每次读入一条边e(a,b)，要检查a,b之间是否有路径相连，我们需要一个深搜的过程>如果我们用链表的话，深搜的时间复杂为O(e)，而最小树形图中最多只有n-1条边，所以这个过程为O(n)级的然后我们要去边与加边，这都是小于O(n)级的，所以维护的时间复杂的是O(n)级的。因为有m要增加，我们总共要维护m次，所以总的时间复杂度为O(n*m)级的，这是可以承受的。>空间复杂度我们采用链表，只要存储边就可以了，最小树形图中最多只有n-1条边，所以空间复杂度为O(n)。【第三题】迷宫这道题其实跟欧