__故人__

分类

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20) 题解(117)

/ 注册

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

30篇文章 846人学习

22篇文章 1707人学习

全部文章（共169篇）

离别

分析欢迎私聊，感觉说的不太清晰。我们考虑如何保证每个区间的某一个种类个数达到。这个我们可以考虑离线询问，将的询问差分成的答案。那么我们先把一个询问拆分成两个，再来考虑前缀的做法。我们对于每个数，保留它的前一个和他相同相同的元素。那么枚举的右端点到了，那么左端点在都是可以...

2020-11-23

16 875

Network

分析考虑求出边双连通分量，那么题目其实就是在问，有多少个桥。那么由于边双缩点之后，整个图变为树。那么树的边数就是答案。考虑新加一条边之后的贡献。那么就是树上距离，在将这个链上的权值变为。这个考虑树链剖分或者维护，写完才发现，好像直接并查集时间复杂度好像还要更优。这里采用了实现，时间总复...

2020-11-20

8 983

Tree with Small Distances

题意你有一颗个节点的有根树 (以号节点为根) ，求最少加入多少条边之后使得根节点（即 11 号节点）到这棵树上任意一点的距离不大于。分析我们考虑覆盖一个节点有多少种方法。在父亲节点连一条边。在儿子节点上连一条边。在当前节点上连一条边。这样我们发现并不是很好做，考虑叶子...

2020-11-19

7 945

组合数学和斯特林数

写在前面的本博客基本不会讲解如何运用组合数和斯特林数，应该偏向于数学证明，各类恒等式，我先咕一咕。更新日志 11.17 基本的组合恒等式。 11.18 反演原理（很多反演放在后面讲解）。 11.18 第一类斯特林数。 11.18 第二类斯特林数。 11.18 二项式反演，斯特林反演。定义 ...

2020-11-17

9 1110

Bookshelves

题意要求分成恰好组，每组的权值为。要求最大化。分析和位运算有关系，我们就要想到拆位。由于是要最大化权值，所以我们肯定是要优先满足高位。而每一位独立，所以我们可以直接枚举位数。定义表示前个已经分成了组，是否可以组成当前答案，表示现在枚举的答案。那么转移为。那么最后是...

2020-11-16

8 952

Qtree4

题意给出一棵边带权的节点数量为的树，初始树上所有节点都是白色。有两种操作：：改变节点x的颜色，即白变黑，黑变白。：询问树中最远的两个白色节点的距离，这两个白色节点可以重合 (此时距离为 ) 。分析无脑上点分树，每个节点维护两个堆维护子树中最大的长度，自己对父亲的贡献...

2020-11-16

7 601

点分树

说在前面的我一看到是点分树，马上就点进来了，很快啊。前置知识：点分治。约定表示的树上路径长度。引入给出一颗个点的树，每个点有一个权值，有两种操作，一种是将某个点的权值修改为，另一种是查询距离点不超过的点的权值和。分析我们考虑暴力，如果将一个操作的复杂度降...

2020-11-13

9 960

[SDOI2013]淘金

比较有趣(有难度)的数位。分析我们考虑表示每一位的积。那么我们先考虑一维的情况，那么我们要求出最多的一个。那么这个考虑数位解决。但是我们发现还是比较大的。直接表示状态是表示不出来的。但是就有了一个非常好的性质。。这样我们发现其实有用的状态非常少，大概个左右...

2020-11-12

7 599

带权二分

前面的话这篇博客大概是带权二分(wqs 二分，是叫这个名字吧)的入门博客，希望大家点个赞👍。引入给你一个序列。其中。可以把序列分为段。定义每一段的价值为，现在要求的总和最小。形式的，我们要最小化。分析我们可以先做一个的线性。定义为结尾，分了的...

2020-11-11

8 719

2020 CCPC 长春 F

题意非常简洁，给你一个有根树。求问。分析我们发现出现的非常突兀。考虑直接枚举，由于每个点对只计算一次。所以只用计算后加入的对前者的贡献。那么一个点的贡献为，其它子树中权值为的编号。但是答案为。这个没有什么结合率和交换率。我们考虑直接拆位。那么令表示，权值为，第 ...

2020-11-11

6 942