savage level
获赞
1170
粉丝
57
关注
8
看过 TA
218
女
南阳理工学院
2018
IP属地：未知
暂未填写个人简介
私信
关注
发布(489) 评论 刷题 收藏
2019-09-11 14:14
南阳理工学院
题解 | FBI树-牛客假日团队赛14A题
题目描述           我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。   FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：   1) T的根结点为R，其类型与串S的类型相同；   2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。   现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出...
0 点赞 评论 收藏
分享
2019-09-09 11:45
已编辑
南阳理工学院
题解 | 瑞士轮-NOIP2011普及组复赛
算法知识点: 排序,多关键字排序,归并   复杂度：   解题思路：   此题中的排序是多关键字排序：总分较大者优先，编号较小者优先。   初始时先将所有参赛队员排序，这里可以采用快速排序，时间复杂度是 。   接下来每轮比赛结束后，均需要将所有选手重新排序。    如果采用快速排序，则总时间复杂度是 ，会超时；  可以发现每次比赛会将 个同学的分数加0，另外 个同学的分数加1，所有加0的 个同学内部是有序的，加1的 个同学内部也是有序的，因此这一步需要我们将两个有序序列合并，使用二路归并算法即可，每次归并的时间复杂度是 。   C++ 代码：  #include <cstdio>...
0 点赞 评论 收藏
分享
2019-09-09 11:47
已编辑
南阳理工学院
0 点赞 评论 收藏
分享
2019-09-09 11:48
已编辑
南阳理工学院
题解 | 多项式输出-NOIP2009普及组复赛
算法知识点: 字符串处理，模拟   复杂度：    解题思路：   从前往后依次处理每一项，依次考虑符号、系数、x、x的次数：    如果系数是0，则直接continue；  如果不是第一个非零项，且系数是正的，则输出'+'；如果系数是负的，则无条件输出'-'；  如果系数的绝对值不是1，或者是常数项，则输出系数的绝对值；  如果次数不为0，则输出x  如果次数大于1，则输出次数   C++ 代码：   #include <iostream> #include <algorithm>   using namespace ...
0 点赞 评论 收藏
分享
2019-09-09 11:50
已编辑
南阳理工学院
0 点赞 评论 收藏
分享
2019-09-09 11:51
已编辑
南阳理工学院
题解 | 宝藏-NOIP2017提高组复赛
算法知识点: 状态压缩DP   复杂度：   解题思路：   参考这篇题解所写。   状态压缩DP，下文中i是一个 位二进制数，表示每个点是否存在。   状态f[i][j]表示：    集合：所有包含i中所有点，且树的高度等于j的生成树  属性：最小花费   状态计算：枚举i的所有非全集子集S作为前j - 1层的点，剩余点作为第j层的点。 核心： 求出第j层的所有点到S的最短边，将这些边权和乘以j，直接加到f[S][j - 1]上，即可求出f[i][j]。   证明： 将这样求出的结果记为f'[i][j]    f[i][j]中花费最小的生成树一定可以被枚举到，因此f[i][j] >= ...
0 点赞 评论 收藏
分享
2019-09-09 11:52
已编辑
南阳理工学院
题解 | 换教室-NOIP2016提高组复赛
算法知识点: 数学期望,动态规划   复杂度：   解题思路：   状态表示：    f[i][j][0]表示前i个课程，申请换了j次，且最后一次没申请换的最小期望长度  f[i][j][1]表示前i个课程，申请换了j次，且最后一次申请交换的最小期望长度   则f[i][j][0]在如下两种情况中取最小值即可：    第i - 1个课程没申请交换，最小期望是f[i - 1][j][0] + d[a[i - 1]][a[i]]  第i - 1个课程申请交换，最小期望是f[i - 1][j][0] + d[a[i - 1]][a[i]] * (1 - p[i - 1]) + d[b[i - 1]]...
0 点赞 评论 收藏
分享
2019-09-09 11:52
已编辑
南阳理工学院
题解 | 愤怒的小鸟-NOIP2016提高组复赛
算法知识点: 状态压缩DP   复杂度：   解题思路：   一般抛物线方程：   题目中的抛物线有两个特点：    过原点, 即  开口向下，即   因此抛物线方程为：，有两个未知数，因此两点即可确定一条抛物线。   因此最多有 个不同的抛物线。接下来求出所有不同的抛物线，及其能覆盖的所有点的点集。   此时问题变成了经典的“重复覆盖问题”，即给定01矩阵，要求选择尽量少的行，将所有列覆盖住。   f[i]表示当前已经覆盖的列是i时的最小行数。   转移时随便找到当前未被覆盖的某一列 ，然后枚举所有包含 的行j来选择即可。   即：f[i | j] = min(f[i | j], f[i] ...
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了：
牛客网
牛客网在线编程
牛客网题解
牛客企业服务