昵称很长很长真是太好了

分类

bfs(5) codeforces(19) kmp(1) python(7) 前缀和(1) 图论(2) 数据结构(18) 未归档(14) 每日一题(14) 牛客(3) 线段树(4) 记忆优化搜索(1) 逆元(1) 题解(99)

/ 注册

TA的专栏 172篇文章 0人订阅

142篇文章 2162人学习

python学习记录

7篇文章 3021人学习

数据结构算法学习

13篇文章 2173人学习

算法专题学习记录

10篇文章 1012人学习

全部文章（共189篇）

选点来自专栏

题意：有一棵n个节点的二叉树，1为根节点，每个节点有一个值wi。现在要选出尽量多的点。对于任意一棵子树，都要满足：如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小。题解：要满足根节点的值最小，左子树的值大于右子树的值。这样的话我们...

2020-11-17

2 783

CF1006E Military Problem 来自专栏

题意：给你一棵树，有q次查询，每次查询第n个结点的他的子树按照dfs序第x个元素是什么？题解：一道dfs序的裸的题目。首先需要一个数组存放第i个结点在dfs序中的位置再需要一个数组来存放dfs序的顺序在需要一个数组来存放一个结点子树的大小。（用来判断是否需要输出-1）每次查询首先判断他的子树大...

2020-11-17

2 677

小A与欧拉路来自专栏

题解：欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次问你走完这树上所有的点最短路径是什么。因为树是没有环的，所以你走到叶子结点的时候需要往回走，也就是再走一遍刚刚走过的路。所以我们确定一条主道路，遇到分支就走一遍（主道路是不需要走两遍的）。因为所有长度都是已...

2020-11-10

1 609

CF888G Xor-MST

题意：给你n个数，每个数有一个值。问你这n个数的最小生成树为多少，两点之间的边权为异或值。题解：参考了洛谷上的一个题解，总觉得这样的时间复杂度会爆炸，但是确确实实没爆炸。我们每次去合并两个点，要想尽量使全值小，对于一颗字典树来说，就要尽量先合并越靠树叶的结点，一个叶子结点对应一个结点。那么我们对于...

2020-11-04

1 734

Perfect Security （01字典树&&删除点）来自专栏

题意：第一行给你一个n第二行给你n个数字分别是a[1],a[2].....a[n]。第三行给你n个数字分别是b[1],b[2].....b[n]。问：第三行的序列可自由排列，要求排列之后的顺序 a[1]^b[1],a[2]^b[2]...a[n]^b[n]的字典序最小。题解：因为b数组可以...

2020-10-30

2 613

Vitya and Strange Lesson （01字典树）

题意：给定一组数，然后对所有的数进行异或操作m次异或操作，问你每次操作后，没有出现过的最小的非负整数题解：首先需要一个性质（a^b）^c=a^(b^c);所以我们没有必要对于所有的数进行异或操作。我们只需要设一个ans=0，每次用输入进来的数于ans进行异或即可。其次，我们把没有出现过的数字加入...

2020-10-30

2 631

奶牛异或（01字典树）来自专栏

题意：让你找一个连续区间异或和最大，如果有相同的，则输出断点较小的。题解：01字典树，利用前缀和的思想进行求解，我们在插入前缀的同时，也在不断的更新最大值。我们查询当前二进制字符串与已经插入的二进制字符串中的哪一个异或和最大？找到最大的那个，读取这个前缀和是到谁结束的，来判断是否要更新 /*...

2020-10-30

2 604

The XOR Largest Pair（01trie模板题）来自专栏

题意：给你一堆数，问你从里面跳出来两个数异或和最大。（菜鸡第一次用字典树做题）题解：之前没用过字典树做题，，看了大佬的题解，才知道字典树还有这种妙用。对于二进制，如果我们想让它最大，（一点贪心的小思想）那么最高位的1 我们是要尽量保留的，（再就是保留次高位.....）。对此我们建立一颗字01字典树...

2020-10-29

2 568

D.Router Mesh 来自专栏

题意：模板题，求图中每个割点能把网络分成几个点双连通分量（不是割点就输出他有几块即可）。题解：跟POJ 的SPF很像这题用Tarjan来求，首先我们需要统计出来具体有几个连通块。对于每个连通块，我们需要判断这个割点去掉后，这幅图会被分成几块？这个其实很简单，只需要更改一下判断这个点是否为割点即可...

2020-10-27

3 966

起床困难综合症来自专栏

题意：选一个小于m的数，始得他经过一系列位运算后值最大。题解：因为数特别大，所以无法用暴力解决。一开始想了贪心，不过只考虑了用111111111111这样的二进制过一遍然后检查得到的数，忘了可以用0过一遍了。看了大佬的题解才恍然大悟，因为这题基础是位运算，所以我们我们把每一位拆开进行判断。贪心这个想...

2020-10-22

2 516