查看原题请戳这里 我没看过电影qwq…… 刚开始看到这个题，觉着可以用Floyd去做，时间复杂度为n^3…… 于是…… 我们还是用并查集好了当然了，如果我们在每次删去一个点后就跑一遍并查集去统计联通块的数量，那么一定会超时的。 所以，我们要用另一种方法…… 倒着做！然后，我们先把所有将被干掉的 ...

查看题目请戳这里 又一道欧拉回路的裸题把字母hash一下，然后跑一个欧拉回路就可以轻松搞定。 不会欧拉回路的戳这里。 附一下代码： #include<iostream> #include<cstdio> #include<cstring> #include< ...

查看原题请戳这里因为每条边都只能走一次，所以这道题可以用欧拉路的性质来求解。我们首先用并查集去记录每一个联通块，然后再统计每一个子图的奇点数，如果是偶数则满足欧拉回路的性质直接ans++ 就好了，如果是奇数，那么需要的蚂蚁数则是奇点数/2附一下代码： 12345678910111213141516 ...

前言SPFA算法由于它上限O(NM)的时间复杂度,被卡掉的几率很大.在算法竞赛中,我们需要一个更稳定的算法:dijkstra 什么是dijkstra?dijkstra是一种单源最短路径算法,时间复杂度上限为O(n^2)(朴素),在实际应用中较为稳定;加上堆优化之后更是具有O((n+m)log^2 ...

查看原题请戳这里我们用单调栈来维护每一个小矩形的左侧和右侧第一个比它低的矩形的位置。为什么要维护这个呢？根据木桶原理，每一个大矩形的高度是由其高度最小的矩形的高度决定的，所以我们要去记录第一个比当前矩形小的矩形的位置。ps：别忘了初始化qwq……附一下代码： 1234567891011121314 ...

查看原题 一道非常简单的数论题为什么说它非常简单呢？可能大家刚开始看到那个式子会有点懵，但是如果你把求和函数展开就会发现，式子会变为 a[n] - a[n-1] + a[n-1] - a[n-2] + … +a[2] - a[1]然后你就会发现这个求和函数的值只与an与a1的值有关…… 于是这个题 ...

ARX：我今天上午做了两个分层图最短路的题，可简单了……概念 分层图最短路是指在可以进行分层图的图上解决最短路问题。一般模型是：在图上，有k次机会可以直接通过一条边，问起点与终点之间的最短路径。 算法思路这是一个类似于DP的思路。用直接通过的边把整个图分成k个子图，其中k为可以直接通过的边的个数 ...

查看原题请戳这里 突然感觉qxy和小z是同种生物莫队的一道裸题虽说莫队算是一种暴力的算法，但ta依然是某些题目的正解的。（dfs：我不服） 这道题是需要我们经过一定的数学推导才可以做出来的。具体过程如下：对于L,R的询问。 设其中颜色为x,y,z的袜子的个数为a,b,c… 那么答案即为 (a*(a ...

·拓扑排序是什么呢？我们先来看一下标准解释：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topo ...

直到敲完这个题，我才发现原来prim如果用邻接矩阵存图即使加上堆优化时间复杂度依然是O(n2)qwq…… 首先，由于两个点只需要间接联通就可以互相通讯，所以这道题可以用最小生成树去做。这一步比较好完成。 问题在于怎么去加卫星电话。由于两个点只要间接联通就可以，那么每一个用无线电收发器连成的 ...