Blog

洛谷P1120 小木棍 搜索

huangkui 2017年8月14日 No Comments Problem, 未分类

题目链接:传送门 Description 乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。 现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。 给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

HAOI 2016 食物链(洛谷P3183) 记忆化搜索

huangkui 2017年8月14日 No Comments Problem, 未分类 ,

题目链接:传送门 Description 现在给你n个物种和m条能量流动关系,求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3……am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链

NOIP2003 加分二叉树(洛谷P1040) 区间DP

huangkui 2017年8月11日 No Comments Problem, 未分类 , ,

题目链接:传送门 Description 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数。 若某个子树为空,规定其加分为1,叶子的加分就是叶 […]

NOIP2008 传纸条(洛谷P1006) 双线程动规

huangkui 2017年8月9日 No Comments Problem, 未分类 , ,

题目链接:传送门 Description 小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个m行n列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者 […]

LCA总结

huangkui 2017年8月8日 1 Comment Algorithm, 未分类 , , , , , ,

这段时间一直在学习LCA的各种算法,下面就对LCA的各种算法进行一次总结: 问题概述 LCA(最近公共祖先)指的是在一棵树上两个节点的最近的公共祖先(这句话好像跟没说差不多),也就是深度最深的公共祖先。LCA的适用范围非常广,在许多较难的与树有关的题中都会需要用到。因此,掌握求LCA的方法是非常重要的。

树链剖分

huangkui 2017年8月8日 No Comments Algorithm, 未分类 ,

开始一直以为树剖是一个非常高大上的数据结构,怕学不会,学完之后发现树链剖分其实特别简单 问题概述 树链剖分(也叫轻重链剖分),是解决在树上进行区间修改、查询这一类问题的一个算法。事实上,树链剖分就是由两遍dfs预处理+其他数据结构(如线段树、树状数组等)构成的。以洛谷P3384为例,如果我们直接将每个节点按照dfs的顺序加入线段树中的话,每次修改或是查询都需要将u和v的路径之间所有的节点都处理一遍。但是如果我们现将这棵树进行特殊的编号,使得在查询 […]

区间神器——莫队

huangkui 2017年8月8日 No Comments Algorithm, 未分类

问题概述 在处理区间问题时,如果一类题目满足已知区间[latex][L,R][/latex]的答案后,我们可以[latex]O(1)[/latex]处理出[latex][L+1,R],[L-1,R],[L,R+1],[L,R-1][/latex]的答案,且可以离线处理的话,我们就可以用莫队算法在均摊时间复杂度为[latex]O(N ^{1.5})[/latex]的复杂度内解决此类区间问题。 为什么说它是区间神器呢?那是因为它的常数非常小,大多数区 […]

RMQ问题(ST表算法)

huangkui 2017年8月8日 No Comments Algorithm, 未分类 ,

问题概述   RMQ (Range Minimum/Maximum Query),即区间最值查询,是指对于一个长为n的序列A,回答m次询问区间[latex][l,r][/latex]的最大值或最小值。这种问题我们如果暴力枚举,当查询次数较多且范围较大时复杂度是不能被接受的。下面就来介绍一下一种比较高效且容易写的算法:ST表

Hello World!

huangkui 2017年8月8日 No Comments 未分类

经历了各种瞎折腾两三天之后,终于把这个博客建好了 希望今后能够继续坚持写博客,在OI这条道路上越走越远 #incldue<bits/stdc++.h> using namespace std; int main(){ puts(“Hello World!”); return 0; }

Page 13 of 13