昵称很长很长真是太好了

题解

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

/ 注册

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

[codeforces] 383C Propagating tree(dfs序+线段树) 来自专栏

题意：给你一棵n个结点的树, 以1为根。每个结点有点权。有m次操作：1.x结点权值 +val，x的儿子权值 −val，x的孙子们 +val，以此类推。2.询问x的点权；题解：我们首先跑一边dfs序，顺便求除每个结点的深度。我们把他分成两颗线段树，深度为奇数的在第一颗上，深度为偶数的在第二课上。我们每...

2020-11-20

2 729

求和（dfs序+线段树）来自专栏

题意：已知有n个节点，有n−1条边，形成一个树的结构。给定一个根节点k，每个节点都有一个权值，节点i的权值为vi。给m个操作，操作有两种类型：1 a x ：表示将节点a的权值加上x2 a ：表示求a节点的子树上所有节点的和（包括a节点本身）题解：dfs序+线段树用dfs序确定in[x]和out[x...

2020-11-19

2 600

CF570D Tree Requests 来自专栏

题意：给定一个以1为根的n个节点的树，每个点上有一个字母(a-z)，每个点的深度定义为该节点到1号节点路径上的点数.每次询问 a,b 查询以a为根的子树内深度为b的节点上的字母重新排列之后是否能构成回文串.题解：dfs序+状态压缩+二分查找这个题用到了很多小技巧，比如说异或前缀和等等。我们首先对他跑...

2020-11-18

3 680

选点来自专栏

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

2020-11-17

2 783

CF1006E Military Problem 来自专栏

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

2020-11-17

2 676

小A与欧拉路来自专栏

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

2020-11-10

1 608

CF888G Xor-MST

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

2020-11-04

1 733

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 630

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

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

2020-10-30

2 603