大致目录最短路单源最短路径1.Bellman-Ford算法2.SPFA算法3.Dijkstra算法多源最短路径Floyd算法总结最长路SPFA拓扑排序非严格次短路严格次短路因为之前一直好久之前用的博客园，现在上大学了慢慢开始用CSDN，把之前写的一些年轻的文章先拿过来用用，嘻嘻。如题，这

分层图讲真的…感觉有点像那么一点点的种类并查集简单来说，就是把一个图分成很多层，然后对图进行一些处理比较模板一点的东西就是直接在分层图上跑最短路，这个时候就涉及到了很多决策，每一个决策能进行一些特殊的操作，比如让某条边免费（边权为0，不是把边切掉），让某条边花费减半之

题解总之，赞美太阳#include<bits/stdc++.h>usingnamespacestd;inlineintread(){ charc;intf=1,res=0; while(c=getchar(),!isdigit(c))if(c=='-')f*=-1; while(isdigit(c))res=res*10+c-'0',c=getchar(); returnres*f;}constintN=1e3+5

问题背景在推理过程中使用TOT方式可以增加推理性能，但由于增加了推理次数，导致耗时过大。目前待解决的问题是如何能在推理时既保持很好的推理能力，又保持推理耗时不会过大。本文方法文章提出CPO（ChainofPreferenceOptimization）方式。该方法使用TOT方式来探索推理路径得到

线段树structsegmenttree{ structnode{ intl,r; longlongsum,tag;} T[maxn*4]; longlongrepair(intp,longlongk){ returnT[p].tag+=k,T[p].sum+=k*(T[p].r-T[p].l+1);} voiddowndata(intp){ repair(2*p,T[p].tag),repair(2*p+

有\(n\)个人排成一列（或一个环），第\(i\)个人手里有\(c_i\)张牌，在每一步操作中，可以让某人给他左边或右边的人一张牌，问最少多少步可以让每个人手中的牌数相等。线性均分纸牌问题首先定义\(\texttt{avg}\)为纸牌总数的平均数，如果\(\texttt{avg}\)不是整数的话，那么就是无解。

9.3/9.4P3376【模板】网络最大流因为Dinic对于求最大流是比较优的算法，考虑对Dinic进行一个复习Dinic属于Ford-Fulkerson增广路算法，每次增广前我们都先用BFS将图分层，每个点的层数都是其距离源点的最短距离求解思路如下：对原图进行BFS构建分层图考虑EK算法的

洛谷P5340大中锋的游乐场题意给出一张\(n\)个点\(m\)条边的图，每个点有一个点权\(1\)或\(-1\)。给出点\(s,t\)，求出\((s,t)\)间满足以下条件的最短路。任意时刻，走过的路径上点权和均\(\in[-k,k]\)。思路分层图最短路。\(dis_{i,j}\)表示走到\(i\)，点权和为\(j

涉及了区间翻转操作，Splay不再是BST；Splay只能保证其中序遍历为当前序列；用lazy标记做，具体见OI-wiki，代码见下#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=100010;structSplay{intl,r;intcnt,Size;intval,lazy;}a[N];int

思路首先，我们可以将一条要标记的路线\((s,t)\)分成\((s,lca)\)和\((lca,t)\)两个部分，这两个部分分别对应一种\(y=kx+b\)。代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;usingi64=longlong;constintN=100010;consti64

DescriptionA,B两个国家正在交战，其中A国的物资运输网中有\(N\)个中转站，\(M\)条单向道路。设其中第\(i\(1\leqi\leqM)\)条道路连接了\(u_i,v_i\)两个中转站，那么中转站\(u_i\)可以通过该道路到达\(v_i\)中转站，如果切断这条道路，需要代价\(c_i\)。现在B国想找出一个

三年之后第一次打比赛，用小号打了场\(Div.3\)，居然没有AK，感觉实力退步到小学了。A.HowMuchDoesDaytonaCost?若只判断题，只要判断\(\{a_n\}\)中是否存在\(k\)即可。B.AleksaandStack构造方法不唯一，我直接输出奇数列，显然正确。C.VasilijeinCacak若只判断题

0/1Trie具象化一次操作对数据结构产生的影响试想，如果我们在一次修改指令中逐一更新了子树p中的所有节点，但是在之后的查询指令中却根本没有用到，那么更新p的整棵子树就是徒劳的精妙的懒标记设计，详见代码注释(1ll<60)用类实现懒标记无法读取文件是因为UTF-8BOM，另存为UTF-8就

这场rank4，应该是暑假以来打的最好的一场了。。。其它时候就没进过前10。。。博弈30pts赛时$O(n^2)$暴力30pts；对于暴力，我们能发现一个性质就是只要有一类边权出现了奇数次，那么先手必胜，所以我们枚举每一个点对，开个数组统计一下即可；不要忘了离散化；对于正解，用到了一个东

定义割点：无向图中，若删除点及其连边，连通块变多，那么被删除的点为割点点双连通：若无向图中点对\(x,y\)，删除任意非\(x\)和非\(y\)节点后，\(x\)和\(y\)任然连通，陈\(x,y\)点双连通点双连通子图：无向图中的一个子图\(G\)，\(G\)中任意2点都是联通的，那么称\(G\)为原图的点双

性质1.百度百科给的最主要的性质就是归零和结合，其他的就都是拓展了。例题：P14692.\(a\bigoplusb<=a+b\)关于这个不等式比较好的理解为异或就是不进位的加法例题：luoguP5514应用异或哈希异或跟hash一样，也是会发生冲突的例如：$1\bigoplus2=5\bigoplus6$那我们

思路其实就是一道数学题。设每座山的水量为$ans_i$，大坝的水量为$w_i$，则根据题意可以得到以下方程：$$\begin{cases}w_i=\frac{ans_i+ans_{i+1}}{2}&i<n\w_i=\frac{ans_i+ans_1}{2}&i=n\end{cases}$$所以只要求出任意一个$ans$就可以求出剩余的$ans$，这里我选择求$ans_1$的

Rank有点可惜，暴力打满就并列Rank1了。A.Kanon原[JOI2021Final]雪玉签。考虑到每两个球之间的距离是恒不变的，因此我们可以通过找到每个球控制的边界得到答案，每个区间正好可以得出左边球的右边界和右边球的左边界。记录每个区间的标号和长度，按长度升序sort一遍，然

要把二进制数的“每一位”取反，用^((1<<n)-1)，（~运算会得到一个负数，而且也没有取出前n位）点击查看代码#include<bits/stdc++.h>usingnamespacestd;strings[5];intcnt[10],tot[10];//1表示可以通过改变这一位使得tot+1voidchange(intx){ cnt[x]--; for(inti=0;i<3;

正题题目链接:https://www.luogu.com.cn/problem/CF1615H题目大意有\(n\)个点，每个点有个初始权值\(a_i\)，你每次可以让一个点权值\(+1\)或者\(-1\)。有\(m\)个限制要求某个点最终权值小于等于另一个点。求最少的操作次数使得满足所有限制。\(2\leqn,m\leq1000,1

[ABC366C]BallsandBagQuery题解题目传送门AT原题传送门首先是题面的翻译：你有一个袋子，给予\(Q\)次操作，操作有三种1\(x\)，将一个写有整数\(x\)的球放入袋中。2\(x\)，从袋中取出一个写有整数\(x\)的球。3，查询袋中球上的不同整数的数目。整理了一下思

图的基本操作图的存储1.邻接矩阵//对于一个正常的边(u,v,w)vector<int>a[MAXN];a[u].push_back(v);a[v].push_back(u);2.链式前向星//对于一个正常的边(u,v,w)structnode{ intto,next,len;}e[MAXN];inttot=0,h[MAXN];voidadd(intx,inty,intlen){ e[++

寻找性质优化DP:对于一个音高为\(a_i\)的音符，在最优解中，接在其后面的音符一定是离这个音符最近的音高在【\(a_i-k,a_i\)】或【\(a_i,a_i+k\)】内的音符这个音符是可以通过线段树预处理求出来的点击查看代码#include<bits/stdc++.h>usingnamespacestd;longlonga[10000

Prufer序列Prufer序列可以将一个带标号\(n\)个结点的树用\([1,n]\)中的\(n-2\)个整数表示，也可以理解为完全图的生成树与数列之间的双射。建立过程：每次选择编号最小的叶子节点并删掉，然后在序列中记录它连接的节点标号，重复\(n-2\)次后结束。不难发现：构造完Pruf

前置芝士：时间戳在树的优先深度遍历中，以每个节点第一次被访问的顺序，依次给予这\(N\)个节点\(1~n\)的整数标记该标记被称为时间戳。通常用\(dfn[x]\)表示\(x\)节点上的时间戳。树的DFS序定义：在树的深度优先遍历中，对于每个节点进入递归后以及即将回溯前各记录一次该