savage

题解

/ 注册

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

题解 | 宝藏-NOIP2017提高组复赛

算法知识点: 状态压缩DP 复杂度：解题思路：参考这篇题解所写。状态压缩DP，下文中i是一个位二进制数，表示每个点是否存在。状态f[i][j]表示：集合：所有包含i中所有点，且树的高度等于j的生成树属性：最小花费状...

题解宝藏 NOIP2017提高组复赛

2019-09-07

0 1004

题解 | 换教室-NOIP2016提高组复赛

算法知识点: 数学期望,动态规划复杂度：解题思路：状态表示： f[i][j][0]表示前i个课程，申请换了j次，且最后一次没申请换的最小期望长度 f[i][j][1]表示前i个课程，申请换了j次，且最后一次申请交换的最小期望长度则f[...

题解换教室 NOIP2016提高组复赛

2019-09-07

0 793

题解 | 愤怒的小鸟-NOIP2016提高组复赛

算法知识点: 状态压缩DP 复杂度：解题思路：一般抛物线方程：题目中的抛物线有两个特点：过原点, 即开口向下，即因此抛物线方程为：，有两个未知数，因此两点即可确定一条抛物线。因此最多有个不同的抛物线。接...

愤怒的小鸟题解 NOIP2016提高组复赛

2019-09-07

0 860

题解 | 子串-NOIP2015提高组复赛

算法知识点: 线性DP，前缀和复杂度：解题思路：状态表示：f[i, j, k]表示只用S的前i个字母，选取了k段，可以匹配T的前j个字母的方案数。状态计算：将f[i, j, k]表示的所有方案分成两大类：不用S[i]，则方案数是f[i - 1, j,...

题解子串 NOIP2015提高组复赛

2019-09-07

4 740

题解 | 乌龟棋-NOIP2010提高组复赛

算法知识点: 线性DP 复杂度：解题思路：状态表示：表示所有第种卡片使用了张的走法的最大分值。状态计算：将表示的所有走法按最后一步选择哪张卡片分成四类：第类为最后一步选择第种卡片。比如，则这一类的最大分值是。 C++ 代码： #...

乌龟棋题解 NOIP2010提高组复赛

2019-09-07

0 759

题解 | 传纸条-NOIP2008提高组复赛

算法知识点: 线性DP 复杂度：解题思路：状态表示：f[k, i, j]表示两个人同时走了k步，第一个人在 (i, k - i) 处，第二个人在 (j, k - j)处的所有走法的最大分值。状态计算：按照最后一步两个人的走法分成四种情况：两个人同时向...

传纸条题解 NOIP2008提高组复赛

2019-09-07

0 826

题解 | 矩阵取数-NOIP2007提高组复赛

算法知识点: 区间DP，高精度复杂度：解题思路：状态表示：表示将[i, j]这段数取完的所有取法的最大分值。状态计算：将所表示的所有取法分成两类：先取左端点。这一类的最大分值是，其中是第个数的值。先取右端点。这一类的最...

题解矩阵取数游戏 NOIP2007提高组复赛

2019-09-07

0 695

题解 | 回文日期-NOIP2016普及组复赛

算法知识点: 枚举,模拟复杂度：解题思路：由于只有八位数，而且回文串左右对称，因此可以只枚举左半边，这样只需枚举总共一万个数，然后判断：整个八位数构成的日期是否合法；是否在范围内 C++ 代码： #include &l...

回文日期题解 NOIP2016普及组复赛

2019-09-07

1 1109

题解 | 扫雷游戏-NOIP2015普及组复赛

算法知识点: 枚举复杂度：解题思路：依次枚举每个空格，然后统计八个方向上的相邻格子有没有地雷即可。 C++ 代码： #include <cstdio> #include <cstring> #include ...

扫雷游戏题解 NOIP2015普及组复赛

2019-09-07

1 1006

题解 | 比例简化-NOIP2014普及组复赛

算法知识点: 枚举，欧几里得算法，数论) 复杂度：解题思路：由于在100以内，因此可以枚举的所有组合，然后判断：是否互质；是否大于等于，并且最小 C++ 代码： #include <cstdio> #in...

比例简化题解 NOIP2014普及组复赛

2019-09-07

1 936