在此处输入标题

贪心
在此输入正文

贪心

比恶心的几道题：

meet it in middle

背包问题：
一个容积问 m的背包，有n个物品，第i个物品的体积为wi
价值为ci
选择物品若干，使得体积和不超过m的情况下
价值总和最大
n<=40
思路：
分为两半 前一半 后一半 然后合并
meet it in middle

K’th number

有n个数，共有2^n个子集，一个子集，的值看做其所有数的和
求2^n个子集中地K大的子集
n<=25

解法：meet it in middle 拆开枚举 17+18 1<<17枚举所有情况的和，排序 1<<18对于每种情况，设价值综合为W2
在当前找有多少子集的和（设w1）满足w1>mid（二分）-w2 即w1+w2>=mid 求的数就是有多少个子集满足 >=mid

小结：
meet it middle ：
数据范围20-40；

分块

把区间分为sqrt（n）个
例：
区间开平方：
给出一个数列，以及n个操作，操作涉及区间开方，区间求和

解法：int范围内的数字大约（最多）开五次后为1，每次查看那些数不是1，
是1的话直接跳过整个为1的快，否则暴力修改（分块：单点修改，区间求和），
那么怎样快速找出那些区间全是1，用并查集，如果自身是1的话指向自己的前一个，那么并查集的根指向不是1的位置

整体二分

分治算法 :
每次在区间（子区间）中二分
总时间复杂度nlogn

st表

求区间内的最值
倍增的思想：
二分区间
f[i][J]表示以i为端点，长度为2^j的区间内的最值