DDOSvoid's Blog

题目描述

https://www.luogu.com.cn/problem/P1967

简介

在 $kruskal$ 求最小生成树的过程中，每次加边时，新建一个节点，然后让两个连通块分别成为新建节点的左右儿子，且新建节点的点权就是这条边的边权

题目描述

简要题意：给定一个长度无限大，宽度为 $m$ 的平面，现在我们依次在平面上加入 $n$ 个点，每加入一个点都需要求一个最小的半径 $r$，使得平面上这些点变成半径为 $r$ 的圆后，这些圆的并将平面封住，即无法从平面最左侧走到最右侧

$n\le 2000$

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=5807

题目描述

https://codeforces.com/contest/1406/problem/C

简要题意：给定一棵 $n$ 个节点的树，求是否可以通过删一条边并且加一条边使得该树的重心唯一，删掉的边和加入的边可以是同一条边

$n\le 10^5$

题目描述

https://www.luogu.com.cn/problem/P2882

题目描述

有一个序列 $a$，序列中每个元素有一个属性 $a_i$，其中 $1\le a_i\le m$

求所有区间 $[l,r]$，满足区间中所有属性的元素均有出现，且每种属性的元素数量相等

$n\le 10^5,m\le 50$

题目描述

https://www.luogu.com.cn/problem/P4366

简要题意：给定一个有 $n$ 个点的完全图，无向边 $$ 的权值为 $(u~xor~v)\times C$，$C$ 是给定的常数，现再给定 $m$ 条单向边 $(u,v,w)$ 和起点 $s$ 以及终点 $t$，求 $s$ 到 $t$​ 的最短路

$n\le 10^5,m\le 5\times 10^5$

简介

总结一些非常经典的套路

题目描述

https://www.luogu.com.cn/problem/P3521