开始复习计划~~

一些算法。

基础算法

二分

我一直写不对的算法。。。

网上讲的二分都太杂了，现在我们把二分的边界条件全设为如下模式(向FALLEN_GEMINI大佬学习)：

while(l<r)
{
    mid=·····;
    ······;
}

此时如果我们要求的是较大值，则中间内容如下：

while(l<r)
{
    mid=(l+r+1)>>1;
    if(check(mid))
        l=mid;
    else
        r=mid-1;
}

反之，较小值则如下：

while(l<r)
{
    mid=(l+r)>>1;
    if(check(mid))
        r=mid;
    else
        l=mid+1;
}

实数上的二分加个精度判断就好：

while(l+eps<r)
{
    double mid=·····;
    ······;
}

关于二分题的类型，一般有如下特征：

  1. 最大值最小或最小值最大；
  2. 含有特定的单调性；
  3. 数据范围一般较大(毕竟二分时间复杂度才 O(logN))。

关于几个二分的题：

[AtCoder abc144E] Gluttony

[HNOI2006] 鬼谷子的钱袋

[USACO08JAN] Haybale Guessing

例题：Luogu P1316 丢瓶盖

一道经典的二分答案题，我们二分最大的距离，然后判断距离超过这个距离的瓶盖到没到达 BB 个即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,m;
long long a[101010];
bool check(long long x)
{
	long long cnt=1;
	long long num=1;
	for(int i=2;i<=n;i++)
		if(a[i]-a[num]>=x)
		{
			cnt++;
			num=i;
		}
	if(cnt>=m)
		return true;
	return false;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	long long l=1,r=a[n]-a[1];
	long long mid;
	while(l<r)
	{
		mid=(l+r+1)>>1;
		if(check(mid))
			l=mid;
		else
			r=mid-1;
	}
	printf("%lld\n",l);
	return 0;
}

接着二分中有一类三分法，可以解决那种单峰或单谷问题，这个我之前写过，放几个链接在这里：

三分法

[SHOI2017] 期末考试

[SCOI2010] 传送带

[ZJOJ3203] Light Bulb

然后是关于离散化，这个我老是记不住，总之就是排序，去重，再二分：

int main()
{
    int a[],b[],q[],n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        b[i]=a[i];//复制
    }
    sort(b+1,b+n+1);
    cnt=unique(b+1,b+n+1)-b-1;//排序加去重
    for(int i=1;i<=n;i++)
        q[i]=lower_bound(b+1,b+cnt+1,a[i])-b;//二分查找下标
}

倍增

和二分一样优秀的算法，就是每次遍历的长度较上一次增加一倍，与二进制相结合可以做出很多题。

倍增最重要的是它的 ST 算法，在 RMQ 问题中能够在 O(NlogN) 的预处理后，O(1) 在线回答任何区间内的最值。

算法思想如下：

设 F[i,j]F[i,j] 代表区间 [i,i+2j−1][i,i+2^j-1] 里的最值，初始化为 F[i,0]=A[i]F[i,0]=A[i]， 即 [i,i][i,i] 里的最值为 A[i]A[i]。

然后用倍增的思想递推出 FF 数组，即：

F[i,j]=max⁡(F[i,j−1],F[i+2j−1,j−1]) F[i,j]=\max(F[i,j-1],F[i+2 ^{j-1} ,j-1])

就是把区间分成两半，取左右两半的最大值。

于是得到代码：

for(int i=1;i<=n;i++)
    f[i][0]=a[i];
for(int j=1;j<=20;j++)
    for(int i=1;i<=n-(1<<j)+1;i++)
        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);

题目：[CF1237D] Balanced Playlist

贪心

这个要重点讲讲，因为我做的题比较少。

反正就是以下几点：

  1. 选最优的；
  2. 保证整体最优由局部最优得到

有几个经典例题要看看：

选择不相交区间：给 nn 个开区间 (ai,bi)(a_i,b_i)，选择尽量多个区间让它们两两无公共点。

按照 bib_i 排序，考虑每个区间是否冲突，如果没有就选。

区间选点问题：给 nn 个闭区间 [ai,bi][a_i,b_i]，在数轴上选尽量少的点，让每个区间都至少有一个点。

按照 bib_i 排序，每次选第一个不能覆盖到的区间末尾的点。

区间覆盖问题：给 nn 个闭区间 [ai,bi][a_i,b_i]，选择尽量少的区间覆盖指定线段区间 [s,t][s,t]。

按照 aia_i 排序，每次找覆盖点 ss 的区间中，bib_i 最大的那个，然后更新 s=bis=b_i，直到包含 tt。

流水作业调度问题：有 nn 个作业要在两台机器 aa 和 bb 的流水线上加工，每个作业必须先花 xix_i 在 aa 上加工，再花 yiy_i 在 bb 上加工，确定 nn 个作业的加工顺序，让所有作业的加工总时间最短(即作业 11 在 aa 上加工开始至作业 nn 在 bb 上加工结束)。

对于 xi<yix_i<y_i 的作业集合，按照 xix_i 从小到大排序；

对于 xi≥yix_i\geq y_i 的作业集合，按照 yiy_i 从大到小排序；

然后第一个作业集合接上第二个作业集合就是最优顺序。

带限期和罚款的单位时间任务调度问题：nn 个任务，每个任务需要花 11 单位时间完成，任务 ii 的截止时间为 did_i，误时惩罚为 wiw_i，请确定所有任务的执行顺序，使得惩罚最少。

将 wiw_i 从大到小排序，依次处理，使处理任务 ii 的时间在 did_i 之内且尽量靠后，如果 did_i 内时间已排满，放弃该任务。

前缀和与差分

这个不用多讲吧。。。主要就是在于优化和数据结构的搭配。

跳过

图论

最短路

Floyd

简单的 Floyd，三层循环即可：

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(dis[i][j]>dis[i][k]+dis[k][j])
                dis[i][j]=dis[i][k]+dis[k][j];

例题：[POJ3613] Cow Relays

Floyd 还能用来传递闭包，用来传递一些信息：

dis[x][y]=dis[y][x]=1;//初始化
for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]|=dis[i][k]&dis[k][j];

例题：[POJ1094] Sorting It All Out