何时秋-CSDN博客

原创 java模板系列之树状数组-poj3903

https://vjudge.net/problem/POJ-3903一道最长上升子序列的模板题，用了树状数组优化，不过因为数的范围比较小，没有做离散化，当数组中的数比较大时要离散化//// Source code recreated from a .class file by IntelliJ IDEA// (powered by FernFlower decompiler)//import java.util.*;//初始化可以选择对每个节点用add或者借助lowbit扫描它的子节点求和

2022-05-18 19:52:57 210

原创 Java模板系列之背包dp-HDU1114

https://vjudge.net/problem/HDU-1114找了个完全背包的题，用了滚动数组，空间复杂度为n（背包大小），时间复杂度为n*m(物品数量)//// Source code recreated from a .class file by IntelliJ IDEA// (powered by FernFlower decompiler)//import java.util.*;public class Main { static class item{

2022-05-15 16:50:11 132

原创 JAVA模板系列之线段树（区间修改，区间查询）- POJ3468

https://vjudge.net/problem/POJ-3468线段树一般开四倍大小的n，每次查询和修改的时间复杂度都是log//// Source code recreated from a .class file by IntelliJ IDEA// (powered by FernFlower decompiler)//import java.util.*;public class Main { static class node{ int l,r;

2022-05-14 21:32:34 211

原创 java模板系列之spfa-hdu2544

最优情况下，时间复杂度是km，k是一个很小的常数，不过现在的出题人，都喜欢随手卡spfa，时间复杂度最差会到nmhttps://vjudge.net/problem/HDU-2544//// Source code recreated from a .class file by IntelliJ IDEA// (powered by FernFlower decompiler)//import java.util.*;public class Main { static List

2022-05-12 17:13:29 191

原创 java模板系列之最小生成树（kruskal）- poj1251

时间复杂度mlogm值得注意的是，在这个板子里并查集的下标是从0开始的，要是直接用的话，记得改下init把右端点带上//// Source code recreated from a .class file by IntelliJ IDEA// (powered by FernFlower decompiler)//import java.util.*;public class Main { static int fa[]; static int n; stati

2022-05-11 21:02:52 93

原创 java模板系列之并查集-hdu1232

题目是hdu 1232https://vjudge.net/problem/HDU-1232并查集中get和merge的时间复杂度都是反阿克曼函数，可近似看作为常数（5以内），故整个并查集的时间复杂度就是get和merage的调用次数//// Source code recreated from a .class file by IntelliJ IDEA// (powered by FernFlower decompiler)//import java.util.*;public cl

2022-05-11 17:42:23 209

原创 java模板系列之dikstra-hdu2544

HDU - 2544https://vjudge.net/problem/HDU-2544没有什么太多好说的，优先队列优化的dikstra，时间复杂度可近似看为mlogn，m为边，n为点//// Source code recreated from a .class file by IntelliJ IDEA// (powered by FernFlower decompiler)//import java.util.*;public class Main { //既代表了li

2022-05-11 17:41:49 103

weixin_43822647的博客