YZBPXX

分类

acm入门练习(1) c#(1) c++，c实用小函数，操作(20) hash/bkdr hash字符串(2) 动态规划—树形dp(1) 动态规划—背包九讲(7) 单调栈(1) 图论—bfs(2) 图论—dfs(6) 图论—最小生成树(1) 图论—最短单源路径(5) 字符串—ac自动机(1) 字符串—扩展KMP/KMP(4) 字符串—马拉车(1) 带权并查集(2) 拓扑排序(2) 数据库学习(6) 数据结构—RMQ(5) 数据结构—字典树(1) 数据结构--红黑二叉树(1) 数论(8) 未归档(2) 矩阵快速幂(1) 算法分析(3) 网络流(1) 集训题(2) 题解(33)

/ 注册

全部文章（共22篇）

网络流初步

先摆上网络流的经典问题：给你一个图，每条边表示能过通过这条变的最大流量，问你从源点最多流多少到终点然后介绍增广路算法：每次选一条从起点到终点的路径，并且答案ans加上这条路径的最小值，并且反向建边，权值为流过的花费，至于反向建边的意义看这个图吧 EK算法：用bfs...

模版

2019-08-20

0 579

归并排序

归并排序可以理解为快排的反向，采用分治的思想，先排两边在用O(n)的时间合并在一起代码（感觉比快排实现容易些） #include<bits/stdc++.h> using namespace std; void merge(int a[],int l,int r){ ...

模版

2019-08-19

0 488

luogu SPFA P3337

题目描述：有n个点给你m条有向边和起始点s 让你输出任一点到s的最短路分析：试着用spfa写了下注意时间复杂度是O（nv）（大于等于n*n） ac代码： #include<bits/stdc++.h> using namespace std; typedef p...

模版

2019-08-18

0 510

hdu 2544 （堆优化）

题意不在重复，对比堆优化和没优化的速度碾压优化思路在叙述一遍：整体上差别还是很大的因为堆优化用了结构体存边（模拟邻接表（但性能比不过链式前向星））而一般是用邻接矩阵存图(这个也能用邻接矩阵，不过太慢了，数据大的话还是用边吧) ，然后是就是pair自定义了大小...

模版

2019-08-18

0 525

分组背包

对于分组背包问题与01背包不同的是物品被分好组了且一个组最多拿一个（也可能出现其他情况，但大致是这样的）其实也很容易想到多加个for遍历这个组拿哪个合适，这里注意多加的for放在第二个，这样保证每个最多选一个 for(int i=1;i<=n;i++){ ...

模版

2019-08-15

0 593

CF Anton and Making Potions

题目描述：你要制作n瓶药水，每瓶花费x分钟现在你有两个优化的方案（给你s个能量） 1 有m个魔法每个魔法花费b[i] 个能量使得制作时间缩短为a[i] 2 有k个魔法每个魔法花费d[i]个能量，使得c[i]个药水瞬间制作完成（d[i],c[i] 都是从小到大）这每...

二分贪心模版

2019-08-14

0 482

ac自动机入门

ac自动机应该和trie放一块好些因为ac自动机就是KMP+trie的结合版原理 trie是每个单词都会匹配吧，按照KMP的思想前面我已经匹配过了的是不是可以不用再匹配了直接跳到下一段去？答案是肯定的，并且就产生了ac自动机（此ac非彼ac，以前还以为是自动ac的咯~~~~） ...

模版

2019-08-12

0 555

字典树入门（模板）

首先说下字典树给来干嘛的；字典树建立是把单词按前缀建立的，这样遍历或者比较都可以根据前缀来判断少了不必要的操作，其实以前用set容器对单词去重的时候就考虑过这个办法，但能力有限实现不了今天才知道原来这个就叫字典树上一个模板题：http://acm.hdu.edu.cn/sh...

模版

2019-08-12

0 536

Hash入门

http://acm.hdu.edu.cn/showproblem.php?pid=1280 题目描述：给你n个数让你两两求和并且输出前m大的数 N<=3000，a[i]<=5000 分析：一开始我是把全部都存起来排个序，然后超内存了，因为空间复杂度为O（n*n），...

模版

2019-08-09

0 610

拓扑排序（bfs模板）

http://acm.hdu.edu.cn/showproblem.php?pid=1285 题目描述：给你几组关系，q,p表示q 大于p现在让你从大到小输出这些数据分析：拓扑模板用bfs跑（题目要求输出小的在前所以用优先队列），每次选入度为0的节点入队注意的一点就是会有重复...

模版

2019-08-08

0 683