二分

二分查找

二分查找必须在有序(单调)的序列中进行。

每次折半搜索,复杂度为O(\log n),可以在有序的序列中快速找到需要查找的值(的位置)。

二分答案

假设有函数f(x)表示某个受x影响的状态是否能实现,那么如果x越大或越小时,越难满足条件,则其满足单调性,可以使用二分答案求解

假设此满足单调性的f(x)的函数图像为1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0(1代表能实现,0代表不能实现),那么我们的任务就是找到0前面的那个1(不是在开车),使用二分可以在\log n的时间内实现快速求解。

怎么二分:我们要枚举的就是答案,即题目需要求出的值,然后依据题干定出上下界,然后在这一范围内实现二分,再通过这个答案是否能满足题意来重新划分上下界,然后一步步缩小范围,最后求出答案。

例题:P2678 跳石头

跳石头这道题显然满足单调性和有界性,可以用二分答案求解

枚举题目要求的最短跳跃距离,思考:最短跳跃距离越大,需要挪走的石头越多,这显然满足单调性,又由于能挪走的石头有一个上限M,因此可以使用二分答案进行求解。

求解时从区间[1,L]开始二分,取中点mid,然后开始模拟跳石头,如果下一个石头离上一个石头的距离小于了取的mid,则说明这块石头应该被挪走,计数器cnt加一

如果中途时cnt大于了M,说明需要挪走的石头数量超过了上限,即mid取的过大,方案不可行,接下来就继续二分[1,mid-1],一步步缩小二分的范围。

同理,如果结束时cnt\leq M,说明该方案可行,但是可能不是最优解,mid还可以取更大,因此继续二分[mid,L],依次求解。

到最后如果到了区间[l,r]l=r,说明已经找到了最优解,输出即可。

#include <cstdio>

int L,n,m,d[50005];//见题意

bool judge(int x)
{
    int cnt=0;//表示需要挪多少块石头
    int now=0,i=0;//now表示当前人在的石头标号,i表示当前处理的石头标号
    while(i<n+1)//注意是n+1
    {
        ++i;
        if(d[i]-d[now]<x)//如果两块石头中间的距离小于需要查找的mid值
            cnt++;
        else
            now=i;
    }
    return cnt<=m;//返回判断结果
}

int binary()//二分答案
{
    int l=1,r=L;//表示二分边界
    int ans;//当前答案
    while(l<=r)//当l<=r的时候
    {
        int mid=l+r>>1;//用位运算更快???
        if(judge(mid))//如果这个满足条件
            ans=mid,l=mid+1;//那么把它存下来,更新二分边界
        else//如果不满足条件的话
            r=mid-1;//mid取太大了,更新二分边界
    }
    return ans;//返回答案
}

int main()
{
    scanf("%d %d %d",&L,&n,&m);
    d[0]=0;
    for(int i=1;i<=n;i++) scanf("%d",d+i);
    d[n+1]=L;
    printf("%d\n",binary());
    return 0;
}

实数二分

一般问题:已知函数单调上升,求函数零点。

进行实数二分时记得定义eps(是一个很小的double数)由于浮点误差,使用eps可以避免判断相等时一直等不了的尴尬

例题:P1024

#include <cstdio>
#define EPS 0.001
using namespace std;

double a,b,c,d;

double f(double x)
{
    double ans=a*x*x*x+b*x*x+c*x+d;
    return ans;
}

void binary(double l,double r)
{
    while(r-l>EPS)
    {
        double mid=(r+l)/2;
        if(f(mid)==0)
        {
            printf("%.2lf ",mid);
            return;
        }
        if(f(r)==0)
        {
            printf("%.2lf ",r);
            return;
        }
        double ansl=f(l)*f(mid),ansr=f(mid)*f(r);
        if(ansl<0)
        {
            r=mid;
            continue;
        }
        else if(ansr<0)
        {
            l=mid;
            continue;
        }
    }
    printf("%.2lf ",l);
}

int main()
{
    scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
    for(int i=-100;i<=99;i++)//先在[-100,100]中逐个枚举
    {
        if(f(i+1)==0){printf("%.2lf ",i+1.0);continue;}//如果直接满足岂不美哉
        else if(f(i)*f(i+1)<0)//如果f(x1)<f(x2),且f(x1)*f(x2)<0,则零点必然在(x1,x2)中间
            binary(i,i+1.0);//开始二分
    }
    return 0;
}

三分

三分法可以用来求单峰函数的峰值。

具体做法:先在整个区间中将区间划为三份,就会存在两个划分点a,b,假设待划分的区间为[l,r],如果a>b,则函数的峰值一定在[l,b]中,继续三分;

反之如果 a ,则函数的峰值一定在[a,r]中,再次三分。

额当a=b的话怎么办呢,说明峰值一定是在[a,b]中。

当然这题也可以求导找导函数的零点然后他就变成二分了

#include <cstdio>
#include <iostream>
#define eps 1e-6//做浮点数的题的时候记得定义eps防止浮点误差
using namespace std;

int n;
double k[15];
double l, r;

double ksm(double base, int p)//快速幂
{
    double ans = 1;
    for (; p; p >>= 1)
    {
        if (p & 1)
            ans *= base;
        base *= base;
    }
    return ans;
}

double f(double x)//求函数值用的
{
    double ans = 0;
    for (int i = 0; i <= n; i++)
    {
        double tmp = k[i] * ksm(x, i);
        ans += tmp;
    }
    return ans;
}

void search()//三分函数
{
    while (r - l > eps)//当左右端点不重合时
    {
        double a, b;
        double t = (r - l) / 3;
        a = l + t;//构造a和b
        b = r - t;
        if (f(a) >= f(b))//如果f(a)>f(b),则峰值一定在[l,b]
        {
            r = b;
            continue;
        }
        else if (f(a) < f(b))//峰值一定在[a,r]
        {
            l = a;
            continue;
        }
    }
    printf("%.5lf", l);//输出答案
}

int main()
{
    cin >> n >> l >> r;
    for (int i = n; i >= 0; i--)
        cin >> k[i];
    search();
    return 0;
}

STL

提供upper_bound()lower_bound()函数

贪心

贪心,就是只从局部考虑,局部优则采用该策略,不考虑总体情况。

贪心不一定能得到最优解,贪心的正确性需要证明虽然窝不会证,考试的时候也不是很必要证

例题:P1090

这个贪心很好想,只需要每次都将最小的两堆合并即可。类似的问题还有饮水机接水等等

一道例题:给定n,让你钦定一个参数T,有两种操作A:TB:\displaystyle\frac{n}{T},使得操作的时间最短。

答案:当T=\sqrt{n}的时候最短,为什么

均值不等式

a^2+b^2\geq2ab\
a+b\geq2\sqrt{ab}\quad(a,b>0)

并且仅当a=b时取得最小值

证明:

\begin{aligned}
(a-b)^2&\geq0\
a^2+b^2-2ab&\geq0\
\therefore a^2+b^2&\geq2ab\
\end{aligned}

a_1=\sqrt{a},b_1=\sqrt{b}

\begin{aligned}
\because a_1^2+b_1^2&\geq 2a_1b_1\
\therefore a+b&\geq 2\sqrt{ab}
\end{aligned}

我们需要T+\displaystyle\frac{n}{T}最小,就使T=\sqrt{n}即可。

排序不等式

又一道例题:钦定一个长度为n的排列a,使得

1\cdot a_1+2\cdot a_2+3\cdot a_3+\cdots+n\cdot a_n

最小/最大

答案:当a=1,2,3….时最大,当a=n,n-1…时最小

排序不等式:顺序和\geq乱序和\geq逆序和

求证:a^3+b^3+c^3\geq a^2b+b^2c+c^2a

证明:记序列{x}=a,b,c{y}=a^2,b^2,c^2,由排序不等式得正序和大于乱序和,证毕。

数据结构2

堆是一棵完全二叉树,每个节点拥有一个key,父亲节点的key一定大于两个儿子节点

堆的查询:堆只能查询堆顶,返回其key即可

堆的插入

核心思想:修复,直接将需要插入的元素摆在堆尾,然后修复堆

如何修复:如果它的key值大于父亲节点的,交换之,递归执行知道它的key值小于父亲节点为止

堆的删除

核心思想:修复,只能删除顶节点

直接将其与末尾节点交换,然后修复之。

如何修复:交换后找一个最大的儿子节点,交换之,递归执行直到修复完毕为止。

细节

堆式存储:直接利用数组来存

根据完全二叉树的性质,一个节点的左儿子的编号是该节点的编号乘2(使用<<1加快运算),右儿子的编号是左儿子的编号+1(使用|1加快速度),父节点的编号就是除以二向下取整(使用>>1加快速度)

#define LE(x) ((x)<<1)
#define RT(x) (((x)<<1)|1)
#define DAD(x) ((x)>>1)

struct heap{
    int w[100005];
    int tot;

    heap()
    {
        memset(w,0,sizeof(w));
        tot=0;
    }
    int top()
    {
        return w[1];
    }
    void modify(int x)
    {
        if(x==1) return;
        if(w[x]>w[DAD(x)])
            swap(w[x],w[DAD(x)]),modify(DAD(x));
    }
    void push(int key)
    {
        w[++tot]=key;
        modify(tot);
    }
    void repair(int x)
    {
        int tar=w[LE(x)]>w[RT(x)]?LE(x):RT(x);
        if(w[x]<w[tar])
        {
            swap(w[x],w[tar]);
            repair(tar);
        }
    }
    void pop()
    {
        swap(w[1],w[tot]);
        w[tot--]=0;
        repair(1);
    }
}h;

堆排序

利用堆满足堆顶最大/小的性质,可以利用堆进行排序,由于堆是一棵完全二叉树,每次修改的复杂度为O(\log n),因此排序的总复杂度为O(n\log n)

将所有元素压入堆顶,然后依次弹出,弹出的就一定会有序(有些时候这个东西会比快速排序快)

int a[100005];

int main()
{
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        h.push(x);
    }
    for(int i=n;i>=1;i--)
    {
        a[i]=h.top();
        h.pop();
    }
    for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
    return 0;
}

STL的优先队列

嗯,我们一般都不手写堆的

优先队列,priority_queue定义在<queue>中,默认是大根堆,可以改成小根堆。

priority_queue<int> q1;//大根堆
priority_queue<int, vector<int>, greater<int> > q2;//小根堆

支持结构体,需要重载结构体的小于号。

支持的常用操作:

q.push(x);//插入x
q.pop();//删除堆顶
q.top();//返回堆顶元素的值
最后修改日期:2020年2月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。