强烈推荐的tarjan解释 HDU 3861 The King’s Problem 缩点后得到新图，在新图上跑最小路径覆盖，得到答案 The King’s Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4653 Accepted Submission(s): 1567 Problem Description In the Kingdom of Silence, the king has a new problem. The...

逆元 逆元满足：     a   ∗   i   n   v   (   a   )   ≡   1   (   m   o   d    a*inv(a)≡1(mod   a∗inv(a)≡1(mod      p   )    p)   p) 1.模     p    p   p为素数的逆元 利用费马小定律:      a    p   −   1     ≡   1   (   m   o   d    a^{p-1}≡1(mod   ap−1≡1(mod      p   )    p)   p) 则     i   n   v   (   a   )   =    a    p   ...

HDU 4089 Activation(推导公式) Activation Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5214 Accepted Submission(s): 1732 Problem Description After 4 years’ waiting, the game “Chinese Paladin 5” finally comes out. Tomato is a crazy fan, and luckil...

概述 所谓线性基，就是线性代数里面的概念。一组线性无关的向量便可以作为一组基底，张起一个线性的向量空间，这个基底又称之为线性基。这个线性基的基底进行线性运算，可以表示向量空间内的所有向量，也即所有向量可以拆成基底的线性组合。 定义 设数集     T    T   T的值域范围为     [   1   ,    2   n    −   1   ]    [1,2^n−1]   [1,2n−1]。      T    T   T的线性基是     T    T   T的一个子集     A   =    A=   A={     a   1   ,   a   2   ,   a   3  ...

利用DFS 由于每个顶点和每条边都只访问了一次，因此 复杂度为O(V+E) const int maxn = 1e4+10; vector<int> g[maxn]; int n; //顶点数 int color[maxn]; //顶点i的颜色，1 or -1 bool dfs(int u, int c) { color[u]=c; for(int i=0; i<g[u].size(); ++i) { int v=g[u][i]; if(color[v]==c) return false; if(color[v]==0 && !dfs(v,-c)) retur...

链接：https://ac.nowcoder.com/acm/contest/923/D 来源：牛客网 题目中隐含条件是给的图是一个 DAG，那么就是一个 DAG上求单源最短路的问题。首 先是肯定能写出一个      O   (    n   2    )    O(n^2)   O(n2)的 DP，然后因为每条边的边权是两个点之间的叉积。叉积的几何意义为有向面积的      2    2   2 倍。所以我们将所有向量画到直角坐标系中，并且按照极角排序，所求最短路就是让你选取平面中的若干个点，使得这个几何图形的面积最小。 y 均为正数，这个图形应该是越下凹面积越小。使用单调栈维护这个下凹的凸...

弦论 一道板子题，让我感觉板子题都还不会。。。然后把递推写成dfs时没有给string加上&，导致内存爆了，2333，果然还是传引用好 题意：求字典序第K小子串以及本质不同的第K小子串 思路：  正常的建好后缀自动机 由于处理一个节点有多少endpos以及经过一个节点有多少子串都需要将所以节点按len从大到小排序，因此就不采用topo排序了 利用一次计数排序，即可完成长度排序，得到长度第i短的子串为a[i] 然后就是进行两个处理：endpos(cnt数组)大小以及size大小 最后是贪心的构建字典序第K小子串，但要记住当前节点字典序要比在后面增添字符后的字典序的小，所以要先考虑当前节点...

闲谈一下 树状数组最基本的功能是加速前缀和的更新。 查询一个数组的前缀和本来是O(1)的复杂度，用树状数组则为O(logn)。 但树状数组优点在于单点更新时复杂度为O(logn)，而正常的为O(n)，这也就使得树状数组能够进行大规模的更新。 虽然查询速度(O(logn))稍有些慢(相对于O(1)而言)，但依旧可以用于大规模的查询。 总之，遇到有不断更新的数组前缀和时可以考虑树状数组。 树状数组求区间最值 就像线段树一样，我们一开始接触线段树时一般也是求区间和，学会以后发现仅仅需要将sum改成max就能求出区间最值，既然可以将树状数组理解为线段树的单点更新版本，那树状数组又如何呢？ 事实上，树状...

洛谷最近公共祖先模板题 题目描述：给出一棵有     N    N   N个节点的树，有     M    M   M个询问，每个询问为     u   ，   v    u，v   u，v节点LCA      N   ,   M   <   =   5   e   5    N,M<=5e5   N,M<=5e5 倍增实现 复杂度：     O   (   n   l   o   g   n   )    O(nlogn)   O(nlogn) 此模板最小节点标号为1 #include "bits/stdc++.h" using name...

废话不多说，直接上模板 #include "bits/stdc++.h" #define pb push_back #define ls l,m,now<<1 #define rs m+1,r,now<<1|1 using namespace std; typedef long long ll; typedef pair<int,int> pr; inline int read() { int x=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>...

题目描述 如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和 输入输出格式 输入格式： 第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。 接下来一行包含N个非负整数，分别依次表示各个节...

game with numbers 给定大小为     n    n   n的集合     S    S   S 一个数被称作合法的，当且仅当     x   ∈   S    x∈S   x∈S或者     x    x   x存在大于1的真因数，且这些真因数均是合法的 求有多少个数     x    x   x满足     2   ≤   x   ≤   m    2≤x≤m   2≤x≤m且     x    x   x合法 PS:     x    x   x的真因数指不是     x    x   x本身的约数 T组数据 每组数据给定     n   和   m    n和m   n...

原题地址 食物链 动物王国中有三类动物      A   ,   B   ,   C   ，    A,B,C，   A,B,C，这三类动物的食物链构成了有趣的环形。     A    A   A 吃      B   ，   B    B，B   B，B 吃      C   ，   C    C，C   C，C 吃      A    A   A。 现有      N    N   N 个动物，以      1   －   N    1 －N   1－N 编号。每个动物都是      A   ,   B   ,   C    A,B,C   A,B,C 中的一种，但是我们并不知道 它到底是...

极为舒服的 计算几何终极模板+总结 小知识点 //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back #define ls l,m,now<<1 #define rs m+1,r,now<<1|1 #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<'='<<(x)&lt...