还没补E，感觉很GF。个人感觉质量挺好，拿CFDiv.2来对标也是出的比较好的一场。唯一的缺陷可能是E/F应该换个位置？简要写个题解？A给定数组\(a\)，以及常数\(k\)，定义\(w(i,j)\)当\(|a_i-a_j|>k\)时候为\(\max(a_i,a_j)\)，否则为\(\min(a_i,a_j)\)。显然排序之后贪心将\(w

哈希函数的基本性质函数定义域是无穷的，值域相对有限（但也很大，比如2的64次方）输入同样样本一定得到同样的输出输入不同样本可能得到相同输出，此时叫哈希碰撞输入大量不同的样本，得到大量输出值，会几乎均匀的分布在整个输出域上布隆过滤器通过几个不同哈希函数计算哈希值，对位

基环树1.定义基环树是一个由n个点及n条边组成的连通图，其比树多出一条边，所以称作基环树。2.分类基环树分为无向基环树和有向基环树。而有向基环树又分为内向基环树和外向基环树。内向基环树，即每个点出度为1的基环树；外向基环树，即每个点入度为1的基环树。3.解决方式对于有关

[THUPC2018]淘米神的树先考虑开局只有一个黑点，将黑点做根，问有多少种排列满足父亲在儿子前。很平凡的问题，设\(f_u\)为\(u\)子树的合法序列个数，\(f_u=(siz_u-1)!\sum_{v\inson_u}\frac{f_v}{siz_v!}\)，先将根放入，再由合法子树相对序列代替全排列。整理答案为\(ans=\frac{\prod_u

基环内向树上dp，不过在这里提供给一种非典型做法。考虑将环上的每一条边都断开，这样就会形成多棵树，先在这些树上进行树形\(dp\)。设\(dp_{i,0/1}\)表示不选/选\(i\)时，\(i\)子树内的最大选点数。明显方程为：\[\begin{cases}dp_{u,0}=\sum\limits_{v\inuson}\max(dp_{v,0},dp

P6037Ryoku的探索基环树有两种思路：将环上一条边断开，转化为树上问题先考虑环上，再考虑环上每个点构成的子树。考虑后者。首先基环树上深度遍历只会少走一条边，所以考虑哪条边没被走。可以发现，基环树上深度遍历完后没遍历的边一定在环上。那么如果起点在环上，没遍历的边一定是

一致性哈希  一、什么是一致性哈希  一致性哈希是一种用于分布式系统中数据分片和负载均衡的算法。它的核心思想是将数据和节点通过哈希函数映射到一个固定范围的环形空间中，每个节点在环上占据一个位置，而数据则根据哈希函数计算出的值映射到环上的某个位置上。目前主要应

2023.4做题记录[NOIP2018提高组]旅行看到题目中要求\(m=n\)或\(m=n-1\)，此时就应当分类讨论。①当\(m=n-1\)时：此时数据为一颗树。我们贪心的想：起始点为\(1\)的时候显然最优。对于每一个节点，在它子树内按照从小到大的顺序遍历显然最优。复杂度\(O(n\logn)\)，瓶颈

AGC010ERearranginglink题意：一个序列\(a_{1...n}\)，两个人游戏。先手打乱这个序列，然后后手可以多次选择一对相邻的互质的数交换。先手希望最终序列字典序尽量小，后手则相反。两人都绝顶聪明，求最终序列。\(1\len\le2000,\space1\lea_i\le10^8\)考虑不互质的两个数\(a_i,a

虚高*2800。放模拟赛T2人均切了。先想树的情况怎么做。枚举每个起点，剩下的贡献就是定值。求这个值可以钦定\(1\)为根求出所有的\(siz\)，然后枚举\(i\)为起点，以\(i\)为起点的答案就是\(\sumsiz_i\)加上\(i\)到\(1\)路径上，不含\(1\)的所有点的\(\sum_jn-2\time

基环树学习笔记定义基环树指的是一张有\(n\)个节点和\(n\)条边的图，如果不保证连通的话，那么整张图是一张基环树森林。并且如果将环上的任意一条边去除，那么整棵基环树会成为一棵普通的树。分类基环树有以下几种特殊情况，也是题目中较多出现的。基环内向树指的是在一棵有向

基环树下面几个条件互相等价：一个图（连通块）是基环树联通块有n个点n条边图上存在且仅存在一个环，且环上每个节点是一颗子树的根。通常情况下树指的都是无向图，但是有向图也可以构成基环树。内向基环树：每个点都有一条出边。容易发现沿着这条边一定会走到环上“向内走”。外

法一：环套树。把基环树看作一个环上吊了几棵树，在处理时遍历环上每个点，处理出每棵树的答案，然后做环形的操作。缺点：只能处理基环树，如果是仙人掌就不适用了。法二：树回边。以深搜树的方式看待，用处理树的方式（比如树形DP）。在遇到环上深度最浅的结点的时候，让它把下方的环的结果当作一

\(dp_{i,j}\)表示第一个人走到\(i\)，第二个人走到\(j\)的方案数量。环上的情况先把每个点按照拓扑序排序，相同环上的点放在一起。但是有可能在环上游走。非常抱歉，昨天有很多东西是错的，以下内容感谢\(\textrm{liuhangxin}\)的帮助指正。所以开一个辅助数组\(g_{i,j}\)

题意给定一个长度为\(n\)的排列\(p\)。你可以进行不超过\(10^6\)次操作，每次操作是选择一个长度为偶数的区间\([l,r]\)，然后交换\((p_l,p_{l+1}),(p_{l+2},p_{l+3}),...,(p_{r-1},p_r)\)。你需要将排列排序。数据范围：\(n\le3\times10^5\)。题解刚才有个群友问我Z

前言看这道题有好多巨佬都是用Tarjan来做的，在这里讲一个自认为比较简单的做法，(不到\(30\)行)。题意题意比较难讲，建议自己去看一下翻译，在这里不多赘述。思路首先看到题目中间给的一个每一次操作的式子：\(a_{l_{i}}=l_{(i\modk)+1}\)。仔细观察这个式子后会发现，其实每一次

城市环路题目描述一座城市，往往会被人们划分为几个区域，例如住宅区、商业区、工业区等等。B市就被分为了以下的两个区域——城市中心和城市郊区。在这两个区域的中间是一条围绕B市的环路，环路之内便是B市中心。整个城市可以看做一个$n$个点，$n$条边的单圈图（保证图连通），唯一

应该是联赛前最后一次任性了，浪费的时间有点多，不过也揭露了我的基础知识和代码能力都很弱的问题，得加油啊。先stodwt。给定一棵基环树森林，起初有\(m\)个点已被选进\(S\)里，你需要再选\(k\)个点加入到\(S\)中，最小化其余点到\(S\)距离的最大值。这个问题直接做非常困难，

原题注意这个环指的是简单环这题用到一个非常trick的思路：给你一个图，让你保证每个点恰好处于一个环上。对于任意在环上的点\(p\)，出入度都为\(1\)，于是我们把它拆成两个点\(p_{in},p_{out}\)。则原图上的一条边\((u,v)\)在拆点后的图上对应\((u_{out},v_{in})\)，而满足

前言一日知基环树弱，固补题。关于基环树基环树定义一个环，环上每个点都有一颗以该点为根的树，如下图为一棵基环树关于基环树常规思路通常来说基环树常规思路是先处理环上树的结果，后通过树的结果来处理换上结果。具体处理方式依照题目来定。然而只是通常来说因为基环树的问

一千瓶药水中有一瓶毒药，毒性在喝下后24小时发作，问至少需要多少只老鼠才能在24小时后得出哪瓶是毒药？将一千瓶药水编号1~1000，对应10位二进制位。让第1只老鼠嘬一口所有二进制编号第1位为1的药水，第2只老鼠嘬一口所有二进制编号第2位为1的药水，依次类推则需要10只老鼠。24小时后如

题目链接：D-Flower-likePseudotree题目大意：给定度数数组\({d_n}\)，要求构造一个\(n\)个点\(n\)条边的连通图（也就是基环树），允许有重边，但不能有自环。需要满足第\(i\)个点的度数恰好为\(d_i\)，并且将环上的边全部删去后，剩下的每棵树的高度（以原先在环上的点为根）相同。首先考

题意描述马塞尔和瓦勒里乌（Valeriu）所在的疯狂城市由\(n\)栋建筑和\(n\)条双向道路组成。马塞尔和瓦勒里乌（Valeriu）分别从\(a\)号和\(b\)号建筑开始。马塞尔想赶上瓦勒里乌（换句话说，与他在同一栋楼里或在同一条路上相遇）。在每次移动过程中，他们都会选择前往当前建筑的邻近建

首先，严格地讲，基环树不是树，它是一张有\(n\)个节点、\(n\)条边的图。介绍无向图上的基环树有向图上的基环树内向树出度为1外向树入度为1流程找到唯一的环；对环之外的部分按照若干棵树处理；考虑与环一起计算。找环从任意一点开始搜索；每次拓展到的点涂为灰色，回

基环树DP一些基本概念：在一棵树上加一条边，就会构成一个环，环上会挂着一些子树。基环树是只有一个环的仙人掌。如果基环树的边是有向边，环上的点是p1,p2,p3,...则环上的边是p1->p2,p2->p3,...,pn->p1或者全部反过来总之就是环上的边要么全部逆时针要么全部顺时针。对于