昵称很长很长真是太好了

分类

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

/ 注册

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

142篇文章 1959人学习

python学习记录

7篇文章 2746人学习

数据结构算法学习

13篇文章 1780人学习

算法专题学习记录

10篇文章 829人学习

全部文章（共189篇）

数学家的迷题来自专栏

题意：1：将的值改为。2：令，求t能被多少个不同的素数整除。题解：本题有两种解法，带修莫队和线段树，带修莫队的话需要开个O3提提速，不然会T一个点。 1.带修莫队题目不是5e4的范围吗，带修莫队会卡时间？因为莫队移动的操作时间复杂度为O(1)，但是这个移动的时间复杂度却不是O(1)，应该是一...

2021-06-30

1 413

牛客推荐系统开发之标签重复度来自专栏

题意：给你一棵树，问树上所有两点路径上的（最大值最小值乘积）之和。题解：很明显的一个点分治问题，然后就是个二维偏序问题了（虽然我也不知道啥是二维偏序）。点分治不难，重点是点分治内cal函数如何去写。假设当前计算的这个树是以root为根节点，我们对于每一次分治的过程，每个结点储存两个值，一个是...

2021-06-14

0 420

题解 | #小Q与彼岸花#

题意：题解：因为这个题目是弱化以后的，正常的范围是5e4 . 看了官方题解去学习了一波可持久化01trie然后回来把这个题补完。可持久数据结构其实就是我们的数据结构的内容会不断发生变化，而我们还要查询以前的历史版本，比如某个区间的情况。听名字可以听出来，可持久化01trie跟可持久化线段树差不...

2021-04-26

1 430

题解 | #Max Flow#

咦，竟然之前做过题解：是一道很经典的树差分模板题，点差分我们需要让cnt[s]++,让cnt[t]++，而让他们的cnt[lca]--，cnt[faher(lca)]--;边差分cnt[s]++ ， cnt[t]++ ，cnt[LCA]-=2 边差分：边差分的话要把边的权值存在他连着的儿子节点上...

2021-04-13

0 432

题解 | #[HAOI2012]音量调节#

题解：简单的dp。也许dp我只会做这种小白型的了（剩下的交给队友奥里给）首先我们先看一下，不优化空间的dp怎么写的。我们发现他最多会演唱50首歌曲，最大音调为1000。开一个代表演唱到第i个物品的时候，能不能演唱出来音调为j的歌曲。初始状态全是false，只有转移方程：代码： #include...

2021-04-13

1 617

题解 | #A Simple Task# 线段树

题解：这种题之前做过一个类似的题目，也是关于选择区间然后给区间进行排序。这种题用线段树把排序转换成区间修改区间求和即可。类似的题目：https://vjudge.net/problem/HDU-5649 首先我们看到这个题是针对于字母进行排序的，区间操作很像线段树，那么如何把他转换成线段树呢？我们考...

2021-04-09

0 583

[HAOI2015]树上操作来自专栏

首先先说一下基本概念： 1.重儿子：一个结点的所有儿子中，大小最大的那个（最重的，所以说只有一个，如果有多个儿子的大小相等那就随便取一个）。 2.轻儿子：一个结点的儿子除了重儿子以外的所有儿子都是轻儿子。（根节点为轻儿子） 3.重链：从一个轻儿子开始，一路往重儿子走，连出来的链叫重链。 4.轻链：除...

2021-03-27

1 583

3月9日Tree Decoration 来自专栏

题解：对于叶子节点，我们直接购买要求购买的个数即可然后树上维护几个变量，sz表示该节点的子树已经挂在了多少个礼物了，如果挂载的礼物总数小于要求的总数，那么当前结点是要必须再购买一些礼物的，但是并不一定买在当前结点上，我们可以买在他已经他子树上，找一个最便宜的结点来购买礼物，从而保证价格最低！这个我...

2021-03-11

0 539

区区区间来自专栏

题解：线段树，不过这里线段树区间维护要换一种方法。我们发现这个等差数列的等差为1。对于修改一段区间如果我们知道首项值，那么我们便可以在的时间复杂度计算出这段区间的大小。又可以知道，对于线段树每一个结点，代表一段区间，那么我们我们用lazy数组保存这一段区间的首项，那么我们便可以在O（1）的时间复杂...

2021-03-09

0 496

CF187C Weak Memory 来自专栏

题解：二分+bfs，二分最长距离，这个题在bfs时使用堆来处理会变得比较简单，优先去走油量较多的那个点（某个点当前能量最大一定“有利于”接下来点的转移），每当遇到特殊点的时候，把油量加满即可。走到终点即返回true。没走到返回false即可。代码： /*Keep on going Never gi...

2021-03-01

0 459