讲课

清北学堂--刷题班

题目

1、特技飞行
思路：

首先每个动作制作两次，135做了和15做一样的价值
让最大放在第一个

2、矩阵分割

对于一条横的和一条竖的，切一条后另一条会切两次，先切大的；
两个同方向的则没有什么问题，排序即可。

Jan Protecting the Flower

ti*di+(ti+ti)*di+1 ti*di+1 ti/di

区间修改

m次操作，l...r 加k
s[i] = a[i]-a[i-1]
l...r +k
s[l] += k;
s[r+1] -= k;
a[i] - a[i-1]+s[i];

Meet in the middle

背包

容量为m(<=1e9),n(<=40)物品，wi体积，ci价值，体积不超过m的情况下价值总和最大

分成两半，20+20，
2^20枚举每个物品选不选，求体积，价值，排序
另一半枚举且在另一半找最优（价值）的且满足情况（体积）的，二分

k' th number
n(<=35)个数，求第k大的子集（子集的和）

二分
17+18
2^17枚举所有情况的总和，排序，
2^18对于每种情况，设价值总和w2
在前面找有多少个子集的和（设w1）满足 w1>=mid(二分)-w2
即 w1+w2>=mid,
求的数就是有多少个子集的和满足 >=mid;

结：
meet in the middle
数据范围 n<= 35/40...
分成两段，在前面预处理。

分块

区间加

把区间分成sqrt(n)
查询对于大块直接加

T2
加and查询求和
分块，在快上加，散的直接暴力
求和 块直接加，其他暴力

t3

长度：n，
操作：n，
操作：区间开方，
查询：区间求和

记录这个块是否为一，即可
并查集 找出所有不是1的数，

整体二分

把一段区间分成两段，跨过中间点
左边找后缀最小值，右边找前缀最小值
nlogn

RMQ(st表)

倍增的思想
查询O(1)，处理nlogn
f[i][j] : 以i为端点，长度为2^j，的最小值

预处理：

void RMQ_init（）{
    for (int i=0; i<n; ++i) f[i][0] = a[i];
    for (int j=1; （1<<j)-1<=n; ++j) {
        for (int i=0; i+(1<<j)-1<n; ++i) {
            f[i][j] = min(f[i][j-1],
        }
    }
}

长度为k的，起点为i的最小值