savage

题解

/ 注册

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

题解 | 金明的预算-NOIP2006提高组复赛

算法知识点: DP，分组背包问题复杂度：解题思路：可以将每个主件及其附件看作一个物品组，记主件为，两个附件为,则最多一共有4种组合：这四种组合是互斥的，最多只能从中选一种，因此可以将每种组合看作...

题解金明的预算方案 NOIP2006提高组复赛

2019-09-07

2 693

题解 | 过河-NOIP2005提高组复赛

算法知识点: 动态规划，数学复杂度：解题思路：如果不考虑的范围，那么就是一道简单的DP问题：状态表示表示走到位置，踩到的石头个数的最小值；状态计算 , 其中表示第个位置是否有石头，在到之间。那么当很大时该...

题解过河 NOIP2005提高组复赛

2019-09-07

0 996

题解 | 合唱队形-NOIP2004提高组复赛

算法知识点: 线性DP，最长上升子序列复杂度：解题思路：假设最优解的中心是第个人，则一定是以结尾的最长上升子序列。同理，也一定是以结尾的最长上升子序列。因此可以先预处理出：从前往后以每个点结尾的最长上升子序列长度；从后...

题解合唱队形 NOIP2004提高组复赛

2019-09-07

0 801

题解 | 加分二叉树-NOIP2003提高组复赛

算法知识点: 区间DP，二叉树的遍历复杂度：解题思路：状态表示：表示中序遍历是的所有二叉树的得分的最大值。状态计算：，即将表示的二叉树集合按根节点分类，则根节点在时的最大得分即为，则即为遍历所取到的最大值。在计算每个状态的过程中，记录每个区间的最...

题解加分二叉树 NOIP2003提高组复赛

2019-09-07

0 674

题解 | 信息传递-NOIP2015提高组复赛

算法知识点: 图论,找环复杂度：解题思路：由题意，我们需要在所有点的出度均是1的有向图中，求出最小环的长度。首先我们考虑一下所有点的出度均是1的有向图的性质：即一个环上挂着很多路径，而且不管从哪个点出发，最终都会走到某个环上。因此我们可以借助于栈结构来找出...

信息传递题解 NOIP2015提高组复赛

2019-09-07

0 822

题解 | 最优贸易-NOIP2009提高组复赛

算法知识点: SPFA 复杂度：解题思路：先求出：从走到的过程中，买入水晶球的最低价格；从走到的过程中，卖出水晶球的最高价格；然后枚举每个城市作为买卖的中间城市，求出的最大值即可。求和时，由于不是...

题解最优贸易 NOIP2009提高组复赛

2019-09-07

3 905

题解 | 双栈排序-NOIP2008提高组复赛

算法知识点: 二分图,栈,染色法,贪心复杂度：解题思路：如果只有一个栈，则整个操作顺序是固定的：从前往后遍历每个数，每次先将当前数压入栈中，如果后面的所有数均比栈顶元素大，则将栈顶弹出，否则栈顶不能被弹出。因此，我们只需考虑将每个数分配给哪个栈即...

双栈排序题解 NOIP2008提高组复赛

2019-09-07

1 1092

题解 | 神经网络-NOIP2003提高组复赛

算法知识点: 拓扑排序复杂度：解题思路：这道题目需要注意输入层的初始状态不用减去阈值。为了保证使用每个点的状态去更新其他点时，该点的状态已被计算完毕，我们需要使用拓扑序来计算每个点的值。计算完拓扑序列后，我们只需从前往后递推一遍，即可求出每个点的最终状态值。...

题解神经网络 NOIP2003提高组复赛

2019-09-07

0 916

题解 | 纪数问题-NOIP2013普及组复赛

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

题解 NOIP2013普及组复赛记数问题

2019-09-07

0 748

题解 | 质因数分解-NOIP2012普及组复赛

算法：枚举,数学复杂度：解题思路：所有约数都是成对出现的：如果是的约数，那么也是的约数。我们可以只枚举较小的约数，然后计算出较大的约数即可。那么需要枚举的范围满足：，则。因此只需要枚举次。 C++ 代码： #include &...

题解 NOIP2012普及组复赛质因数分解

2019-09-07

0 802