牛客多校第十场总结  A Rikka with Lowbit  期望的定义，前缀和 J Rikka with Nickname  预处理，字符串  D Rikka with Prefix Sum  组合数学，树状数组  F Rikka with Line Graph  归并排序，dp  H Rikka with Ants  计算几何，斜率转化  E Rikka with Equation  中国剩余定理，容斥原理  G Rikka with Shortest Path  树dp  B Rikka with Burrow-Wheeler Transform  BWT+线段树+归并  I Rikk...

优化失配函数  #include <bits/stdc++.h> #define mem(ar,num) memset(ar,num,sizeof(ar)) #define me(ar) memset(ar,0,sizeof(ar)) #define lowbit(x) (x&(-x)) using namespace std; typedef long long LL; typedef unsigned long long ULL; const int prime = 999983; const int INF = 1e8; const LL INFF =0x7FFFFF...

1005GuGuFishtion 数论题,预处理+容斥   后面的部分可以用容斥做,令     F[k]=∑i=1i=M∑j=1j=N[gcd(i,j)=k]    F   [   k   ]   =  <munderover>  ∑    i   =   1     i   =   M   </munderover> <munderover>  ∑    j   =   1     j   =   N   </munderover>  [   g   c   d   (   i   ,   j   )   =   k   ]         F...

1001 wa了两发，SPFA不熟练  1010 矩阵快速幂+分块，一看到这道题就有思路分块写，无奈能力对于n/i的特性还是不是很了解，调试了半天，花了好长时间才通过  1005 公式推出来了，化简不会了，对于容斥原理和莫比乌斯反演还是不够熟练  一个暑假过去了还是只会写水题，我好菜啊 1001 跑SPFA+set记录状态贼快，然后就没有然后了 #include <bits/stdc++.h> #define mem(ar,num) memset(ar,num,sizeof(ar)) #define me(ar) memset(ar,0,sizeof(ar)) #define lo...

最小生成树  Prim算法(普利姆算法)  关键问题   Krustral算法(克鲁斯卡尔算法)  关键问题   最小生成树扩展          最小生成树 首先, 什么是最小生成树  图论基础 Prim算法(普利姆算法) 采用prim算法解决生成树问题   假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U,TE初值均为空集。 首先从V中任取一个顶点（假定取v1），将它并入U中，此时U={v1}，然后只要U是V的真子集(U∈V)，就从那些一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短边，设为(vi ,vj ),其中vi ∈U, vj ∈V-U，并...

sublime 配置  下载,安装sublime 安装编译器 配置g++环境变量 配置sublime 写一个hello world 程序 其它的编译build命令          sublime 配置 下载,安装sublime https://www.sublimetext.com/3 安装编译器 如果已经安装dev或者codeblocks，找到安装目录下的mingW  例如dev cpp 的路径 C:\Program Files (x86)\Dev-Cpp\MinGW64\bin 如果没有编译器，需要额外下载编译器 配置g++环境变量 将C:\Program Files (x86)\Dev...

二分图最大权匹配 hdu2255   hdu 6346   分析 同类题还有  Golden Tiger Claw UVA - 11383  这是根据二分图KM算法的性质求解特殊的线性规划问题  6364求得最小，需要取相反数，然后求最大  对于2255 ,普通的O(n^4) 都能通过，  但是对于6364 ，O(n^3) 才能通过  感到诡异的是在6364中通过的代码竟然没有其他的代码在2255中跑的***到窒息 #include<bits/stdc++.h> using namespace std; #define LL long long const int inf = 0x...

文章目录   二分图定义  二分图判定 二分图算法  匈牙利算法求最大匹配  KM算法求最大权完美匹配 邻接表存图  稳定婚姻问题 二分图相关定理  ①最小路径覆盖： ③最大独立集=总数-最小覆盖集证明：  例题      二分图定义 ###什么是二分图 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。 二分图判定 二分图判定 二分图算法 博客推荐 ：链接  二分图二•二分图最大匹配之匈牙利算法 相关定理  匈牙利算法求最大匹配  遍历左...

latex 使用中文和语法高亮 转载自原网址 1 先安装python，并在选择的时候选择将路径加到环境变量中  2 点击 点击上面的链接，下载这个python文档运行  3 然后在cmd命令行运行easy_install Pygments  4   \documentclass[CJK]{cctart} \usepackage{minted} \begin{document} \begin{minted}{c++} int main() { printf("hello, world"); return 0; } \end{minted} \end{document} 测试就...

牛客网多校第五次总结  A gpa B div C grf D inv E room F take G max H subseq I vcd J plan     牛客网多校第五次总结 A gpa 01 分数规划的原题，二分平均值就行了 B div 公式题 C grf 全场只有一个人过 D inv 逆序数 E room 二分匹配的模板题 F take 树状数组求之前比它大的都不出现的概率，然后注意100%的情况就行了 G max 水题 H subseq 可持续化线段树或者树状数组 I vcd 分|S| 的大小讨论 J plan 水题  判断，多判断就行了

Problem E. Matrix from Arrays 打表发现是2L*2L 的矩阵重复出现，然后预处理2L*2L的矩阵的前缀和就行了，之后求一下有多少完整的矩形，有多少一部分矩形的  #include <bits/stdc++.h> #define mem(ar,num) memset(ar,num,sizeof(ar)) #define me(ar) memset(ar,0,sizeof(ar)) #define lowbit(x) (x&(-x)) #define Pb push_back #define FI first #define SE second #d...

文章目录   Problem A. Integers Exhibition Problem B. Harvest of Apples Problem C. Problems on a Tree Problem D. Nothing is Impossible Problem E. Matrix from Arrays Problem F. Travel Through Time G. Depth-First Search Problem H. Eat Cards, Have Fun Problem I. Delightful Formulas J. Let Sudoku Rotate Prob...

C. Dynamic Graph Matching    题意 分析 参考代码      C. Dynamic Graph Matching 题意 给定一个 n 个点的无向图，m 次加边或者删边操作。  在每次操作后统计有多少个匹配包含 k = 1, 2, …,n/2 条边。  匹配的定义： 边的集合，没有共同的顶点 分析 先把匹配的概念转换，n个边的匹配，就是n条边没有共同的顶点，那就是2*n个点，没有共同的边  那么问题就转化成点,  1,2,3....n/2    1   ,   2   ,   3....   n    /    2   条边，其实就是  2,4,6,8,..n    ...

杭电多校第三场  6319 Problem A. Ascending Rating 倒着维护最大值的单调队列 int a[maxn], b[maxn], deq[maxn],c[maxn]; void solve(int n,int k){ int s = 1,t = 1; for(int i = n;i >= 1; --i){ while( s < t&& a[deq[t-1]] <= a[i]){ t--; } deq[t++] = i; if(n-i+1 >= k){ b[i] = a[deq[s]]; c[i] = t-s; if(deq[s] ...