题面传送门我感觉这个题很牛逼！提供了一种全新的视角！首先考虑这个平面图怎么用。因为平面图的边数满足\(m\leq3n-6\)，所以一个平面图一定存在一个点度数\(\leq5\)。我们每次删掉这样的一个点，并删掉所有以这个点为端点的边，则剩下的图还是一个平面图，这样不断删除下去就可以得到

中山市选2011杀人游戏一个环上的点可以通过询问环上任意一点来确定整个环的状态，有入度的点可以通过询问它之前的点来确定。所以我们先缩点。需要统计出所有入度为\(0\)的强连通分量的个数。注意一个特殊情况，若存在一个强连通分量满足它大小为\(1\)，且它连接到的点的入度都不

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

构建口胡一下过程：\(fail\)边指向自己的最长回文后缀（偶根指向奇根）。定理：每添加一个字符，至多新增一个新的本质不同的回文串，且是所有回后缀中最长的。由此得出推论：本质不同的回文子串（回文自动机的点数）不超过|S|暴力跳终止链，找到第一个左侧有\(x\)的回文后缀\(v\)。

这种题有一个常见的根号分治做法：设\(d\)为度数，显然有\(O(1)\)修改单点，\(O(d)\)查询邻域和\(O(d)\)修改邻域，\(O(1)\)查询单点两种暴力。对度数大于\(\sqrtn\)的点使用前者，度数小于等于\(\sqrtn\)的点使用后者，可以做到\(O(m\sqrtn)\)的时间复杂度。这种做法的本

这一周在主攻搜索，题单里的搜索题感觉写的还是比较顺利的，还剩一题八数码要用到一些进阶的搜索算法。以下是感觉比较有收获的题目：一、数独挑战：用到了位运算，用位运算进行标记以及判定，可以有效节约空间和时间。二、[NOIP2014]寻找道路题目要求在有向图上找一条最短路，满足路径上

这道题目看官方题解就好了，这个转换图论挺显然的证明一下为什么最后一定是显然练完贬值后图只能长成这个样子在消掉长度为\(2\)的环后，如果说图没边了，那么显然就不用交换了，否则的话我们任取一条边那么对于\(2\)号点来说，要么没出边，要么出边的终点是\(3\)号点（因为没有长度为\(2

DescriptionP1989无向图三元环计数给定简单无向图\(G=(V,E)\)，求其三元环个数，其中\(\lvertV\rvert\leq10^5,\lvertE\rvert\leq2\times10^5\)。Solution考虑给每一个边定一个方向。具体地，对于原图的一条边\(E=(u,v)\)，有若\(\deg_u>\deg_v\)或\(\text{deg}_u=\text{

题意给定一个有向图\(G\)，以及将所有边反向重连的无向图\(T\)。你最多可以在\(T\)上连续走\(k\)条边，走过每条边的代价都为\(1\)，然后必须在\(G\)的对应点上走一条边以恢复体力。若当前对应点没有出边，则停留在该点\(1\)代价。求每个点到\(n\)的最小代价。Sol考

最大流对于网络\(G=(V,E)\)，给每条边指定流量，得到合适的流\(f\)，使得\(f\)的流量尽可能大。此时我们称\(f\)是\(G\)的最大流。Dinic算法思想考虑在增广前先对\(G_f\)做BFS分层，即根据结点\(u\)到源点\(s\)的距离\(d(u)\)把结点分成若干层。令经过\(u\)

本文首发于QOJhttps://qoj.ac/blog/skip2004/blog/866大家好，我是钱哥，我来写一下PKUSC2024最短路径的题解。没有做过这个题的同学可以先自行做一做。我们下面来讲解一下如何一步步解决这个题目。subtask4首先，我们来解决第一个具有挑战性的子任务：\(m\leq2.5n\)，这个点具

\(\color{red}(1)\)P2296[NOIP2014提高组]寻找道路在有向图\(G\)中，每条边的长度均为\(1\)，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：路径上的所有点的出边所指向的点都直接或间接与终点连通。在满足条件\(1\)的情况下使路径最短。

这道题目实在没有什么好的办法去描述状态空间，只能感性理解一下，等对概率的理解更深了再来吧。。。发现这是一道概率DP，而且满足拓扑序，我们直接倒序转移就好了设\(f_i\)表示从第\(i\)个点到第\(n\)个点的概率，我们发现当只有一条出边是非常好转移的，但是其他就不太行了我们遇到这种

这道题目本身不算难，只是有一点点小的最短路算法的改动我们首先从分层图的角度考虑这个问题，每一层代表一秒钟在第一层，最开始只有\(1\)在集合中，然后我们扫描第一层中\(1\)的所有出边，将终点全部加入到集合中在第二层，我们扫描集合中所有点在第二层中的出边，把不在集合中的终点全部加

欧拉回路感觉自己学了个假的欧拉回路。trick1给定一个图，我们需要给每个边定向，使得每个点入度与出度差不超过\(1\)。\(sol:\)首先，因为有奇数点的存在，我们不能直接构造出欧拉回路。所以我们建立一个虚点，然后从所有奇数点和虚点连边，显然此时所有点度数都为偶数，我们跑欧拉回

当给定一张图后，我们需要存储。下面有三种存储方法。1.邻接矩阵直接用二维数组\(g_{i,j}\)来表示从结点\(i\)到结点\(j\)的距离。空间复杂度为\(\mathcal{O}(N^2)\)。2.邻接表可以发现，邻接矩阵在存稀疏图时，有大量的空间浪费。此时可以使用邻接表存图。邻接表就是对

某人竟然忘记了星期天晚上有\(\text{ARC}\)，我不说是谁。首先选择最小点删除和最小字典序都是最小化，所以可以弱化最小点删除的限制，现在原问题就变成了可以删除任意一个点的出边，如果没有出边则为\(0\)(这个其实本题中是最优的策略)。如果每一个点向其删除的出边连边，先考虑它会形

恶魔的低语，会送来天堂的福音。题意有一个\(n\)个点的有向无环图，第\(i\)（\(1\lei\len\)）个点有mi条有序的出边\(e_{i,1},e_{i,2},...,e_{i,m_i}\)。每个点要么是黑点，要么是白点。有\(k\)个程序，第\(i\)个程序形如从\(r_i\)开始，对\(r_i\)的直接或间接后继

Boruvka最小生成树一个用得相对少的最小生成树算法。需要注意的是只能做边权互不相同的问题。怎么做？首先先将所有点看做独立的连通块。然后对于每个联通块找到最小的一条出边，判了连通性，可以就直接合并就行了。这样每次联通块个数每次都会变为原来的\(\frac{1}{2}\)，所以只

纪念一下第一次补完div1的所有题这个1E相较于其他的1E并不算太难。本题解部分参考官方题解。先观察到一条边是好的当且仅当它的值和一个端点的值相同。原因很简单，要求两端点值不同，若边权跟点权也不同，那么三个值分别只能为\(1,2,3\)，又因为\(1\oplus2\oplus3=0\)，不符

洛谷传送门考虑dp，设\(f_i\)为以\(i\)结尾的合法子串个数。如果我们能对每个\(i\)，求出来\(g_i\)表示最大的左端点\(l\)使得\([l,i]\)是合法串，那么\(f_i=f_{g_i-1}+1\)。若\(g_i\)不存在则\(f_i=0\)。答案为\(\sum\limits_{i=1}^nf_i\)。考虑求\(g_

考虑给无向图定向，设\(d_u\)为点\(u\)的度数，对于无向边\(\langu,v\rang\)，若\(d_u<d_v\)或\(d_u=d_v\)且\(u<v\)，我们在新图中连有向边\(\langu,v\rang\)，否则连有向边\(\langv,u\rang\)，容易发现新图必然是一张DAG。我们枚举三元环中的一个点\(x\)，在新图中同时标记

T1大水题，用位运算更加便捷求解。T2看出来有环了，但是没往基环树上想，寄。暴力分，有部分分是基础树，可以跑一遍深搜，根节点的选择是k种颜色，剩下的是k-1种颜色。还有暴力是可以二分图染色做出来的。正解，我们对于一个环上的操作，可以用递推式子求出来。f[0][i],f[1][i]分别表

这是之前关于欧拉路的两篇博客。关于欧拉路的逆序压栈问题：here。22年写的一个小总结：here。关于欧拉路，主要疑点在于两个：一是压栈输出的原理；二是打上标记后时间复杂度退化的问题。压栈输出的原理走到点u时，有两种情况：u此时是终点，那么没有没走过的边与之相连。u此时不是终点

概述定义基本规则：两个玩家轮流移动同一颗棋子。每次移动沿一条出边将棋子移到下一个点。当前玩家走不了（没有出边）时输。图可能有环，游戏无法结束时为平局。出现平局的根本原因是决策会绕起来成环。我们先来解决如何判断一个点的胜负状态。首先，如果图是\(\text{DAG