savage

题解

/ 注册

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

题解 | 买铅笔-NOIP2016普及组复赛

算法知识点: 模拟，枚举复杂度：解题思路：由于老师只能买一种包装的铅笔，因此直接枚举买哪种包装，然后求出最少需要买多少包，才能使总数量不少于即可。其中是老师需要买的铅笔总数。 C++ 代码： #include <cstdio> #i...

买铅笔题解 NOIP2016普及组复赛

2019-09-07

2 1292

题解 | 寻宝-NOIP2012普及组复赛

算法知识点: 枚举，模拟复杂度：解题思路：模拟从第层走到第层的整个过程，每次找出从当前房间开始第个有梯子的房间即可。最终每层遇到的之和就是答案，不要忘记将答案对取模。 C++ 代码： #include <cstdio>...

题解寻宝 NOIP2012普及组复赛

2019-09-07

0 1298

题解 | 接水问题-NOIP2010普及组复赛

算法：模拟复杂度：解题思路：从前往后依次考虑队列中的每个同学，每个同学会去当前结束时间最早的水龙头处接水。由于本题数据范围较小，因此可以直接循环一遍所有水龙头，求出当前结束时间最早的水龙头编号。那么我们就将当前同学安排在这个水龙头的位置上，然后将该水龙头的结束时间加...

题解接水问题 NOIP2010普及组复赛

2019-09-07

0 1128

题解 | 观光公交-NOIP2011提高组复赛

算法知识点: 贪心，递推复杂度：解题思路：这道题目的信息较多，我们先将其整理一下。首先预处理出每个站台的发车时间，即最后一个到达站台i的时间。然后预处理出从每个站台下车的人数。接下来求出车到达每个站台的时间，那么每个乘客的旅行时间就是，其中是乘客的终点站，...

观光公交题解 NOIP2011提高组复赛

2019-09-07

0 1284

题解 | 积木大赛-NOIP2013提高组复赛

算法知识点: 差分,贪心复杂度：解题思路：我们逆向思考：假设给定了每块积木的高度，每次可以将某一段区间中的所有高度减一，问最少操作多少次可以将所有高度变成0。原序列是： , 其中。构造差分序列： ... ...

积木大赛题解 NOIP2013提高组复赛

2019-09-07

4 875

题解 | 国王的游戏-NOIP2012提高组复赛

算法知识点: 贪心复杂度：解题思路：我们先给出做法，再证明其正确性。做法：直接将所有大臣按左右手上的数的乘积从小到大排序，得到的序列就是最优排队方案。证明：我们记第个大臣左手上的数是，右手上的数是。假设当前的排队方案不是按从小到大排序的...

题解 NOIP2012提高组复赛国王的游戏

2019-09-07

0 1110

题解 | 合并果子-NOIP2004提高组复赛

算法知识点: 贪心,哈夫曼树,堆,优先队列复杂度：解题思路：经典哈夫曼树的模型，每次合并重量最小的两堆果子即可。 C++ 代码： #include <iostream> #include <algorithm> #in...

合并果子题解 NOIP2004提高组复赛

2019-09-07

6 877

题解 | 小凯的疑惑-NOIP2017提高组复赛

算法知识点: 数论时间复杂度：解题思路：结论题：如果均是正整数且互质，那么由不能凑出的最大数是。 C++ 代码： #include <cstdio> #include <cstring> #i...

题解小凯的疑惑 NOIP2017提高组复赛

2019-09-06

2 897

题解 | 组合数问题-NOIP2016提高组复赛

算法知识点: 前缀和，组合数复杂度：解题思路：首先通过组合恒等式将所有模的余数预处理出来。然后递推出前缀和：，表示中的倍数的个数。查询时直接查表即可。 C++ 代码： #include <cstdio> ...

题解组合数问题 NOIP2016提高组复赛

2019-09-06

0 965

题解 | 计算系数-NOIP2011提高组复赛

算法知识点: 组合数，二项式定理复杂度：解题思路：由二项式定理：因此，的系数是。时间复杂度分析: 计算的瓶颈在计算上，对于分母中每个数都需要做一次快速幂，因此总时间复杂度是。 C++ 代码： #include&...

计算系数题解 NOIP2011提高组复赛

2019-09-06

0 726