清北学堂金秋营 day7

%%%lh

题解

T1

容斥原理

T2

30：枚举每个区间排序读中位数排序
n^3log n
60：固定左端点枚举，移动右端点，插入排序
n^3
100：二分答案，中位数，大于等于它的个数等于小于等于它的个数，标记1与-1
a：1 2 3 4 5
b：-1 -1 1 1 1
求前缀和
~~~
求顺序对

T3

一个区间某数统计多少次等于小于等于它的个数

二分、贪心、分块

poj2976

有n个ai,bi，选择n-k个元素，询问sum{ai}/sum{bi}最大
二分一个k,sum{ai}/sum{bi}>=k,sum{ai}-ksum{bi}>=0

第k大区间2

给n个数，将所有区间的平均数排序求第k大。
sigma(ai)/(r-l+1)>=k
->sigma(ai)>=k(r-l+1)
->sigma(ai-k)>=0
不会

poj2728

分数规划

二分答案跑最大生成树

poj3621

分数规划
spfa负权环

第k大区间3

给n个数，将所有区间的众数排序求第k大。

二分。
倘若一个区间存在一个数次数大于t，则其众数出现次数也大于t。

枚举右端点，研究有多少个合法左端点which满足存在次数大于t的条件。如果[2,5]合法，则[1,5]合法，则[1,6]合法，

l=0表示目前没有合法的左端点。r移动，每到一个新地方，就找出前面出现的这个数，更新l

跳石头

关押罪犯

noi2015荷马史诗

阿狸和桃子的游戏

usaco2007 nov tanning

特技飞行

每个动作最多做两次
1-3-5===1-5
把越刺激的活动越放在两边

矩形分割

反正都是要切，先切最疼的

大背包

把m个物品分成两半，

meet in the middle

要是2^30不行的话
就搞成2*2^15

rmq

st表

f[i][j]记录以i为右端点长度为2^j的区间的某属性（和、最小值之类的）
（其实就是用来写倍增的数据结构）