自创试题解题报告-lzx.doc

寒假作业——自创试题——解题报告
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之间的所有整数：
123456789101112131415161718192021222311
131
31
1
361
61
1
63
61
3
61
1
3
6121
121
1
123
121
3
121
1
3
126
121
6
121
1
6
123
6
121
3
6
121
1
3
6
12好了，光知道这些还没有用，我们必须要从中找到规律：
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)。

【第三题】迷宫
这道题其实跟欧