回归梦想

未归档

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

全部文章 / 未归档（共539篇）

1143 Lowest Common Ancestor 甲级

题意：给出一棵二叉搜索树的前序遍历，问结点u和v的共同最低祖先是谁，利用先序遍历特点。二叉搜索树满足：节点的左子树只包含键小于节点键的节点。节点的键只包含节点的右键大于或等于子树的节点的键。左子树和右子树也必须是二叉搜索树。题解：样例： 6 3 1 2 5 4 8 7 根据题目要...

2020-12-02

0 313

1151 LCA in a Binary Tree 甲级

题意：给定前序遍历和中序遍历，问u和v的lca （先是中序，后是中序）题解：方法一：参考题解将树映射到一颗BST上，在BST上找到答案然后再映射回原本的树方法二：参考题解已知某个树的根结点，若a和b在根结点的左边，则a和b的最近公共祖先在当前子树根结点的左子树寻找，如果a和b...

2020-12-02

0 0

1148 Werewolf - Simple Version 甲级

题意：有n个玩家，有两个狼人，有两人说慌（其中一个为狼人一个为非狼人），找出狼人是谁？题解：暴力枚举先枚举i和j为狼人，然后从1号开始假设其说谎，然后判断是否符合题目要求代码： #include<stdio.h> #define maxn 110 int wolf[m...

2020-12-02

0 324

1147 Heaps

题意：给一个二叉树的层次遍历，问是什么类型的堆，是大顶堆还是小顶堆，然后输出这个树的后续遍历题解：大小堆根直接比较a[i]与a[i/2]即可因为给的树的层次遍历，i就是i/2儿子后序遍历，对于节点index分别遍历孩子index2和右孩子index2+1，遍历完左右子树输出根节点代...

2020-12-02

0 314

牛客网dp专题数位dp

文章目录数位dp NC116652 uva11038 How many 0's NC15035 送分了QAQ NC20669 诡异数字 NC20665 7的意志 NC17385 Beautiful Numbers CF55D ...

2020-12-02

0 463

Neat Tree

Neat Tree 题意： n个数，每个区间的贡献为区间内最大值减最小值，问这个n个数的总贡献是多少？也就是n所能组成的所有区间的贡献值之和题解：我们可以用单调栈来做第i个数对答案的贡献值为=h[i] * 作为最大值出现的次数-h[i] * 作为最小值出现的次数求每个点贡献值的过程可...

2020-12-02

0 286

[ZJOI2007]棋盘制作

文章目录 [ZJOI2007]棋盘制作题意：题解：单调栈代码：悬线法 [ZJOI2007]棋盘制作...

2020-12-02

0 0

【悬线法】学习总结

【悬线法】学习总结主要用于求满足某条件的最大矩阵定义：一条竖线，竖线的上端点位于矩阵的上边界或是一个障碍点，然后对这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进行确定这条悬线所在的极大矩阵。底线为(i,j)的悬线 Left[]存每个点能达到的最右位置 Right[]存放每个点能...

2020-12-02

0 364

单调栈

以前一直有接触，但是一直没单独进行分析处理单调栈：维护其中元素单调性的栈也就是从栈底到栈顶都是有序的维护：如果入栈的元素满足单调性，直接入栈；如果不满足，就让栈顶元素出栈，直到能让入栈元素满足单调性为止，再将元素入栈（已经出栈的元素就被抛弃）例题：求直方图中包含的最大矩阵面积题解...

2020-12-02

0 304

莫队算法

参考讲解莫队算法将暴力与分块两个算法合二为一，可以称之为优雅的暴力莫队是一个必须离线的算法本质是通过改变查询的顺序来实现降低时间复杂度样例：求一个区间中每个数出现次数的平方和（多次询问）我们可以用暴力来做每次枚举L~R，这样的暴力注定不可，我们考虑先一个等级的暴力一开始指针区...

2020-12-02

0 0