自创试题解题报告-lzx

寒假作业寒假作业 自创试题自创试题 解题报告解题报告 K2002 12 李子星 第一题 金链 第二题 公路建设 第三题 迷宫 第四题 Number 第一题第一题 金链金链 将这道题的题意看清 就知道题目的意思其实就是要我们求 长度为 n 的链条怎么分段 使得 1 分出的各个子链的长度可以凑成 1 到 n 之间的每一个整数 这样就可以保证店主在第 i 天拥有 i 个金环 即每一天店主都不会多收或少收房钱 2 分出的子链中 长度为 1 的子链的段数 子链的总段数 div 2 3 分出的子链尽量的少 明确我们的目标后 就要向目标进攻 我们采用构造法 构造 关卡数 当 n8 时 看下面 如果我们只取出 2 个金环 那么我们最多只能得到 5 段子链假设长度不限的话 我们使另 外的三段子链长度分别为 3 6 12 那么我们就可以得到 1 23 之间的所有整数 1 2 3 4 5 6 7 8 9101 1 121314151617181920212223 11 1 31 3 1 1 3 61 6 1 1 6 3 6 1 3 6 1 1 3 6 121 12 1 1 12 3 12 1 3 12 1 1 3 12 6 12 1 6 12 1 1 6 12 3 6 12 1 3 6 12 1 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若相连则找到路径上权值最大的一条边 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 第三题第三题 迷宫迷宫 这道题其实跟欧拉回路有关 因为我们可以传送 所以我们其实可以忽略图的连通性的问 题 我们要注意下面几点 1 我们的目的是杀掉所有的敌人 最多的就是所有的 对于没有敌人的道路 我们完全 没有必要考虑 2 对于有敌人的道路 我们最好是一次遍历 一条路不需要走两次 我们可以传送 而 传送的时间一定小于走过去的时间 3 我们必须从起点走到终点 于是问题就是 通过 传送 在顶点之间连最少的边 构造一个欧拉回路 所以 1 将不是起点和终点的点称为 中间点 起点和终点称为 非中间点 若要构造一条 起点出发 终点结束的欧拉回路 就一定要使 非中间点 的度为奇数 中间点 的度为偶数 2 由 1 可知 对于每一个节点 我们只需要统计它的度的奇偶性 而不要知道他与其他 哪个节点连了边 然后统计奇偶性不正常的点的个数 x 而奇偶性不正常的点的个数 一定是偶数 看证明点击这里 所以一定可以配成 x 2 对 所以 x 2 就是要传送的次 数 3 对于有敌人的道路 我们都要走且仅走一次 我们只需要知道有敌人的道路的总长就 可以了 4 每个敌人都只会也必须被我们杀掉一次 所以我们只要知道迷宫中敌人的总数乘以 TK 的结果 而不要管他们分布在哪里 于是 看似复杂的题就变成简单的统计题了 时间复杂度为 O m 空间只需要存 10000 个 boolean 每个点的奇偶性 就可以了 前面说到 图中奇偶性不正常的点的个数一定是偶数 证明如下 因为所有点的度的总和一定为偶数 所以奇点的个数一定是偶数 当这偶数个奇点有奇数个是 非中间点 时 奇偶性不正常的点就有 当这偶数个奇点有偶数个是 非中间点 时 奇偶性不正常的点就有 所以奇偶性不正常的点总有偶数个 奇数 奇数 偶数 奇数个奇点为 中间点 这些点都是奇偶性不正常的 奇数个偶度的 非中间点 它也是奇偶性不正常的 偶数 偶数 偶数 奇数个奇点为 中间点 这些点都是奇偶性不正常的 奇数个偶度的 非中间点 它也是奇偶性不正常的 第四题第四题 Number 这是一道简单的递推题 用 f i 表示 i 位 K 进制数的总数 那么就有 f i f i 1 f i 2 K 1 怎么解释这个方程呢 f i 也就是 i 位 K 进制数的总数应该等于 第 i 1 位为 0 与第 i 1 位不为 0 的情况的和乘以第 i 位的情况数 1 k 1 第 i 1 位为 0 的情况应