A给定一个无限长序列的\(0\simn-1\)项，每项满足与\(n\)的差不超过\(1\)。之后的每一项满足\(a_i=\sum_{j=0}^{i-1}[a_j+j\gei]\)。\(q\)次询问第\(p\)个位置的值。\(p\le10^{15}\)。非常难的签到，考虑消去常数，将\(a_i\)全部减去\(n\)，那么\(a_i=[a_{i-n-1}=1]-[a_

目录1.迷宫中离入口最近的出口 1.1算法原理1.2算法代码2.最小基因变化★★★2.1算法原理2.2算法代码3.单词接龙3.1算法原理3.2算法代码4.为高尔夫比赛砍树(hard)4.1算法原理 4.2算法代码1.迷宫中离入口最近的出口 .-力扣（LeetCode）1.1算

最小生成树模板题：【模板】最小生成树求最小生成树的边权和。Prim这似乎是我最早学的最小生成树算法。也是忘的最早的首先注意到，由\(n\)个节点和$n-1$条边构成的连通图一定是树。那么只需要选\(n-1\)条边使图连通，求最小代价。不难发现只要保证结果不出现环就可能是

图论系列：前言：相关题单：戳我一.最小瓶颈路唉，前面4个题单里其实有不少题是最小瓶颈路的做法啊。讲解摘自wiki。1.定义无向图\(G\)中\(x\)到\(y\)的最小瓶颈路是这样的一类简单路径，满足这条路径上的最大的边权在所有\(x\)到\(y\)的简单路径中是最小的。（对于下面这张

20241015最短路与生成树@.ThearmyofThutmoseIII题号是@，原因是过了之后才发现测不了被删了。注意到问题形如最大值最小，直接上二分答案。考虑如何check。设当前check的答案为\(x\)。容易获得一个猜想，点一定放在区间端点上。那么将区间端点离散化。记\(a_i\)表示第

20241009模拟赛A.排列喵手玩一下，依次操作\(1,n,1\)必然能使序列有序，所以答案不超过\(3\)。那么依次判断\(0,1,3\)即可。原序列如果有序就是\(0\)。如果\(a_1=n\)且\(a_n=1\)就是\(3\)，因为这两个条件有一个不满足时只要操作\(1,n\)或\(n,1\)就能变成有序。考虑

ShichikujiandPowerGrid题意还是很简单，每个点有点权，每个点之间也有边权求最小生成森林，每个一颗最小生成树的权值等于边权+最小点权思路边权我们很好处理，有模板，但如何处理这个点权，便成了主要的问题如果我们以边权的思路思考点权，那么点权就是某个点从到该点的边权而我们可

[TJOI2012]桥删边最短路模板。只需求出对于每条边，不经过这条边的最短路就做完了。考虑不在原\(1\)到\(n\)最短路上的边，它们的答案就为原本的最短路。对于原本就在最短路上的边，既然删掉了这条边，那么新的最短路一定会经过另外一条边，设这条边为\((u,v,w)\)，\(dis(u,v)\)表

Question1.[ARCY2021]E.PlanningRailroadDiscontinuation给定\(l\)张\(n\)个点\(m\)条边的图\(G_i(0\leqi<l)\)，其中图\(G_i\)中连接\(u,v\)两个点的边的边权为\(w_{u,v}+b_i\)。在所有图中钦定\(r\)个点\(s_1,s_2,\cdots,s_r\)，作为特殊点，其中点\(G

[SXZOI2024E]哮题目背景是什么在黑夜嚎叫？题目描述有一个$n$个点，$m$条边的有向无环图。每条边上有边权。定义一条路径的权值为路径上所有边权的异或值。现在对于所有从节点$1$出发走到节点$n$的路径，输出这些路径的权值和。答案对$998244353$取模。输入格式第一

搜索BFS我的理解：基础的bfs本质上也是动态规划，dist[i,j]表示到达(i,j)转移的最小次数。由于动态规划的无后效性，就是当前状态确定后，不需要管之前的状态转移。bfs是一层一层搜的，搜索的相当于是一个状态，第一个搜到的就是最优的。比如最简单的走迷宫，每个点只会走一次，那么第一

A大家使用了整体二分+可撤销并查集，倍增等方法...考虑线段树合并。在跑Kruskal时，如果一个询问的两个点在同一个连通块内，那么这个询问就是可回答的，但是可回答不一定要回答，因为如果此后加的边权相同那么其实里面的点还能再往外走。所以在加边时如果新加的边权大于连通块边权，那

A.排列最小生成树(pmst)大家都没签上的签到调参调到110能过？！但赛时用set这个大常数选手存的边，挂了个log，所以跑不动大样例。正解：发现只按把编号相邻的点连边构成一条链，此时所有边的长度都\(\len\)，所以无论如何我们都能保证最小生成树每条边的边权\(\len\)。那么我们

一个相当厉害的东西啊。参考原件：IOI2008国家集训队论文——周冬。图片引自OI-wiki平面图llmmkk’sblog论文原件先给出结论：平面图最小割等于其对偶图最短路平面图平面图，指可以通过画图方式将使得边两两不相交的图。(无向图)例如：事实上是：一些概念：设\(G\)

定义：在无向连通图中边权和最小的生成树为最小生成树。生成树的定义是在一个无向图中包含所有节点且边数最少的连通子图。Kruskal算法考虑一种贪心，我们将边权从小到大排列，依次将边加入生成树中，如果此次加边形成了环，则扔掉这条边。我们可以轻易证明此贪心的正确性，若在某次加入中

P6748FallenLordDescription给定\(n\)个节点的树，每个点有点权\(a_i\)，求构造一组边权，使得每个点连接的边的边权的中位数不超过其点权，且每条边权不超过给定的\(m\)，输出边权之和的最大值。一个升序序列\(A=\{A_1,A_2,A_3...A_n\}\)的中位数定义为\(A_{\lfloorn/2\rfloor

[JOI2013Final]现代豪宅题意给出一个\(n\timesm\)的网格图，每两个格子之间有一扇门。初始上下方向的门都是开着的，左右方向的门是关着的。有一些格子有按钮，可以把打开的门关上，关上的门打开。走一步需要一秒，按按钮需要一秒，求从\((1,1)\)到达\((n,m)\)的最小步数。思路

Problem给出n个点、m条边的无向连通图，每条边具有2个边权，一高一低，我们需要选择若干条边，使得图连通的情况下选择至少k条较高边权，输出选择的边中，边权最大值的最小值，输出答案的一半（保证偶数）Slove假设每条边只具有1条边权，答案显而易见，跑一遍最小生成树即可，因为最小生成树就是最小

最小生成树证明最小生成树构成的过程实际上是做\(n-1\)次操作，每一次合并一个点集，直到图中只剩下一个集合为止。要达到的就是让每一次合并的代价之和最小。那么我们实际上可以贪心地选择边权最小的并且能够合并集合的边（Kruskal算法），这个算法的正确性简单来说可以用反证法来证

给出一棵树，同时存在一张\(n\)个点的无向完全图，其中边权为树上两点距离，求所有点对之间最小瓶颈路上最大边权之和。这是梦熊第七场noip模拟赛的t1题面，如果你想要做出t1，你只需要一个结论和见过足够的题。结论：两点之间最小瓶颈路最大边权就是两点在最大生成树上简单路径的

A调整法可证只需要考虑左端点或右端点在\(a_i\)上的区间，考虑对于一个区间\([l,r]\)计算答案。注意到对于每对相邻的数，挤压后较大者仍然大于等于较小者，所以可以分别求较大者与较小者压缩后的和再相减。以求较大者压缩后的和为例，小于\(l\)的数变成\(l\)，大于\(r\)的数变

9.16上午补了一下暑假姚子奇讲的题，让姚子奇给我调个题他都不带鸟我的。P4180[BJWC2010]严格次小生成树先用kruskal将最小生成树求出来，之后再枚举不在最小生成树的每条边，设每条边的端点为x,y，如果加入这条边，则会形成一个环，于是我们考虑用这条边替换x和y路径上的一条边，但是由于是

[SCOI2009]迷路题意给出一张带权有向图，从\(1\)号点出发，必须在恰好\(t\)时刻到达\(n\)。中途不能停留，求有多少种方案。思路先考虑边权为\(1\)的情况，设\(f_{t,i,j}\)为从\(i\)走到\(j\)花费\(t\)个时刻的方案数。\(f_{t,i,j}=\sum{f_{t-1,i,k}\timesf_{t-1,

算法理解从一个点出发，遍历它的所有相邻点，一层一层往下遍历T1：（30min）bfs注意起点不一定在左上角，四个方向都要走T2：（40min）bfs注意山峰山谷有一个很重要的条件，周围的所有点高度必须大于或小于山峰山谷的高度T4：（1h）我打了一个SPFA，因为每一个点需要更新最小值并且可以重复入队（准确来讲

题意给定一个\(2\timesN\)的网格，网格上的点和上下左右连边。要求支持以下几种操作：修改某条边的边权。求满足\(y\in[l,r]\)的点构成的点集的最小生成树。分析这道题的想法和P4246[SHOI2008]堵塞的交通很相似。注意到\(N,M\leq6\times10^4\)，并且查询的是