win_the_medal

分类

Codeforces(14) Codeforces (Div.3)(6) kuangbin带你飞——搜索专题(9) STL(4) UVA(2) 动态规划--01背包(1) 动态规划--最长上升子序列(1) 动态规划--最长公共上升子序列(1) 动态规划--最长公共子序列(1) 动态规划--简单DP(4) 图论--SPFA(3) 图论--二分图(1) 图论--差分约束(3) 图论--最小生成树(3) 图论--最短路(10) 字符串--AC自动机(4) 字符串--hash(7) 字符串--KMP(4) 字符串--Manacher(3) 字符串--后缀数组(13) 技巧--二分查找(5) 技巧--前缀和(5) 技巧--大数运算(6) 技巧--尺取法(5) 技巧--拓扑排序(2) 技巧--数据离散化(1) 搜索--BFS(3) 搜索--DFS(20) 数学--gcd和lcm(1) 数学--中国剩余定理(2) 数学--博弈论(2) 数学--快速幂(1) 数学--拓展欧几里得(1) 数学--欧拉函数(1) 数学--矩阵快速幂(1) 数学--素数筛(5) 数学--逆元(1) 数据结构--fhq Treap(2) 数据结构--LCA(1) 数据结构--ST表(2) 数据结构--主席树(1) 数据结构--划分树(1) 数据结构--单调栈与单调队列(4) 数据结构--字典树(5) 数据结构--并查集(4) 数据结构--替罪羊树(1) 数据结构--树状数组(4) 数据结构--树链剖分(8) 数据结构--线段树(15) 牛客(1) 算法--BFPRT(1) 算法--枚举(1) 算法--模拟(7) 算法--贪心(2)

/ 注册

全部文章（共216篇）

multiset用法

c++语言中，multiset是<set>库中一个非常有用的类型，它可以看成一个序列，插入一个数，删除一个数都能够在O(logn)的时间内完成，而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。简单的运用： int main() { //fre...

2019-07-30

0 845

poj3660 Cow Contest（Floyd-Warshall方法求有向图的传递闭包）

算法实现原理由于我们只需要确定节点对(i,j)之间是存在i->j的路径，所以，对于松弛操作可以有两种优化方式，(1)将所有节点对之间的存在的直接连通的边权重设为1，不连通设为0。然后运行该算法，如果mp[i][j] = 1;则（i，j）之间存在一条简单路径。如果mp[i][j] = 0,则...

2019-07-30

0 432

差分约束

一类不等式组的解给定n个变量和m个不等式，每个不等式形如 x[i] - x[j] <= a[k] (0 <= i, j < n, 0 <= k < m， a[k]已知)，求 x[n-1] - x[0] 的最大值。例如当n = 4，m = 5，不等式...

2019-07-30

0 807

POJ - 3259 Wormholes（求负权回路）

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path tha...

2019-07-30

0 481

POJ 1860 Currency Exchange（BellmanFord算法的变形，求正环）

Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchang...

2019-07-30

0 314

Bellman-Ford算法

Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼（Ric...

2019-07-29

0 732

POJ 1990 MooFest

每年，农夫约翰的N（1 <= N <= 20,000）只牛会参加“MooFest”，一个来自世界各地的牛的社交聚会。 MooFest有许多活动，包括干草堆积，篱笆跳跃，把尾巴钉在农夫的身上...当奶牛都站在同一个地方排队，他们会大声喊叫，吼声几乎震耳欲聋。事实上，每年参加了这个活动后，一...

2019-07-29

0 394

POJ3067:Japan(树状数组求逆序对)

Description Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the venue. Japan is tall island with N cities on th...

2019-07-29

0 500

树状数组求逆序对

首先，先让我们了解下逆序对的概念：如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。现在直接拿POJ-2299作为例题来说下这个逆序对吧 ...

2019-07-29

0 511

树状数组

树状数组基础树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改&&区间求和. 另外一个拥有类似功能的是线段树. 具体区别和联系如下： 1.两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树. ...

2019-07-29

0 395