基础算法

二分 贪心

二分

POJ2976

给出n个物品，每个物品有两个属性a和b，选择n-k个元素，询问sum{ai}/sum{bi}的最大值。

分数规划
等价于$\sum (a_i-kb_i)>0$
令$c_i=a_i-kb_i$，可以通过这个二分答案

第k大区间2

定义一个区间的值为其中所有数的平均数。
现给出n个数，求将所有区间的值排序后，第K大的值为多少。

求第k大一般二分。
分数规划
二分答案，等价于找多少区间>=k
[L,R]>=k等价于$\dfrac{\sum^R_{i=l}}{r-L+1}>=k$
等价于$\sum^R_{i=L}(a_i-k)>=0$
如果存在这样的区间，那么就是所求。
求一遍$a_i-k$的前缀和，相当于求顺序对的个数
$O(nlogn)$

POJ2728

给定一张图，每条边有一个收益值和一个花费值，求一个生成树，要求花费/收益最小，输出这个值

分数规划
$\dfrac{\sum花费}{\sum收益}>=k$
即$\sum花费>=k\sum收益$
即$\sum(花费-k·收益)>=0$
跑一遍最大生成树，即从大到小Kruskal即可

POJ3621

给定一张图，边上有花费，点上有收益，点可以多次经过，但是收益不叠加，边也可以多次经过，但是费用叠加。求一个环使得收益和/花费和最大，输出这个比值。

分数规划
$\dfrac{\sum花费}{\sum收益}>=k$
$\sum(花费-k·收益)>=0$
将环边权取负，等价于求负权圈
所有点入队列，跑SPFA，如果进入m次就有负权圈。

第k大区间3

定义一个区间的值为其众数出现的次数。
现给出n个数，求将所有区间的值排序后，第K大的值为多少。

终于tm的不是分数规划
$O(n^3log \ n)$
枚举左右边界，然后暴力的统计一下
建桶，维护一个max，就可以求出众数的出现次数。
$O(n^2log \ n)$
首先确定左端点，右端点每次加1
由[L,R]转化为[L,R+1]是O(1)的，因为可以直接将下一个数扔到桶里。这样就是$O(n^2)$
$O(nlog\ n)$
枚举右端点，数多少左端点满足条件
如果[L,R]合法，那么[L-k,R]与[L,R+t]均是合法的
可以记录一下i上一次出现的位置，如果该位置合法，那么[i-k,R]就是合法的。
当检验t时令L=0，当R扫到一个数，找出这个数t次前出现的位置，
用这个数字更新L,那么这个区间就是合法的。
可以以权值为第一关键字、位置为第二关键字进行排序，就可以O(1)找出t次前出现的位置查询。

NOIP2015 跳石头(Luogu P2678)

一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M块岩石（不能移走起点和终点的岩石）。

二分最短距离
把离岸边$<t$的扔掉，再去找下一个，那么对于下一块，优先选择下一块扔(我真的说不清..)，所以这么贪一下就行，可以得到最小的需要去除的数量。
由此可以写出check()函数。

NOIP2010 关押罪犯

有两个监狱，N个犯人，M对关系，每对关系描述一对犯人如果在一个监狱将会产生一个冲突值。任意安排犯人的分配，使得产生的最大冲突值最小

二分k，判断冲突关系前k大的矛盾能不能解决。
判断矛盾可以染色，a编1，矛盾编0，矛盾的矛盾编0...BFS一下判断矛盾

贪心

哈夫曼树

总之先贴一下
http://blog.csdn.net/shuangde800/article/details/7341289

NOI2015 荷马史诗

相当于每次能合并k堆果子
不求立刻理解..那您列出来干什么啊orzzzzz

阿狸和桃子的游戏

有一个有点权有边权的图，然后两个人分别给每个点染色。对于一个点的点权将会赐予染了这个点的人。对于一条边的边权，若它连接的两个点被同一个人染了，那么边权会赐予这个人。它们两个人都想让自己的分数减去对方的分数尽可能多。输出最终双方的分数差。

将边权剖开加诸两端，不会影响结果。
一个人选最大，一个人选比较小的
读入时处理一下排个序就好了。

Usaco2007 Novtanning

奶牛们计划着去海滩上享受日光浴。为了避免皮肤被阳光灼伤，所有C(1 <= C <= 2500)头奶牛必须在出门之前在身上抹防晒霜。第i头奶牛适合的最小和最 大的SPF值分别为min$SPF_i$和max$SPF_i$($1 <= minSPF_i <= 1,000; minSPF_i <= maxSPF_i <= 1,000$)。如果某头奶牛涂的防晒霜的SPF值过小，那么阳光仍然能 把她的皮肤灼伤；如果防晒霜的SPF值过大，则会使日光浴与躺在屋里睡觉变得 几乎没有差别。为此，奶牛们准备了一大篮子防晒霜，一共L(1 <= L <= 2500)瓶。第i瓶 防晒霜的SPF值为$SPF_i(1 <= SPF_i <= 1,000)$。瓶子的大小也不一定相同，第i瓶防晒霜可供$cover_i$头奶牛使用。当然，每头奶牛只能涂某一个瓶子里的防晒霜 ，而不能把若干个瓶里的混合着用。 请你计算一下，如果使用奶牛们准备的防晒霜，最多有多少奶牛能在不被灼 伤的前提下，享受到日光浴的效果？

只有上限，将最弱的给上限最小的，也就是限制比较强的。
现在我们有了下限之后，对于某一瓶，可以先找出满足限制的所有奶牛，那么下限就已经无效了。此时再考虑这个最优策略即可。

某年国家集训队互测 特技飞行

神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间，每个单位时间可以进行一项特技动作，可选的动作有K种，每种动作有一个刺激程度Ci。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间)*Ci，若为第一次进行该动作，价值为0。安排一种方案，使得总价值最大。

每个动作最多有两次，例如，1时刻、5时刻等价于1 3 5时刻，刺激不会变多
分配间隔时间时，给C_i大的分配时间多，所以排个序，大的尽量扔两边，贪就好了。

矩形切割

出于某些方面的需求，我们要把一块N×M的木板切成一个个1×1的小方块。 对于一块木板，我们只能从某条横线或者某条竖线（要在方格线上），而且这木板是不均匀的，从不同的线切割下去要花不同的代价。而且，对于一块木板，切割一次以后就被分割成两块，而且不能把这两块木板拼在一起然后一刀切成四块，只能两块分别再进行一次切割。现在，给出从不同的线切割所要花的代价，求把整块木板分割成1×1块小方块所需要耗费的最小代价。

对某一组横切和纵切，优先切代价大的那条，让代价小的切两遍
然后按权值从大到小排个序，按这个切就好。

Usaco2007 Jan Protecting the Flowers

约翰留下他的N(<=100000)只奶牛上山采木．他离开的时候，她们像往常一样悠闲地在草场里吃草．可是，当他回来的时候，他看到了一幕惨剧：牛们正躲在他的花园里，啃食着他心爱的美丽花朵！为了使接下来花朵的损失最小，约翰赶紧采取行动，把牛们送回牛棚．牛们从1到N编号．第i只牛所在的位置距离牛棚Ti(1≤Ti<2000000)分钟的路程，而在约翰开始送她回牛棚之前，她每分钟会啃食Di(1≤Di≤100)朵鲜花．无论多么努力，约翰一次只能送一只牛回棚．而运送第第i只牛事实上需要2Ti分钟，因为来回都需要时间．写一个程序来决定约翰运送奶牛的顺序，使最终被吞食的花朵数量最小．

除法为最优策略。
yy一下就出来了。
当然也可以严格的算：
判断需要交换与不需要交换
如果不交换，那么
$t_id_i+t_{i+1}d_{i+1}<t_id_{i+1}+t_{i+1}d_i$
整理得 $\dfrac{t_i}{d_i}<\dfrac{t_{i+1}}{d_{i+1}}$

NOIP2012 国王游戏

同上

前缀和

区间修改

给定n个数ai，有m次操作，每个操作是给al~ar增加一个数k。
最终输出操作完后的这n个数的值。
要求一个O(n+m)的做法。

s[l]+=k, s[r+1]-=k
还原时首先q[i]=q[i-1]+s[i]来维护前缀和数组q
然后a[i]+=q[i]即可

Meet int the middle

见《搜索的奇技淫巧》

背包

一个容量为m的背包，有n个物品，第i个物品的体积为wi，价值为ci。
选择若干物品，使得体积总和不超过m的情况下价值总和最大。
n<=40。

分成两半，然后拼起来
第一部分枚举出来$2^{20}$种情况，按体积排序。
对每一个w，二分查找找出前一半体积总和<=m-w价值最大的情况。
用前缀和维护即可。
类似于前天的T3

K-thNumber

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

第k大->二分
分成两半，对第一半枚举所有的总和，并且排序。
后一半，取答案是w，然后用二分答案t，使得拼起来的子集是前面和后面的拼接。然后在第一表中看有多少是t-w的，和t比较。

分块

RMQ分块解法

预处理$\sqrt n$块
询问段区间最小值就是包含段的最小值与单另部分最小值。
复杂度$O(\sqrt n)$

分块维护区间加

类似线段树的lazytag

分块维护区间开平方、区间和

每个数字最多只能被开5次，会变成1.
对所有不是1的暴力开，否则不管。
由于最多有5次，相当于单点修改区间求和。
分块维护即可。
想要找见[L,R]中有多少1，可以用并查集维护。
并查集fa为左边第一个不是1的位置，如果变成1就连向左边的位置。
如果R的根节点比L大，那么这一区间就是1.（没怎么听懂）

整体二分

RMQ

给定n个数，有Q次询问，每次询问一段区间的最小值。

对于跨mid的询问，可以求出[L,mid][mid,R]的最小值
否则可以递归的找前缀最小值，复杂度O(logn)

倍增

RMQ

a[i][j]=max(a[i][j-1],a[i+1<<(j-1)+1][j])
查询是O(1)的，跨区间可以直接搞