非严格二分查找： 情形一：给定序列a[1]~a[N], 每次询问给定一个数v, 一个位置pos， 从a[pos+1]~a[N]中找到第一个大于v的元素的下标 考虑建立一棵普通的位置线段树， 树上节点维护当前位置区间的最大值； 每次查找时从根递归向下查找， 对于当前区间 [ l，r ]： 0.  若当前节点为叶子结点， 若结点的值满足 > v ， 返回下标即可； 1.  若pos <= mid： 若左子树最大值大于v（约束）， 则左子树可能存在解， 递归查找左子树； 若左子树查找到解，则直接返回该解（这是一个重要剪枝，可以大幅优化时间， 显然此时即使右子树存在...

一维： 前缀和的建立： sum[i] = sum[i-1] + val[i], 前缀和求解区间和： { val[l] ~ val[r] } =  sum[r] - sum[l-1], 差分标记： [l,r]区间每个点增加v ， 则tag[l] += v，  tag[r+1] -= v,  然后每个点 val[i] 的值的变化量delta即为  tag[]的1~i的一维前缀和 二维： 前缀和的建立： sum[i][j] = val[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]...

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

输出描述: Output one line containing an integer representing the answer. 示例1 输入 1 0 3 3 0 输出 3 题意： 给定2n个人，每两个人间存在一个竞争值，题目要求将这2n个人划分为人数相同的两组(即每组n人)，记分好组的情况下所有的无序对(x,y)(x, y来自不同组) 产生的的和为F，本题即求最小的F为多少。 分析： 自然想到要枚举子集，倘若单纯地考虑每一元素 放/不放 在组1中，并在 组1/组2 放满后进行统计&更新最优值，则复杂度O(C(2N,N...