savage

题解

/ 注册

全部文章 / 题解（共374篇）

题解 | 导弹拦截-NOIP2010普及组复赛

算法：枚举,排序复杂度：解题思路：先用第一个雷达包围所有点，然后不断缩小第一个雷达的半径，每次圆边缘的点会从圈内出来，我们用第二个雷达去包含它即可。枚举半径的方法：先将所有点按到第一个雷达的距离从大到小排序，依次枚举所有点所在的圆的半径即可。用第二个雷达去...

导弹拦截题解 NOIP2010普及组复赛

2019-09-07

2 1049

题解 | 数字统计-NOIP2010普及组复赛

算法：枚举复杂度：解题思路：直接枚举到中的每个数，再依次判断每一位是否等于即可。 C++ 代码： #include <cstdio> #include <cstring> #include <...

题解数字统计 NOIP2010普及组复赛

2019-09-07

0 773

题解 | 旅行-NOIP2018提高组复赛

算法知识点: 树的深度优先遍历，DFS，基环树复杂度：解题思路：如果是一棵树，则我们一定从1号点开始遍历，每次按编号从小到大的顺序遍历所有子节点，得到的DFS序列的字典序最小。这道题目给定的树还有可能是基环树，即树中有一个环。此时可以发现：不论如何遍历，我们一定...

题解旅行 NOIP2018提高组复赛

2019-09-07

0 876

题解 | 运输计划-NOIP2015提高组复赛

算法知识点: LCA，树上差分，二分复杂度：解题思路：二分时间，则原问题变成一个判定性问题：是否可以通过去掉一条边，使所有路径的总长度在以内。此时去掉所有长度大于的路径的最长公共边一定是最优的。那怎么找出所有公共边呢？我们可以将每条路径上的所有边加...

题解运输计划 NOIP2015提高组复赛

2019-09-07

0 923

题解 | 树网的核-NOIP2007提高组复赛

算法知识点: 二分，树的直径，贪心，树的遍历复杂度：解题思路：二分最小偏心距，判断在直径上是否存在一段长度不超过的路径，使得其余所有点到路径的距离小于等于枚举的值。接下来在直径上找到与的距离不超过的前提下，距离最远的节点，作为节点。类似地，在直径上找到与 ...

题解树网的核 NOIP2007提高组复赛

2019-09-07

1 746

题解 | 联合权值-NOIP2014提高组复赛

算法知识点: DFS，树的深度优先遍历复杂度：解题思路：距离为2的点对有两种：八字形和1字形。对于八字形：直接将当前节点的所有子节点两两配对的结果统计出来即可。这一步线性扫描一遍即可，不需要枚举。我们以求总和为例，求最大值类似。从前往后枚举子节点时维护变量 ...

联合权值题解 NOIP2014提高组复赛

2019-09-07

1 978

题解 | Mayan游戏-NOIP2011提高组复赛

算法知识点: 搜索，剪枝复杂度：解题思路：由于最多枚举 55 步，数据范围很小，因此直接暴搜即可。搜索顺序：依次枚举每一步选择哪个方块，向左右哪个方向移动。剪枝情况有三种：向右移动时，如果右侧的方块颜色和当前方块颜色相同，则剪枝。 ...

Mayan游戏题解 NOIP2011提高组复赛

2019-09-07

0 759

题解 | 靶形数独-NOIP2009提高组复赛

算法知识点: 搜索，剪枝复杂度：解题思路：在搜索时分别记录每行、每列、每个九宫格内当前未填写的数字有哪些。这里采用位运算来加速：每行、每列、每个九宫格内，分别用一个9位的二进制数来表示哪些数字可填。每个空格内所有可选的数字就是其所在行、列、九...

靶形数独题解 NOIP2009提高组复赛

2019-09-07

3 825

题解 | 传染病控制-NOIP2003提高组复赛

算法知识点: 搜索复杂度：解题思路：由于这道题目的数据较弱，且贪心算法均有反例，因此直接暴搜出所有切割方案，保留最小值即可。首先预处理出每一层的节点集合，以及每棵子树的大小。然后从第一层开始，依次枚举每一层中删除哪棵子树，枚举之后通过深度优先遍历，将整棵子...

题解传染病控制 NOIP2003提高组复赛

2019-09-07

0 935

题解 | 标题统计-NOIP2018普及组复赛

算法知识点: 字符串处理复杂度：解题思路：当用cin读入char类型时，会自动忽略空白字符，包括空格、制表符、回车等。因此可以直接利用这个特性，统计总共读入多少个非空白字符即可。 C++ 代码： #include <iostream>...

标题统计题解 NOIP2018普及组复赛

2019-09-07

14 1131