小衣同学的博客

2^i步的点连着2^(i-1)步的两个点，也是一棵入树、一棵出树，每棵树的点的总数是nlogn。1 a b c，要求点a到点b的简单路径上，最小值位于点c处，保证c在a到b的简单路径上。2 a b c，要求点a到点b的简单路径上，最大值位于点c处，保证c在a到b的简单路径上。n(n

可以把4n枚小石子看做是2n对，即(1,4n),(2,4n-1),...,(2n,2n+1)4n个石子中，1,2,6,9为A颜色，3,4,5,11为B颜色，7,8,10,12为C颜色，②由于欧拉回路中，点[i]的入度和出度相等，in和out时在序列中的奇偶性也不同。石子对的内部进行连边，即对于1w，则序列写做u,v,v,w，对于每个点，建好图后，发现颜色的n个点，每个点的度均为4，

计第i个点入度为in[i]，出度为out[i]，则第i个点费用为max(in[i],out[i])，最小化max(in[i],out[i])，由于in[i]+out[i]是固定的，为点i对应的度，若图有欧拉回路，则in[i]=out[i]，abs(in[i]-out[i])=0。求一种定向方案，使得n个点的最大费用最小，若有多种方案，任意输出一种。由于对于奇数度的点来说，abs(in[i]-out[i])至少为1，另一种写法时，不实际把虚点建出来，从奇数度的点开始搜，新图每个点都是偶数，自然有欧拉回路，

Nebius Welcome Round (Div. 1 + Div. 2) F. Approximate Diameter(构造/图论性质+二分+最短路)

AtCoder Beginner Contest 277 F. Sorting a Matrix(拓扑排序+虚点)

The 17-th Beihang University Collegiate Programming Contest (BCPC 2022) - Preliminary L.逃跑路线(思维/二分图)

题目t(t<=50)组样例，每次给定一个长度为2*n的序列，且每个1到n的数恰好出现两次，圆环上等距离分布着1到2*n这2*n个点，数值相同的点要么在环内连边，要么在环外连边，问给定的序列是否可以连边，使得边两两不交，如果可以输出yes，否则输出no自己的一点想法官方给出的题解，已经被找出了反例1 4 1 2 3 2 4 3 1 4队友请教了一下@泛白老哥，得出了一个主席树的做法自己又仔细想了想，感觉这个主席树，好像不太有必要所以，根据这个主席树，手撸了.

题目m(1<=m<=1e5)个数组，第i个数组的长度为ni（2<=ni<=2e5，ni为偶数）第i个数组内的第j个值aij(1<=aij<=1e9)，sumni<=2e5问是否能把这些整数分成两个multiset，不妨称为L集合和R集合，使得每个数组内恰有一半元素在L集合内，另一半元素在R集合内，且L集合和R集合最终是相同的multiset思路来源palayutm、wifiii代码题解如果想到欧拉回路的构造，就很好做了首先

题目输入一个n(n<=1e3)，代表n个点的完全无向图，你需要输出n-1行，分别代表长度为1,2，...，n-1的链上经过的点，使得每条链在原图中都是连续的，且任意两条链之间没有交边思路来源题解①n是奇数，欧拉回路，注意弧优化②n是偶数，考虑长为n-2和n-1的两条链如何构造，令a=n-1，b=n，使a和b交替穿插在[1,n-2]个点里，并最后回到b，最终构成a-1-b-2-...-b-(n-2)-a-b的一个长为2*n-3的链，然后拆成n-2和n-1的两条链

题目n(n<=2e5)个点，m(m<=2e5)条边的有向图，每个点的出度最多为k(k<=9)，m条边每条边都有一个权值，m条边构成了1-m的一个排列，求合法的k元组(c1,...,ck)的数量，使得任意出度为i的点沿着第ci小的权值走向下一个点时，能遍历全图思路来源disangan233代码题解注意到ci<=i，所以所有k元祖数量级是9!的，能遍历全图，说明所有点构成了一个环每个点的入度和出度都恰好为1，先检查出度，如果存在出度为0的直接输出0

题目n(n<=5e5)段项链，第i段左端ai右端bi(0<ai,bi<2^20)，两段项链ij可以拼接在一起，中间产生的值是i的一端u和j的一端v所产生的贡献，贡献计算方式是最大的k，满足(u^v)%(1<<k)=0，即最大的k满足2的k次方能被u异或v的值整除，特别的，如果u=v，k被记作20，要求把i串项链串成一串项链时，链上最小的贡献的最大输出这个贡献，并输出最终的项链上的珠子是怎么摆放的，第i段左端珠子边号2*i，右端边号2*i+1思路.

题目思路来源官方题解题解代码#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<cmath>#include<set>using namespace std;typedef pair<int,int> P;const int N=5e5+10;vector<P>e[N];P

题目该有向图有n(n<=10)个节点，节点从1 至n编号，windy 从节点1出发，他必须恰好在t(t<=1e9)时刻到达节点n。现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？答案对2009 取模。注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。有向图用邻接矩阵的形式给出，a[i][j]只为0-9...

题目思路来源https://oi-wiki.org/graph/min-circle/题解OI Wiki里给出了几种最小环的实现方法，然而最短路的复杂度都比较鸡肋有向图最小环，代价不为1的时候似乎只能用floyd搞，与无向图最小环的floyd不同，有向图比较方便，开始置dis[i][i]=INF，最后枚举环的必经点i，从而来确定最小的环有向图最小环...

题目共有n(n<=2e5)个人，第i(1<=n<=个人)指向的人是ti显然是个出度均为1的有向图，求该图的最小环的大小，输出大小思路来源https://www.cnblogs.com/SINXIII/p/10374689.html题解三种做法，①强连通分量，上个tarjan板子，求最小size的，输出即可②拓扑排序，注意到能清掉的点一定不在环上，...

题目n(n<=100)个点，m(m<=1e4)条边的无向图，第i条边的代价为ci(0<=ci<=500)，无自环，可能有重边，要求输出最小环上的点，若有多解，输出一解即可思路来源https://www.cnblogs.com/TengXunGuanFangBlog/archive/2013/04/19/loop_problem.html题解pre...

题目n(n<=100)个点，m(m<=1e3)条双向边，第i条边代价c(c<=100)元，从V1出发，假设经过的路线为V1,V2,....VK,V1，那么必须满足K>2，即除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。能找到输出最小代价，不能找到输出It's imposs...

题目n(n<=1e5)个纯小写字母组成的单词，第i个单词长为|si|(|si|<=1e3)你可以取一个或一些单词，使得第一个单词的末两位与第二个单词的首两位相同，第二与第三，……，最后一个的末两位与第一个的首两位相同每个单词只能用一次，假设你取了k个单词，单词总长是len，输出最大化的len/k的值题解单纯想总结一下，最大平均环问题将每个单词最开始的两个字母...

题目给你一个n(5<=n<=1e5)个点m(n-1<=m<=2e5)条边的无向图，保证图连通你可以选择以下两种之一来输出：记①输出一个正好为d的独立集，输出这些点，使得两两之间无边②输出一个长度不小于d的简单环，输出这些点思路来源https://www.bilibili.com/video/av96374512dls的B站讲解https:/...

题目n(n<=1e5)个数，第i个数为ai(1<=ai<=1e6)，保证ai最多有7个因子找出这个数组的最短子序列，使得子序列内的所有元素的乘积是一个完全平方数输出这个最短子序列的长度思路来源https://www.bilibili.com/video/av96374512dls的B站讲解https://codeforces.com/contest/13...

题目思路来源定理：任何竞赛图都有哈密顿路径，强连通的竞赛图有哈密顿回路证明：https://blog.csdn.net/unsolvedmys/article/details/73608770题解竞赛图，相当于对C(n,2)条边的完全图定向，定为有向图由定理，对于任意竞赛图，最长链长度都为n所以，长度为1到n-1时输出0，为n时输出2的C(n,2)次方代码...

题目时间限制：1s空间限制：256MB有一天，一位灵魂画师画了一张n个点m条边(1≤n≤1e5,0≤m≤2e5)的图。现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。一共两个子任务：这张图是无向图。（50分） 这张图是有向图。（50分）图中可能有重边也可能有自环。如果不可以一笔画，输出一行 “NO”。否则，输出一行 “YES”，接下来一行输出...

题目给一个n(n<=1e5)个，点m(m<=n*(n+1)/2)条边的图，图本是完全图，这m条边的代价都为1，其余的边的代价都为0，求这个图的最小生成树的代价，输出代价思路来源官方题解题解考虑把0边的在并查集都合在一起，忽略1边，就变成了补图x个连通块，使x个联通块相同必须用1的代价，答案即补图连通块个数-1，一条边只在点号大的时候考虑一次，对于一个...

 题意给定一个有环图，把这个图变成DAG可以将一些边反向，反向的cost为边权多条边反向为这些边边权的最大值求如何反向使cost最小，输出cost、边数和边集题解二分一个值ans，先不管比这个小的边权的边，取只有比这个大的边权的边和所有顶点的生成子图，二分出生成子图无环的最小值ans，dfs判环/拓扑判环均可//各写了一个然后对生成子图拓扑排序，...

题解3个点（含）及以下的显然不行，2条边（含）及以下的显然不行，没有3种颜色的显然不行，剩下的一定可以。思路来源出题方题解1.连通图才有生成树，所以要先判图是否连通2.图中需要出现至少一条R边，一条G边，一条B边3.生成树的边数&gt;=3 (R*1+G*1+B*1),所以n&gt;=4不考虑重边和自环，满足以上三个条件的图一定有解证明：图连通，可...

题意给一个图，图上的点可以被染成权值为1,2,3令边权=两个点的点权和，求令边权为奇数的所有方案数%998244353思路来源自己写的题解首先二分图判定一下，分奇偶层；奇层染奇数，偶层染偶数；或奇层染偶数，偶层染奇数。对于每个连通分量，其方案数为（modpow(2,奇层点数，MOD）+modpow(2,偶层点数，MOD））%MOD这个modpow是快...

题意：给定n个昆虫，m对异性关系，问是否存在同性恋。思路：建无向图然后二分图判定200W条边可以过，但这题网上搜题解的时候搜到一个并查集的方法，很神奇，码住码住。即用op数组记录自己的一个异性①，然后再遇到自己的异性②时将异性①、异性②合并到一个集合里去。如果没出现可能的冲突的话，就说明这一对关系不影响题意，即任意其一为任一性别，另一为相反性别即可。核心：敌人的敌人是朋友呐QAQ...

东北地区赛有个无向图判自环的题当时没苟出来，回来之后想了想用并查集可以实现，然后仔细查了一波还有哪些方法……总结一波博客吧QAQ……资源来源：https://blog.csdn.net/ouyangruo/article/details/51057409https://blog.csdn.net/acmdream/article/details/72983715http://w...

题目给你一张图，n个点m条边，以下m条无向边ui，vi，wi你可以令某条边权值加1，视为一次操作，问，令最小生成树唯一时，最少操作数是多少思路来源https://www.cnblogs.com/shuaihui520/p/10320158.html题解考虑Kruskal加边过程，一条边在合并的时候，u和v已然在一个集合，加入这条边会成环，不取而剩下的边，加入...

题目给你一棵N个节点的树，并多加一条边，也就是N条边要你输出图中唯一的一个环，即按增序输出环上点的标号1<=N<=100000思路来源http://www.cnblogs.com/shoulinniao/p/10423674.html题解本来被自己dfs瞎搞搞过去了但想到topo也挺重要的，之前敲得也不多之前一般是用于有向图的情形，现在发现无...

思路来源https://codeforces.com/blog/entry/61311（官方题解）https://www.cnblogs.com/tobyw/p/9513876.html（E题）D.Mouse Huntn(n<=2e5)个房间，有一只老鼠，可能在t=0时出现在任意房间，第i个房间放捕鼠夹的代价是ci(1<=ci<=1e4)，在这一秒出现在i...

题目n(n<=100)个点，m(m<=1e3)条双向边，保证点最大的度数不超过20（不知道有啥用，照顾时限叭）求恰为s(2<=s<=10)大小的团的个数团即为一个点集，该点集中的点两两之间都有边，又称完全图思路来源https://www.cnblogs.com/kkkkahlua/p/7704245.html题解暴搜，要加入一个点的时候，判断...

题意求n(n<=100)个点的一般图的最大点独立集等于求补图的最大团，暴搜思路来源https://blog.csdn.net/Icefox_zhx/article/details/79593200题解暴搜，注意调整搜索顺序，枚举取还是不取，取当且仅当和之前的团都有边，不取当且仅当剩下的还能比res大代码#include<iostream>#...

题目n(n<=100)个点，m(m<=3e3)条边，1-m条边，第i次独立在原图中删掉第i条边，问删掉这一条边之后，所有点对(i,j)之间的最短路之和的值是多少如果有一对不连通，输出-1思路来源https://blog.csdn.net/a709743744/article/details/51559569https://blog.csdn.net/Todo...

题目思路来源https://www.cnblogs.com/jiachinzhao/p/7474761.html题解本来看了题解，也没大懂，好在归神讲了讲只会暴力check这一种做法对于for(u=1;u<=n;++u)来讲①考虑所有u为度数>sqrt(m)的点，(1)如果v为度数>sqrt(m)的点，就去for循环u，枚举的是形如u-vv...

思路来源：https://blog.csdn.net/riba2534/article/details/79319597题目描述这个挖矿游戏会给出一个n*m个格子的地图，每个格子都有黄金。在游戏开始时小明会随机出现在地图的某一个格子当中。小明可以将他所在的格子的黄金收归囊中，并且还可以向下或者向右移动，然后继续收集黄金。地图上某些格子是障碍物，小明不能移动到有障碍物的格子上。不过，在游戏...