因为本部不让打CF，所以那最近几场CF的题组了一场IOI模拟赛。ACF2033BSakurakoandWaterE内向基环树上两点最短距离，肯定是多个链连到环上，建出反边后就可以以此处理每个子树，不在环上且不同链的一定没戏，还是得先找环。然后先建出反边统计可达性，F首先，选的数很少，\[\begin

算法题意可以转化成给定一个基环树森林,求每颗基环树上的直径长度之和找环按照基环树的方法找即可求直径(i)直径不经过环对于以环上每一个点的子树,记录直径即可(ii)直径经过环断环为链,考虑单调队列处理,具体的关于为什么需要断环为链:方便快速处理环上两点间

1问题我们知道带权无向图上有一个经典问题：最小生成树。那么如果换成带权有向图呢？对于一个带权有向图，从中选出一个子图，使得该子图中无环，且存在一个点可以到达其他所有点，则这个子图就是一个树形图。而求出所有树形图中选出边权和最小的一种选法，就是最小树形图问题。容易想到，解决

A.CloseGroup直接状压。B.P1054[NOIP2005提高组]等价表达式傻逼吗？？？？？？？怎么又不匹配的括号题面里还不说的？？？？？建括号树，然后随一万个数判定即可。C.P7217[JOISC2020]収穫赛时感觉不可做就没做，看来我直觉还是挺准的，但是策队秒了。最重要的一步是观察到每个人摘了苹果之后下一个

A.异或和CF1261F做过类似的题的话，\(O(n^2\log^2v\log(n^2\log^2v))\)应该算是暴力分了。显然这过不了，不然就不是*3100了。主要的瓶颈在于异或完后产生了大量的线段，而且里面大多数是没用的。于是赛时写出了一个绝唐的优化点击查看代码for(inti=0;i<seg[0].size();

csp-s模拟12T小h的几何whk我能说什么呢...T小w的代数仙人掌，DP，计数题本题部分分较有启发意义考虑是一棵树怎么做注意到\(n\)比较小，直接想想比较暴力的做法，可以用\(O(n^2)\)的复杂度枚举起点和终点，而由于是一棵树，两点之间的路径是唯一的，并且本题要求点集不重，

contestlinkA与cheaprobot是一个题，就是跑多元最短路之后\(dis_u+dis_v+w(u,v)\)赋权跑Kruskal重构树即可B注意到是网格图，那么\(u,v\)不连通也就是以其为源点/汇点存在一个割。转对偶图之后也就是判环，那么在删除\((u,v)\)之前对偶图里其对应点已经连通就NIE，否则TAK

NOIP2024集训Day50图论A.[JSOI2012]越狱老虎桥先边双缩点，建出边双生成树。在不额外加边的情况下，割掉树边会使子树内部断开；在加入边的情况下，若加入一条\(1-u\)的边，则形成了一个\(1-u\)的环，环无法通过割一条边断开；而连接树上两个节点\((u,v)\)的情况，把图展开后发

唐氏模拟赛，这没AK我是不是该退役了A枚举矩形上下边界所在的行，拿个桶扫一遍容易算出这两行的贡献。B【模板】离散化+【模板】差分C区间DP，\(f_{i,j}\)表示只留\(i\)子树，所有询问用到的区间个数之和最小是多少。D计数转概率。如果是树的话，考虑维护\(p_i\)表示当前

[NFLSPC#6]等差数列考虑枚举公差\(d\)，如何求得最少题数\(m\)？贪心的想，我们希望的等差数列是一条直线，而增加的数最少就相当于让直线最低且任意点不低过原序列。扫一遍序列，动态维护当先最少需要增加的数\(f\)和当前末项大小\(g\)，如果下一项\(a_i<g-d\)，那么直接把下一项增加

C有\(n\)个点，一开始\(s\)点是白色，其余黑色，你可以花费\(p_i\)的代价使\(i\)点的颜色变成\(a_i\)点的颜色。若第\(i\)个点为白色，那么会有\(w_i\)的代价，问贡献减去代价最大是多少。\(n\le5000\)。不难发现这是一个外向基环树的形式。如果\(s\)不在环上，就是一个树

作者%%%%%%NightTide%%%%%%题目大意求一棵基环树的重心。即一个点，使得树上到其距离最长的点到其的距离最短。注意，这个点不一定是一个节点，可以在树上的任意位置。输出树上到其距离最长的点到其的距离。或者说求基环树最短的直径？（大雾解题思路显然，这颗基环树的直径只有两

题意给定一张\(n\)个点的有向图，每个点都有一条出边。初始保证所有点都能走到\(1\)。你需要重新规划最少的出边，使得最终每个节点都存在一条长度为\(k\)的路径走到节点\(1\)。\(n\le10^6\)Sol显然给定的图为一棵基环树。对环与树分类讨论。首先注意到每个点都能走

今天睡着了。发了只是为了完整性。[CF1672E]notepad.exe先二分得到总长度\(\suml_i+n-1\)记为\(w_1\)，然后考虑其它行数\(h\)，最优的情况只能是每一行都用换行顶替一个空格，此时面积为\(w_h\cdoth=w_1-h+1\)，所以\(w_h=\left\lfloorw_1/h\right\rfloor\)为唯一可能更新答

定义（图片来自这篇文章）基环树：有\(n\)个点\(n\)条边的连通图外向树：每个点出度为\(1\)内向树：每个点入度为\(1\)找环\(dfs\)拓扑排序一般处理方法因题而异，一般有两种常用的第一种是先断掉环边，把环上点当作根，处理每一棵子树，再在环上处理，可能需要

基环树定义在树形结构中添加一条边形成的图。分类无向图基环树内向基环树，每个点的出度为1。外向基环树，每个点的入度为1。找环：方法1：无向图基环树找环。拓扑排序，去掉环以外的点，剩下的就是一个那个环。方法2：有向图和无向图均适用。原理：在搜索树中检查一个点\(x\)的

 CodeForcesRound898(div4)H.Mad City                           大致思路   对于有n条边和n个点，说明这个图里面只有一个环并且两人同时开始和结束移动，所以可以得到当Valeriu进入到这个图里面的唯一

还没补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)\)，瓶颈