savage

题解

/ 注册

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

题解 | 子串-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

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

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

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

2019-09-07

0 822

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

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

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

2019-09-07

0 923

题解 | 跳石头-NOIP2015提高组复赛

算法知识点：二分，贪心复杂度：解题思路：如果长度可以满足，那么当长度小于时也可以满足，所以我们可以二分出最大的。剩下的问题是如何判断给定的情况下，能否最多拿走块石头，使得所有相邻两块石头之间的距离不小于。这一步可以贪心来做。从前往后扫描，并记...

跳石头题解 NOIP2015提高组复赛

2019-09-06

0 1352

题解 | 神奇的幻方-NOIP2015提高组复赛

算法知识点: 模拟复杂度：解题思路：直接按照题目给出的填数步骤模拟一遍即可。时间复杂度分析: 总共有 n2 个数，每个数只被填写一遍，所以总时间复杂度是。 C++ 代码 #include <iostream> using&nb...

题解神奇的幻方 NOIP2015提高组复赛

2019-09-06

0 767

题解 | 斗地主-NOIP2015提高组复赛F题

题目描述牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A 到K 加上大小王的共54 张牌来进行的扑克牌...

NOIP2015提高组复赛题解斗地主

2019-09-01

5 1649

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

题目描述有 n 个同学（编号为 1 到 n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为Ti的同学。 ...

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

2019-09-01

0 727

题解 | 神奇的幻方-NOIP2015提高组复赛D题

题目描述幻方是一种很神奇的 N*N 矩阵：它由数字 1,2,3,.....N x N 构成，且每行、每列及两条对角线上的数字之和都相同。当 N 为奇数时，我们可以通过下方法构建一个幻方：首先将 1 写在...

NOIP2015提高组复赛题解神奇的幻方

2019-09-01

0 664

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

题目描述公元 2044 年，人类进入了宇宙纪元。 L 国有 n 个星球，还有 n-1 条双向航道，每条航道建立在两个星球之间，这 n...

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

2019-09-01

1 775

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

题目描述有两个仅包含小写英文字母的字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串，然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串，请问有多少种...

NOIP2015提高组复赛题解子串

2019-09-01

2 917