原题链接传送门拓扑排序：我们可以这样来理解：就是一些子工程需要建立在另一些子工程的基础上，然后从入度为零的点开始，把这个点一个一个放进一个序列里，建立一个线性的数的序列，这些数列有至少1种。（解释很粗糙，别介意）；当且仅当一个有向图为有向无环图（directed acyclic graph，或称DAG）时，才能得到对应于该图的拓扑排序。按照（wo）这（de）种（tu）方法直接...

思路这道题其实主要的难点是如何排序。排序之后贪心就非常简单了。考虑贪心邻项交换设 si=∏j=0iajs_i=\prod\limits_{j=0}^{i}a_jsi​=j=0∏i​aj​。首先考虑交换前，第 iii 个上的值是 si−1bi\frac {s_{i-1}}{b_i}bi​si−1​​，第 i+1i+1i+1个 是 si−1×aibi+1\frac {s_{i-1}\times a_i

这道题思路很巧妙。我们先假设所有的犯罪团伙都被打击掉了，那么此时我们重新从 n−>1n->1n−>1 复活犯罪团伙（也就是将它们并在一起）。当我们发现无论怎么并，犯罪团伙的危险程度都>n/2>n/2>n/2时，就停止并操作。此时我们直接输出 iii 即可。( iii 为当前被打击掉的团伙)代码：#include<iostream>#include&l

位运算

并查集详解武侠版

考试时没想出来，打了个30分暴力dfs交了上去。结果爆0，发现直接炸数组，自闭了。。。正解就是一个模拟，我们拿样例来讲首先排序：然后直接开始模拟，神奇炸了！代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using

思路这道题是线段树模板题但是不同于上一题，这道题是区间修改，所以我们引入lazy tag。因为如果直接对线段树的每个儿子进行修改，时间会超限，所以我们把父亲的值直接传给左右儿子，然后用lazy tag来标记，当需要用到当前子树时就继续传递lazy tag就好了。代码#include<iostream>#include<cstdio>#include<cmath>

思路这道题是经典的二分题，但是也可以用倍增做。这道题的倍增很容易，就从0开始不断从大到小往后跳，当然范围不能超过n，大小也不能超过x，能跳就跳。最后就会跳到小于x的最后一个数，加一输出就好了。（如果加一不是x就输出-1）代码#include<iostream>#include<cstdio>using namespace std;int n,m,a[1000010],x,a

这道题是LCA模板题！LCA：基于有根树最近公共祖先问题在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先，这个祖先节点即为lca。同时lca一定是u、v路径上的点。开标解释：#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include

思路这道题首先可以发现要找最大字符串的子串来看是否有ABA型，然后直接超时，发现可以直接枚举左端点，大的子串可以包含小的右端点子串。于是枚举每一个左端点，然后求next，把这个子串中所有ABA找出来，然后找的过程也可以用 k=next[k]k=next[k]k=next[k] 来找,当然一个ABA还要满足题目中的两个条件才行。代码#include<iostream>#include&l