无名行者zzz

分类

知识总结(3) 题解(2)

/ 注册

全部文章（共5篇）

9.9训练小结

题意：给定一个序列(长度<=1e5), 要求从其中任选一段长度为L的子段并删除，最后问你剩余序列的LIS(严格递增)为多少？总结：想到了枚举切割子段的起始点，进而也想到了预处理出以每一个元素为终点的LIS长度(前缀预处理)和以每一个元素为起点的LIS的长度(后缀预处理)，进而也想到了从...

2019-09-10

0 677

线段树上的类二分查找总结

非严格二分查找：情形一：给定序列a[1]~a[N], 每次询问给定一个数v, 一个位置pos，从a[pos+1]~a[N]中找到第一个大于v的元素的下标考虑建立一棵普通的位置线段树，树上节点维护当前位置区间的最大值；每次查找时从根递归向下查找，对于当前区间 [ l，r ]： ...

2019-08-30

3 2211

前缀和与差分总结

一维：前缀和的建立： sum[i] = sum[i-1] + val[i], 前缀和求解区间和： { val[l] ~ val[r] } = sum[r] - sum[l-1], 差分标记： [l,r]区间每个点增加v ，则tag[l] += v， tag[r...

2019-08-28

0 881

判断某边是否在图中给定两点间的最短路径上(结论)

由于图中给定两点(假设为No.1 & No.n)间的最短路径不止一条，但可以确定一定是简单通路，因此存在一个较为标准的方法找出在1->n的最短路径的所有边：通过对原图跑Dijkstra求出原点到其他所有点的最短距离dis(1,i) (i : 1~n)，通过对原图的...

2019-07-22

0 625

19牛客多校2-F(DFS,权值计算散步于过程中以优化时间)

输出描述: Output one line containing an integer representing the answer. 示例1 输入 1 0 3 3 0 输出 3 题意：给定2n个人，每两个人间存在一个竞争值，题目要求将这2n个人划分为人...

2019-07-20

0 935