信息学国家集训队作业solution2

1、Solution to partial problems of MIPTGuo HuaIDBrief DescriptionBrief SolutionP000/P001/P002/P003求一个竞赛图中的曼哈顿链在已知图表信息的情况下，任取一个点为初始链，对于任意一个非链上结点有三种情况：1) 到起点有边，此时添加为链首；2) 终点到它有边，此时添加为链尾；3) 否则，必然存在一个 i，使得 Pi->u and u -> Pi+1，可以二分找到这个 i，将 u 添加进入链P004给出一些二元组(mi, si)，满足 si < sj 则 mi < mj。要求出一个最长的

2、序列使得对于任意 k，有 sigmami <= sk(1 <= I < k)贪心P005/P006判断一个数字是否能够被表示为三个平方数的和枚举P007求一个三维立方体的最大子立方体枚举P008判断一个括号序列是否合法栈P009求 Fibonacci 数列第 n 项高精度P010/最大匹配P011/P012/P013有 n 个有序三元组(xi, yi, zi)，有 xi <= yi <= zi。定义偏序关系>，i> j 当且仅当 xi >= xj, yi >= yj, zi >= zj。求最小链覆盖数。希望，有后继的结点最多，这意味着

3、最小链覆盖最小。即转化为一个最大匹配问题。最长反链问题 = 最大匹配问题P014给一个字典，每个单词有一个权值。求一个长度为 N 的字符串，使得包含的单词的权和最大自+DPP015找一个最大空心子矩形枚举P016找两个不相交的空心子矩形，使得总面积最大枚举一个中心线，两边分别统计一下P017/模拟P018有一个分母不大于 N 的最简把分母为2N 的所有分数进行二分是最有算法。分数，大于 0 小于 1，你可以询问“这个数是否小于 r”，给出 N，问 情况下，最少要问多少次才能得到这个 N分数的个数就是所有欧拉函数的和。P019/P020求最小生成树范围很小，硬搞P021计算一个分数表达式所需要占

4、用的屏幕大小递归P022自匹配问题这个题目直接递推P023给出一个些线段和两个点，判断是否存在连接这两个点的不与任何线段相交的曲线离散交点，相当于是让任意两条线断不相交。 存在，当且仅当存在一个中空多边形包含两点，当且仅当对于任何一个多边形（闭合曲线），该两点作下垂线的交点数奇偶情况相同P024表达式求值/P025/求导P026给出 N，通过尽量少的操作将其变成 0，操作有三类：+1，-1，/2（对于偶数）贪心，对于偶数/2，对于 mod 4 = 1 或者 N = 3 的-1，剩下的+1，不难证明其正确性P032给出平面上一些圆，要求找出一条直线，使得该直线经过的圆最多（有公共点就可以）极限法

5、，计算所有两圆切线即可P034看过了周源的解题。而我得到的是另一种算法。算法中心在于表示整个凸现的结构。1) 对于每个点 p，向左找出第一个比它高的点 Lp以及右边第一个比它高的点 Rp；2) 显然 LpRp可能形成一个 pond，这个 pond 为 extendedp；3) 容易证明，extendedp和所有可能的pond是一一对应的；4) LTp为(Lp, p)中最高的点，显然， (Lp, p)是一个可能的 pond，并且等于 extended(LTp)；同样的有 RTp；5) 容易得到一个二叉树结构，仔细分析会发现，这个二叉树结构完美的反应了所有 pond 之间的关系；6) 接下来，略P

6、035棋盘上有一些骑士和一个 King，你需要用最少的移动次数把所有的棋子移动到同一个格子中间去，如果 King和骑士在同一个格子就可以和骑士 ，只算骑士的移动；枚举，需要注意到的是，King 与骑士相遇的地方必然是在 King 发出的两条对角线上或者与对角线相差不超过一格；否则，还不如让骑士负责来回接送JP041给出一个 2*2*2 的魔方，用最少的旋转次数使得所有面上的数字相同。此题没有 AC >_<两种思路： BFS：先说状态数，24！/ (4!)6，太大了两个Cube 可能本质一样，只是颜色是一个置换，去掉这样的重复可以使状态 /= 720；采取双向广搜，理论上是状态到达

7、0.5 次方；考虑 Cube 的翻转、旋转 /= 24总的算起来状态数可以接受，未写程序，不知实际运行效果；DFS：根本找不到好的估价，没想法P048国际象棋中白王+后对黑单王，要求白王 。让黑王坚持尽量长的时间。广搜啊P054直接按照 023 改的P058猜数 。假设 Alise 要用 1, 2, , N 各ni 次，写程序让猜测的总次数尽量少。每次程序重启（无 的）哈夫曼树P063给一个棋盘做尽量少的修改使它对称。棋盘上有 3 类位置：1 个点互相对称，2 个点互相对称，4 个点互相对称；用一个二元组（p，q）描述一个 p 个点互相对称的位置，上面已经存在 q 个 jewel 的位置。用这

8、样的语言重复这个题目：给出一些二元组（p, q)，p = 1, 2, 4, 0 <= q<= p；从中选出一些二元组，使得 sigmap =N，并且 sigmaq最大。这个问题看似需要背包来解决，实则：先不考虑(1, q)；如果 N mod 4 = 0，那么选取的(2, q)必然是偶数个，也就是说，(2, q)必然是成对选取的；按照这个 ，如果选两个(2, q)，必然是选 q最大的两个二元组，依次类推；那么， 可以把所有的(2, q)转化成(4, q)，每次挑选两个 q最大的二元组(2, q1) (2, q2) 合并成(4, q1+q2)即可。如果 N mod 4 = 2，那么先挑

9、一个 q 最大的(2, q)，剩下的合并就好了如此， 只需要面对的就是(4, q)，相信对于这样的贪心 是可以轻松解决的 JP066计算连通块的数目，范围相当采取 WC2005，dface 类似的并查集，将空间复之大杂度降低为 O(N)P073给 n 个点和点 P，选一些点组成多边形，使得 P 在它的内部。多边形各边都 过 K，要求多边形周长尽量小。事实上， 需要找出一个环，从 P 向 射线恰好经过奇数次用最短路算法来实现，对于每个点 u 分拆为两个点 Xu, Yu，分别表示被 P 的射线经过了偶数次和奇数次后到达 u，那么 即为 MinDis(Xu, Yu)P074判断 n 个球是否有公共点

10、枚举三个圆算一下交点，判断这个交点是不是在所有圆内部，这个条件很充分了，当然还有一些细节P095判 断 一 个 有 向 图 是 否 为 PS-graph. 即可以从一条边经过若干次 double 和 split 操作得到。反向模拟就可以了1. 如果有重边就缩成一条；2. 如果有一个点入度为 1 出度为 1 就缩掉需要用平衡树模拟P096判 断 一 个 有 无 图 是 否 为 PS-graph. 即可以从一条边经过若干次 double 和 split 操作得到。反向模拟就可以了1. 如果有重边就缩成一条；2. 如果有一个点度为 2 就缩掉需要用平衡树模拟P109给一些半平面（包含分界线），从中选尽量少的半平面覆盖整个平面。n<=100如果有解的话，至多只需要 3 个半平面就成了，所以这个题目根本就是枚举啊P115给一个由 dot, hyphen 和 0 组成的表达式，其中 0 表示未知（可能是 dot 也 可 能 是 hyphen）。恢复尽量多的 0 使得所有连续 hyphen 的长度为给定值。比