【算法笔记】高精度

什么是高精度

嗯,高精度就是精度很高(滚粗)

好切入正题,高精度就是因为C艹的自带整数类型最大只有64位的long long,无法应对某些无聊出题人出的超大数据。而double的有效数字位数太低,无法精确运算,因此只能使用高精度。

高精度的原理就是使用数组来模拟每一位上的数字。至于数组的选择,可以使用char数组,也可以使用stringvector,看个人喜好。一般来说,char跑的是最快的。

当然也可以将高精整数封装成一个类,再加上重载运算符等高端操作来增强代码的可(复)读(杂)性,并且方便copy模板

什么时候用高精

嗯,当遇到计算阶乘,斐波那契等飞速增长的东西的时候如果unsigned long long还是不能解决问题的话,就上高精。还有当数据非常大的时候也考虑使用高精。

遇到诸如a_i\leq 10^{10000}这种数据范围,就肯定不用说了。。。。。。

高精的实现

大体思路

大体的思路还是使用字符数组或者vector来存储。然后进行计算时就参照竖式计算来算即可。

存储的时候下标0处存储个位,下标1存储十位,依次从低位向高位存储,方便竖式的计算。

当然还有很多神奇的方法能加速乘除法的运算,比如FFT可以加速高精乘法。但由于我不会所以这里就不讲了,

加法

加法的实现很简单,只需要模仿竖式计算一样进位就可以了。下面来模拟一下12345+678的过程来弄懂代码的思路

 12345
+  678

首先从最右边开始,进行相加,5+8=13,填上3并向上一位进1

 12345
+  678
------
     3           进1

然后到十位,4+7=11,再加上前面进的1等于12,填上2并进一

 12345
+  678
------
    23           进1

然后到百位,3+6+1=10,填上0,进1

 12345
+  678
------
   023           进1

接下来到了千位。发现下面的数字并没有千位,怎么办呢,这就需要在一开始的时候补0以避免一些玄学的错误(如果你使用STL容器的话)2+0+1=3,填上3,进0

 12345
+  678
------
  3023           进0

最后同理,加完就好了,最终答案是13023。完结撒花。高精加法的原理大概就是这样的,复杂度为O(n)

如果使用字符数组来存储的话,画风大概是这样的,写的时候一定记得-'0'

#include <cstring>
#include <cstdio>
#define max(a,b) (a>b?a:b)

const int maxn=505;
char a[maxn],b[maxn],aa[maxn],bb[maxn];
int ans[maxn];

int main()
{
    memset(a,'0',sizeof(a));
    memset(b,'0',sizeof(b));
    scanf("%s %s",aa,bb);
    for(int i=0;i<strlen(aa);i++)
        a[strlen(aa)-1-i]=aa[i];
    for(int i=0;i<strlen(bb);i++)
        b[strlen(bb)-1-i]=bb[i];
    int tmp=0;//存储进的位
    int l=max(strlen(aa),strlen(bb));
    for(int i=0;i<l;i++)
    {
        ans[i]=(a[i]-'0'+b[i]-'0'+tmp)%10;
        tmp=(a[i]-'0'+b[i]-'0'+tmp)/10;
    }
    if(tmp)//如果最后还进有一位
        printf("%d",tmp);//直接输出他
    for(int i=l-1;i>=0;i--)
        printf("%d",ans[i]);//逆序输出
    return 0;
}

嗯,真香,又短又跑得快。

当然这只是最简单的情况,不用考虑负数等等乱七八糟的东西,也不用进行什么复杂的操作,但如果操作变得复杂,就有必要将其封装成一个结构体或者类并重载运算符以减少出错的概率。

减法

减法的实现也很简单,跟加法没什么本质的区别,只不过进位变成了退位。退的时候只需要在前面一位减去1就可以了,然后将减出来的负值加上10。

但是细节还是有的,比如你可能需要判断两数的大小并加上负数。而且输出的时候要去掉前导零,例如10000-9999,不正确的方法会输出00001,然后就会被判错。所以高精实现的麻烦之处就在于细节。

#include <iostream>
#include <string>
#include <algorithm>
#define mian main
#define MAXN 10500
using namespace std;

bool cmp_minus(string a, string b)
{
    if (a.length() != b.length())
        return a.length() > b.length();
    for (int i = 0; i < a.length(); i++)
    {
        if (a[i] != b[i])
            return a[i] > b[i];
    }
}

string _minus(string a, string b)
{
    if(a==b) return "0";
    bool flag = cmp_minus(a, b);
    if (!flag)
        swap(a, b);
    short an[MAXN] = {0}, bn[MAXN] = {0};
    short len1 = a.length(), len2 = b.length();
    short maxl = max(len1, len2);
    for (int i = 0; i < len1; i++)
        an[i] = a[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        bn[i] = b[len2 - i - 1] - '0';
    string ans1;
    int tmp = 0;
    for (int i = 0; i < maxl; i++)
    {
        tmp = an[i] - bn[i];
        if (tmp < 0)
        {
            tmp += 10;
            an[i + 1]--;
        }
        ans1=char(tmp+'0')+ans1;
    }
    short head=0;
    while(ans1[head]=='0') head++;
    string ans(ans1,head);
    if(!flag) ans="-"+ans;
    return ans;
}

int mian()
{
    string a, b;
    cin >> a >> b;
    cout << _minus(a, b);
    return 0;
}

由于用char数组太麻烦了所以这里用了string

乘法

乘法也是像竖式一样乘,先乘后加,由于对于每一位都要进行乘法,所以复杂度为O(n^2)。当然FFT可以优化到log级别但我不会。所以这里用朴素的高精乘法。

想打出乘法,首先要学会加法,因为最后需要加起来。

接下来模拟12345*678的过程以加强理解

 12345
*  678

首先要将12345*8,过程与加法的类似,都要记录进的位。

 12345
*  678
------
 98760

然后将12345*7,注意如果最高位还有进位的话要处理干净,然后注意提前补0方便最后相加。

 12345
*  678
------
 98760
864150//补0

最后

  12345
 *  678
-------
  98760
 864150
7407000//补0

再最后按照高精加法的方式加起来,当然这个过程可以每乘一位进行一次

  12345
 *  678
-------
  98760
 864150
7407000//补0
-------
8369910

其实,乘法处理的方式与加法的很像,但是同样要注意最后去掉前导0,还有如果其中一个数是0,那就直接输出0就可以了。

下面的类是重载了乘号运算符的:

struct bigint
{
    vector<int> v;
}

bigint operator*(const bigint &a,const bigint &b)//重载运算符
{
    if((a.v.size()==1&&a.v[0]==0)||(b.v.size()==1&&b.v[0]==0))//如果其中一个是0
        return bigint(vector<int>(1),0);//直接返回
    vector<int> aa=a.v,bb=b.v;
    if(a<b)
        swap(aa,bb);//看似可以减小乘的次数
    bigint ans;
    for(int j=0;j<bb.size();j++)//模拟
    {
        int tmp=0;
        bigint ans1;
        for(int i=0;i<j;i++)//提前补0
            ans1.v.push_back(0);
        for(int i=0;i<aa.size();i++)//然后模拟乘法
        {
            ans1.v.push_back((aa[i]*bb[j]+tmp)%10);
            tmp=(aa[i]*bb[j]+tmp)/10;
        }
        if(tmp)//如果还有剩下的进位
            ans1.v.push_back(tmp);//补进去
        ans=ans+ans1;//更新答案
    }
    return ans;
}

除法

除法是一个很玄学的东西,因为这玩意真的不好模拟竖式的计算。

一个不错的方法是累着相减,减到0为止,然后输出答案即可。

但是这种复杂度完全就是玄学,因为最后花的时间完全取决于商的大小,如果商很大,就意味着要除很多次,这样的话消耗非常大。

这里已经重载了-=运算符和>运算符

bigint operator/(const bigint &a, const bigint &b)
{
    bool flag=0;
    if(a.symbol!=b.symbol)
        flag=1;
    bigint aa=bigint(a,0),bb=bigint(b,0);
    if(aa<bb)
        return bigint(vector<int>(1),flag);
    bigint zero=bigint(vector<int>(1),0);
    bigint ans;
    while(aa>zero)
    {
        aa-=bb;
        if(!(aa>zero))
            break;
        ans++;
    }
    return bigint(ans,flag);
}

自用板子

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>
#include <iostream>
#define R register
using namespace std;

struct bigint
{
    vector<int> v;
    bool symbol;
    int size()
    {
        return v.size();
    }
    bigint(vector<int> vv)
    {
        this->v=vv;
    }
    bigint(vector<int> vv,bool symbol)
    { 
        this->v=vv;
        this->symbol=symbol;
    }
    bigint(bigint a,bool symbol)
    {
        this->v=a.v;
        this->symbol=symbol;
    }
    bigint()
    {
        symbol=0;
    }
    void operator=(const bigint &a)
    { 
        this->v=a.v;
        this->symbol=a.symbol;
    }
    friend bool operator<(const bigint&,const bigint&);
    friend bool operator>(const bigint&,const bigint&);
    friend bool operator==(const bigint&,const bigint&);
    friend bool operator!=(const bigint&,const bigint&);
    friend bigint operator+(const bigint&,const bigint&);
    friend bigint operator-(const bigint&,const bigint&);
    friend bigint operator*(const bigint&,const bigint&);
    friend bigint operator/(const bigint&,const bigint&);
    friend ostream& operator<<(ostream&,const bigint&);
    bigint operator-=(const bigint &a)
    {
        *this=*this-a;
        return *this;
    }
    bigint operator+=(const bigint &a)
    {
        *this=*this+a;
        return *this;
    }
    bigint operator*=(const bigint &a)
    {
        *this=(*this)*a;
        return *this;
    }
    bigint operator/=(const bigint &a)
    {
        *this=(*this)/a;
        return *this;
    }
    bigint operator++(int)
    {
        vector<int> one={1};
        bigint a=*this;
        *this+=bigint(one,0);
        return a;
    }
    bigint operator++()
    {
        vector<int> one={1};
        *this+=bigint(one,0);
        return *this;
    }
    bigint operator--(int)
    {
        vector<int> one={1};
        bigint a=*this;
        *this-=bigint(one,0);
        return a;
    }
    bigint operator--()
    {
        vector<int> one={1};
        *this-=bigint(one,0);
        return *this;
    }
};

bigint conv(int a)
{
    bool flag=a<0;
    a=a>=0?a:-a;
    vector<int> v;
    while(a)
    {
        v.push_back(a%10);
        a/=10;
    }
    return bigint(v,flag);
}

bool operator<(const bigint &a, const bigint &b)
{
    if(a.symbol^b.symbol)
        return a.symbol;
    if(a.v.size()!=b.v.size())
        return a.symbol?a.v.size()>b.v.size():a.v.size()<b.v.size();
    for(R int i=a.v.size()-1;i>=0;i--)
        if(a.v[i]!=b.v[i])
            return a.symbol?a.v[i]>b.v[i]:a.v[i]<b.v[i];
    return false;
}

bool operator==(const bigint &a,const bigint &b)
{
    if(a.symbol!=b.symbol || a.v.size()!=b.v.size())
        return false;
    for(R int i=0;i<a.v.size();i++)
        if(a.v[i]!=b.v[i])
            return false;
    return true;
}

bool operator!=(const bigint &a, const bigint &b)
{
    if(a.symbol!=b.symbol || a.v.size()!=b.v.size())
        return true;
    for(R int i=0;i<a.v.size();i++)
        if(a.v[i]!=b.v[i])
            return true;
    return false;
}

bool operator>(const bigint &a, const bigint &b)
{
    return a!=b&&b<a;
}

bool operator<=(const bigint &a, const bigint &b)
{
    return (a<b)||(a==b);
}

bool operator>=(const bigint &a,const bigint &b)
{
    return (a==b)||(b<a);
}

bigint operator+(const bigint &a,const bigint &b)
{
    bool flag;
    if(a.symbol&&(!b.symbol))
        return b-bigint(a,0);
    if(b.symbol&&(!a.symbol))
        return a-bigint(b,0);
    if(a.symbol==b.symbol)
        flag=a.symbol;
    vector<int> aa=a.v, bb=b.v;
    vector<int> ans;
    if(aa.size()>bb.size())
        swap(aa,bb);
    while(aa.size()<=bb.size())
        aa.push_back(0);
    int tmp=0;
    for(R int i=0;i<bb.size();i++)
    {
        ans.push_back((aa[i]+bb[i]+tmp)%10);
        tmp=(aa[i]+bb[i]+tmp)/10;
    }
    if(tmp)
        ans.push_back(tmp);
    return bigint(ans,flag);
}

bigint operator-(const bigint &a,const bigint &b)
{
    bool flag=0;
    if(a.symbol&&(!b.symbol))
        return a+bigint(b,1);
    if(b.symbol&&(!a.symbol))
        return bigint(b,0)+a;
    if(a.symbol==b.symbol)
        flag=a.symbol;
    vector<int> aa=a.v, bb=b.v;
    vector<int> ans;
    if(a<b)
        swap(aa,bb),flag=!flag;
    while(aa.size()>=bb.size())
        bb.push_back(0);
    for(R int i=0;i<aa.size();i++)
    {
        int tmp1=aa[i]-bb[i];
        if(tmp1<0)
        {
            aa[i+1]--;
            tmp1+=10;
        }
        ans.push_back(tmp1);
    }
    while(ans.size()>1&&ans[ans.size()-1]==0)
        ans.pop_back();
    return bigint(ans,flag);
}

bigint operator*(const bigint &a,const bigint &b)
{
    if((a.v.size()==1&&a.v[0]==0)||(b.v.size()==1&&b.v[0]==0))
        return bigint(vector<int>(1),0);
    bool flag=0;
    if(a.symbol!=b.symbol)
        flag=1;
    vector<int> aa=a.v,bb=b.v;
    if(a<b)
        swap(aa,bb);
    bigint ans;
    for(int j=0;j<bb.size();j++)
    {
        int tmp=0;
        bigint ans1;
        for(int i=0;i<j;i++)
            ans1.v.push_back(0);
        for(int i=0;i<aa.size();i++)
        {
            ans1.v.push_back((aa[i]*bb[j]+tmp)%10);
            tmp=(aa[i]*bb[j]+tmp)/10;
        }
        if(tmp)
            ans1.v.push_back(tmp);
        ans=ans+ans1;
    }
    return ans;
}

bigint operator/(const bigint &a, const bigint &b)
{
    bool flag=0;
    if(a.symbol!=b.symbol)
        flag=1;
    bigint aa=bigint(a,0),bb=bigint(b,0);
    if(aa<bb)
        return bigint(vector<int>(1),flag);
    bigint zero=bigint(vector<int>(1),0);
    bigint ans;
    while(aa>zero)
    {
        aa-=bb;
        if(!(aa>=zero))
            break;
        ans++;
    }
    return bigint(ans,flag);
}

bigint read()
{
    vector<int> v;
    int x;
    char c;
    bool flag=0;
    while(!isdigit(c))
    {
        if(c=='-')
            flag=1;
        c=getchar();
    }
    while(isdigit(c))
        v.push_back(c-'0'),c=getchar();
    reverse(v.begin(),v.end());
    return bigint(v,flag);
}

ostream& operator << (ostream &output,const bigint &a)
{
    vector<int> v=a.v;
    reverse(v.begin(),v.end());
    if(a.symbol)
        output<<'-';
    for(auto i:v)
        output<<i;
    return output;
}

int main()
{
    bigint a=read(),b=read();
    //do sth
    return 0;
}

PJ6 图论初步2

一些杂项

INF

图论题的INF表示两个点不连通,通常设为0x3f3f3f3f,这样两者相加就不会溢出,当需要开long long时通常设为0x3f3f3f3f3f3f3f3fLL

当然如果无负权值边的话也可以使用-1,但需要特判

不推荐使用0x7fffffff,虽然是int的最大值,但是两者相加时会溢出

一些概念

  • 点的度数
  • DAG 有向无环图

拓扑排序

定义

对DAG的顶点进行排序,要求:1. 每个点出现且仅出现一次 2. 对于顶点对(u,v),若排序后uv的前面,则不存在从vu的路径

如果给定一个DAG,从ij有边,则称j依赖于i;如果从ij有路径,则称j间接依赖于i

拓扑排序后,排在前面的节点不能依赖于排在后面的节点

算法实现

  1. 考虑将所有入度为0的点加入一个队列中

  2. 然后挨个点进行处理,设当前处理到u枚举其出边,设该边连着v,然后进行信息更新

  3. 由于u已处理过,所以相当于删除u,将v的入度-1

  4. 如果v的入度为0了,加入队列

偏序关系

从自反性,对称性,传递性三个方面考虑集合的某个关系

类似小于等于

  • \forall a\in S,a\leq a
  • \forall a,b\in Sa\leq bb\leq a,则a=b
  • \forall a,b,c\in Sa\leq bb\leq c,则a\leq c

类似小于

  • \forall a\in S, a \not
  • \forall a,b\in Sa,则b \not
  • \forall a,b,c\in Sab,则a

这类关系称为偏序关系,可以将集合中元素建点,将这些关系建成有向边变成图论问题,然后通过拓扑排序等有向图算法求解

最小生成树

一些定义

  • 连通图:任意两点间存在路径

  • 树:以下定义等价:

    • 任意两点间只存在一条路径的图
    • 无环的连通图
    • n个点n-1条边的连通图
    • n个点n-1条边 , 无环的图
  • 子图:图G’称作图G的子图如果V(G’) \sube V(G)以及E(G’) \sube E(G)

    也就是从原图中选出一些点以及和一些边组成的新的图

  • 生成子图:指满足条件V(G’)=V(G)G的子图G’

    也就是选出所有的点和一些边组成的新的图,生成树则是指子图G’是一颗树

最小生成树

对于带权图,权值和最小的生成树。

最小瓶颈生成树:对于带权图,最大权值最小的生成树,最小生成树一定是最小瓶颈生成树

算法:Prim或者Kruskal算法,推荐后者,无需建图,复杂度都为O(m\log n)

Prim

  • 随意选取一个点作为已访问集合的第一个点,并将所有相连的边加入堆中

    从堆中找到最小的连接集合内和集合外点的边,将边加入最小生成树中

    将集合外点标记为已访问,并将相连边加入堆

  • 重复以上过程直到所有点都在访问集合中

Kruskal

  • 将边按照权值排序

  • 依次枚举每一条边,若连接的两点不连通则加入最小生成树中

  • 使用并查集维护连通性

最短路

所有算法概述

  • Floyd:求多源最短路,可以求出所有点对间的最短路径,时间复杂度O(n^3)
  • Dijkstra(/’daikstra/):单源最短路,求某点到所有点的最短路,时间复杂度O(n^2),优化后O(m\log n)无法处理负权边
  • SPFA(队列优化的Bellman-Ford算法):单源最短路,时间复杂度最坏O(nm)容易被卡可以处理负权边

Floyd

本质是DP

d[i][j][k]为从i到j,仅通过编号为1-k的中间节点的最短路距离

转移方程为d[i][j][k]=min(d[i][j][k-1], d[i][j][k-1]+d[k][j][k-1]),理解:不走k的话就是d[i][j][k-1],走k的话分为两段加起来就是d[i][j][k-1]+d[k][j][k-1]

初始值为d[i][j][0]为两点之间边的权值,未联通为INF

从1到n枚举k,然后枚举(i, j),为了方便可以不开第三维,在原地迭代

int d[MAXN][MAXN];

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && i != k && j != k)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

Dijkstra

维护一个dis[maxn]数组,dis[i]代表从起点到i的最短路长度

dis[s]=0,其余为INF

松弛操作

通过某条路径更新dis[v]的值

if(dis[v]>dis[u]+e.dist)
        dis[v]=dis[u]+e.dist;

尝试使用su的最短路加上边(u, v)的长度更新sv的最短路

实现

  • 起点作为已访问集合的第一个点,并更新相连的点的dis

  • 找到未被访问的dis最小的点,标记访问,用这个点更新相连的点dis

  • 重复上述过程直到所有的点均被访问

第二步中找到未被访问的dis最小的点若使用堆来优化的话时间复杂度将为O(m\log n)

priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > q;
bool vis[maxn];
int d[maxn];

void dijkstra()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    d[s]=0;
    q.push(make_pair(0,s));//pair的首元素是dis,第二个元素是点的编号
    while (!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g[now])//遍历每一条边
            {
                if(d[e.to]>d[now]+e.dist)//松弛操作
                {
                    d[e.to]=d[now]+e.dist;
                    q.push(make_pair(d[e.to],e.to));
                }
            }
        }
    }
    return;
}

SPFA

Bellman-Ford:对整张图进行n-1次松弛,每次枚举每条边进行松弛,最后一定能得到最优解

SPFA在上述过程中避免无意义的松弛

只有成功的松弛操作才会对那个点产生影响,所以使用队列维护等待松弛的点,每次取出一个点进行松弛,对于所有松弛成功的点加入队列

判负环:如果某个点松弛了第n次,说明存在负环

queue<int> q;
bool inq[maxn];
int d[maxn];

void spfa()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    q.push(s);
    inq[s]=1;//一定记得维护inq数组
    d[s]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        inq[now]=0;
        for(auto &i:g[now])//遍历每一条边
        {
            int to=i.to,dist=i.dist;
            if(d[now]+dist<d[to])//松弛
            {
                d[to]=d[now]+dist;
                if(!inq[to])//如果不在队列中
                {
                    inq[to]=1;
                    q.push(to);//标记后加入队列
                }
            }
        }
    }
}

一些奇技淫巧

分层图

将一张图复制成若干层,并在这些图之间建立连边,然后照跑最短路

例题:P1073

我们可以考虑将图复制为三层,第一层到第二层之间将各点相连权值设为买的费用,第二层到第三层之间将各点相连权值设为卖的费用的负值,这样就可以模拟出买卖的操作,然后在同层图中边权都设为0,在同层图内移动就是普通移动,跨层移动就是买卖操作

拆点

遇到涉及到点权的最短路,可以将一个点拆为两个点,然后两个点之间边的权值为点权即可。

PJ7 简单DP

DP的引入

DP为什么比暴力快:因为它舍弃了冗余信息,只关心答案是多少,不关心是怎么来的。

无后效性

只要求出了f(n),怎么求出f(n)就无所谓了,未来与过去无关,这就叫做无后效性

严格定义:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。

最优子结构性质

在求出小问题的最优解之后,就可以利用它们求出大问题的最优解。大问题的最优解可以由小问题的最优解推出,这个性质叫做“最优子结构性质”。

DP的条件

  • 能将大问题拆成性质相同的小问题
  • 状态满足无后效性
  • 满足最优子结构性质

例题:DAG最短路

给定一个DAG,求S到T的最短路

满足无后效性:到了一个点,就无所谓怎么来的了

满足最优子结构性:对于一点P,只关心最小费用f(P),并用其推后面的问题

f(P)为到达P点所需的最小费用,R为有路通向P的所有点,w_{R\rightarrow P}RP的过路费,则:

f(P)=\min{f(R)+w_{R\rightarrow P}}

DP的本质

为什么会快

无论DP还是暴力,目标都是在可能解空间中找到最优解。暴力做法是枚举所有的可能解,但DP是枚举有希望成为答案的

DP自带剪枝,直接舍弃了一大堆不可能称为最优解的答案,而暴力是将所有都考虑进去

DP的核心思想就是尽量缩小可能解空间

操作过程

大事化小,小事化了

将大问题分解为一个个小问题,然后求解这些小问题,最终得到大问题的解

设计DP算法、

首先将面对的局面表示为x,这一步称为设计状态

对于状态x,记该状态的答案为f(x),即要求出的答案为f(T)

然后找出状态x与哪些状态有关联,写出一个式子(动态转移方程),然后通过f(p)来求出f(x)

设计流程:设计状态,表示局面,然后设计转移

例题

最大子段和

P1115,求一段序列中连续且非空的最大子段和

由于连续,所以要么继承上一个,要么重新开一个,设f(n)1n的最大子段和,序列为{a},则有

f(x)=\max(f(x-1)+a_x,a_x)

然后从头到尾统计最大f(x)即可

最长不下降子序列(LIS)

求一段序列中最长不下降子序列的长度

f(x)为以a_x结尾的LIS的长度,那么答案就是\max{f(x)}

状态转移方程:

f(x)=\max\limits_{p<x, a_p\leq a_x}{f(p)}+1

算法复杂度为O(n^2),使用优化可以O(n\log n)

记忆化搜索

记忆化搜索就是将已经计算过的且可能会被再使用的状态记录下来,防止时间的浪费。例如求斐波那契数列的第n项,有

\begin{cases}
f(0)=0\
f(1)=1\
f(n)=f(n-1)+f(n-2)\quad(n>1)
\end{cases}

如果单纯的写递归计算f(x),那么有可能一个f被计算过很多次,这样浪费时间,将其存下来的话会节省很多时间

计数类DP

P1255数楼梯

f(x)=f(x-1)+f(x-2),又是一个斐波那契的递推

注意开高精度

P1002过河卒

\begin{cases}
f(mx,my)=0\quad(mx,my)\text{为马的位置及马的控制点}\
f(i,j)=\max[f(i,j),f(i-1,j)+f(i,j-1)]
\end{cases}

2020年1月 OI学习记录

学习的内容

我很菜,又笨,所以学习的内容也很低端,但我会努力的

  • 线段树和树状数组基础
  • ST表
  • 离散化
  • A* 和 IDA*
  • 归并排序和逆序对
  • 复习二分答案
  • 简单的数论基础

刷题记录

前半个月在准备学校期末考,结果很开心AK了数学物理,所以做题咕咕了,共 15 道题,菜的一批。

总结

水平正在往上慢慢提升,也不是当年那个只能拿普及一等的菜鸡了,(但还是很菜),以后的路还很远,继续吧

PJ4 图论初步

树

基础

基础性质

  • 一对多的关系,一个父亲有多个孩子。
  • 层次性,递归定义。
  • 边数=点数-1
  • 树上两点之间路径唯一,不存在环。

一些术语

  • 深度:选定根节点后,这棵树有几层。
  • 节点的度:这个节点往外连了几条边。
  • 子节点,父节点,兄弟节点
  • 叶子节点:没有孩子的节点。

奇奇怪怪的等比数列求和公式:

S_n=\frac{a_1(1-q^n)}{1-q}

二叉树

定义:每个节点最多只有两个子节点的树

性质

  • 一棵二叉树的第i层最多有2^{i-1}个节点
  • 一棵k层二叉树的最大节点数:2^k-1

满二叉树的堆式存储:

堆式存储

可使用一个数组逐层存储
编号为i的两个子节点的编号分别为2i2i+1

树的存储

邻接矩阵

使用一个二维数组,a[u][v]表示节点u与节点v有没有边或者边权值

缺点:浪费空间,空间复杂度O(n^2)

邻接表

使用vector,每个节点都有一个vector记录它与哪些节点相连

代码实现:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int> G[N];
void addedge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

边权实现:
使用结构体

struct Edge
{
    int v,w;
};

链式前向星

使用一个动态数组(链表)进行存储,当然这种东西没有vector方便

树的遍历

先序遍历:根->左->右

中序遍历:左->根->右

后序遍历:左->右->根

image

先序遍历:

1 2 4 5 6 3

中序遍历:

4 2 6 5 1 3

后序遍历:

4 2 5 6 3 1

例题:FBI树

题目描述

我们可以把由“`0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树,它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2^N的“0101”串S可以构造出一棵FBI树T,递归的构造方法如下:

  1. T的根结点为R,其类型与串S的类型相同;
  2. 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S_1S_2;由左子串S_1构造R的左子树T_1,由右子串S_2构造R的右子树T_2

现在给定一个长度为2^N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历序列。

输入格式

第一行是一个整数N(0≤N≤10),

第二行是一个长度为2^N的“01”串。

输出格式

一个字符串,即FBI树的后序遍历序列

代码:

#include <iostream>
#include <string>
#define DAD(x) (x>>1)
#define LF(x) ((x)<<1)
#define RT(x) (((x)<<1)+1)
using namespace std;
string s;
int n,maxn;

struct node{
    string s;
    char type;
}t[3000];

void make_tree(string s,int cur)
{
    t[cur].s=s;
    int len=s.length();
    if(len!=1)
    {
        string left(s,0,len/2);
        string right(s,len/2,len/2);
        make_tree(left,LF(cur));
        make_tree(right,RT(cur));
    }
    return;
}

char dfs(int cur)
{
    char a,b;
    if(t[cur].s.length()>1)
    {
        //cout<<cur<<endl;
        a=dfs(LF(cur));
        b=dfs(RT(cur));
        if(a!=b||a=='F'||b=='F') t[cur].type='F';
        if(a=='I'&&b=='I') t[cur].type='I';
        if(a=='B'&&b=='B') t[cur].type='B';
    }
    else
    {
        t[cur].type=t[cur].s=="0"?'B':'I';
    }
    printf("%c",t[cur].type);
    return t[cur].type;
}

int main()
{
    cin>>n>>s;
    maxn=1<<n;
    make_tree(s,1);
    dfs(1);
    return 0;
}

二叉排序树

中序遍历有序的二叉树,即满足左<根<右
代码:

#include <bits/stdc++.h>
//二叉排序树:左小于根小于右 
using namespace std;
const int N=1e5+10;
struct node{
    int val,lc,rc,w;
}T[N];
int n,cnt,a[N];
void ins(int o,int v){
    if(!T[o].val)//如果该节点没有定义 
    {
        T[o].val=v;//插入值 
        T[o].w++;//w表示相同的数的数量 
        return;
    }
    if(v<T[o].val)//如果该值小于该节点的值 
    {
        if(!T[o].lc) T[o].lc=++cnt;//若未定义左节点,则定义 
        ins(T[o].lc,v);//递归 
    }
    if(v>T[o].val)//同理 
    {
        if(!T[o].rc) T[o].rc=++cnt;
        ins(T[o].rc,v);
    }
}
void dfs(int o)
{
    if(!T[o].val)return;//如果遍历到未定义节点 ,返回 
    if(T[o].lc) dfs(T[o].lc);//如果已定义,则前往左节点继续递归 
    for(int i=1;i<=T[o].w;i++)//输出 
        printf("%d ",T[o].val);
    if(T[o].rc) dfs(T[o].rc); //再遍历右节点 
}
int main()
{
    scanf("%d",&n);
    cnt=1;
    for(int i=1;i<=n;i++) scanf("%d",a+i);//扫入数据 
    for(int i=1;i<=n;i++) ins(1,a[i]);//构建 二叉排序树 
    dfs(1);//开始遍历 
    return 0;
}

树的重心

定义:挑选某个节点作为树的根节点的话,两子树的大小会相对接近,这个节点就是树的重心

理解:某些树的根不是固定的(无根树)

性质

  • 树中所有点到某点的距离和中,到重心的距离和是最小的,如果树有两个重心,到他们的距离和一样
  • 把两个树通过某一点相连得到一棵新的树,则新的树的重心必然在连接原来两棵树的重心的路径上
  • 一棵树添加或者删除一个节点,树的重心最多只移动一条边的位置

求树的重心

思想:找出最大的子树最小的节点,就是重心

  • dfs一次,算出以每个点为根的子树大小
  • 记录以每个节点为根的最大子树的大小
  • 判断:如果以当前节点为根的最大子树大小比当前更优,更新当前根
  • 代码实现:
#include<bits/stdc++.h>
const int N=1000010;
const int inf=0x7f7f7f7f;
using namespace std;
int f[N],size[N],n;
//f[i]为以i为根时,最大子树的大小
//size[i]表示以i为根的子树大小
int rt,sum;
vector<int> G[N];//存边
void addedge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}
inline void getrt(int u,int fa)
{
    size[u]=1;f[u]=0;//先将size赋初值1
    for(int i=0;i<G[u].size();i++)//开始遍历
    {
        int v=G[u][i];
         if(v==fa)
             continue;//如果遍历到的点是其父节点,忽略
        getrt(v,u);//继续递归查询
        size[u]+=size[v];//u节点的值加上以v节点为根的子树的大小
        f[u]=max(f[u],size[v]);//更新最大值
    }
    f[u]=max(f[u],sum-size[u]);//上面部分如果比下面部分还要大,更新
    if(f[u]<f[rt])rt=u;//如果子树大小的最大值比之前求出的重心的更小,则更新重心编号
}

inline int read()//快读
{
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}

int main()
{
    n=read();
    for(int i=1;i<n;i++){//扫入边
        int u=read(),v=read();
        addedge(u,v);
    }
    rt=0;sum=n;//rt表示树的重心,sum表示总结点数
    f[0]=inf;
    getrt(1,0);
    printf("%d\n",rt);
    return 0;
}

即:先假定1节点为根,然后递归自叶子节点开始求出各节点为根的子树大小,然后利用补集思想求出当该节点为整棵树的根时另一个子树的大小。当最大的子树大小最小时,说明这个节点是重心,更新

树的直径

定义:树上最长的一条树链。

求树的直径

法1 dfs

在一棵树上,对于一个点而言,离他最远的一个点一定是这棵树的直径的一个端点

第一遍dfs:找到直径的一个端点(就是从任意点出发,离它最远的点)

第二遍dfs:从一个端点开始,直接找到另一个端点

时间复杂度O(n)

代码实现:

#include<bits/stdc++.h>
const int N=1000010;
using namespace std;
int n,m,head[N],tot,dis[N],cur,mx;
//cur为直径的端点
//head数组存储以每个u为起点第一个相连的位置
//mx为最远距离max

inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}

struct Edge{
    int u,v,w,next;
}G[N<<1];

inline void addedge(int u,int v,int w){//前向星加边
    G[++tot].u=u;G[tot].v=v;G[tot].w=w;G[tot].next=head[u];head[u]=tot;
    G[++tot].u=v;G[tot].v=u;G[tot].w=w;G[tot].next=head[v];head[v]=tot;
}

inline void dfs(int u,int fa){
    for(int i=head[u];i;i=G[i].next)//链式前向星
    {
        int v=G[i].v;
         if(v==fa)//如果走回头路了
             continue;
        dis[v]=dis[u]+G[i].w;//更新距离
        if(dis[v]>mx)cur=v,mx=dis[v];//如果比目前的距离更长,更新最长值并更新端点cur
        dfs(v,u);//继续遍历
    }
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        addedge(u,v,w);
    }
    dfs(1,0);
    mx=0;
    memset(dis,0,sizeof(dis));
    dfs(cur,0);
    printf("%d\n",mx); 
}

法2 dp

不会

树是一种特殊的无向连通图

定义

G(V,E),由边和点组成的二元组

一些术语

  • 有/无向图:如果给图的每条边规定一个方向,那么得到的图称为有向图。在有向图中,与一个节点相关联的边有出边和入边之分。相反,边没有方向的图称为无向图。
  • 度:一个顶点的度是指与该顶点相关联的边的条数
  • 入度和出度:对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数;出度则是相对的概念,指以该顶点为起点的边数。
  • 自环:若一条边的两个顶点为同一顶点,则此边称作自环。

  • 点权,边权

  • DAG:有向无环图
  • 二分图:设G(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点ij分别属于这两个不同的顶点集(i \in A,j \in B),则称图G为一个二分图。判定:黑白染色法

树没有环

图的存储

类比树的存储

图的遍历

要建立一个vis数组,vis[i]表示该点有没有遍历过

因为可能会有回路出现而进入死循环

图的深度优先遍历实现:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int> G[N];
void addedge(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
}
int vis[N];
void dfs(int u){
    vis[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(vis[v])continue;
        dfs(v);
    }
}

广度优先:

const int N=1e5+10;
vector<int> G[N];
int vis[N];
queue<int> q;
void bfs(int s)
{
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(vis[v]) continue;
            q.push(v);
            vis[v]=1;
        }
    }
}

例题:封锁阳光大学:

题目描述

曹是一只爱刷街的老曹,暑假期间,他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹,感到不爽。河蟹决定封锁阳光大学,不让曹刷街。

阳光大学的校园是一张由N个点构成的无向图,N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁,当某个点被封锁后,与这个点相连的道路就被封锁了,曹就无法在与这些道路上刷街了。非常悲剧的一点是,河蟹是一种不和谐的生物,当两只河蟹封锁了相邻的两个点时,他们会发生冲突。

询问:最少需要多少只河蟹,可以封锁所有道路并且不发生冲突。

输入格式

第一行:两个整数N,M

接下来M行:每行两个整数A,B,表示点A到点B之间有道路相连。

输出格式

仅一行:如果河蟹无法封锁所有道路,则输出“Impossible”,否则输出一个整数,表示最少需要多少只河蟹。

思路分析

  1. 每一条边所连接的点中,至少要有一个被选中。
  2. 每一条边所连接的两个点,不能被同时选中。由此,可以推断出:

每一条边都有且仅有一个被它所连接的点被选中。

因此可以对每个连通图进行黑白染色

代码实现

//P1330
#include <cstdio>
#include <vector>
using namespace std;
const int N=1e5+10;
vector<int> G[N];
void addedge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

bool vis[N];
bool color[N];
int c[2];
int n,m;

bool dfs(int cur, bool col)
{
    if(vis[cur]){
        if(color[cur]==col)
            return true;
        else 
            return false;
    }
    vis[cur]=1;
    c[color[cur]=col]++;
    bool flag=1;
    for(int i=0;i<G[cur].size();i++)
    {
        int v=G[cur][i];
        flag=flag&&dfs(v,!col);
    }
    return flag;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
    }
    int ans=0;
    for(int i=1;i<=n;i++)//从第一个点开始遍历处理连通图 
    {
        c[1]=c[0]=0;
        if(vis[i]) continue;//如果已处理,跳过
        if(!dfs(i,0))
        {
            puts("Impossible\n");
            return 0;
        }
        ans+=min(c[1],c[0]);
    }
    printf("%d\n",ans);
    return 0;
}

例题:信息传递:

题目描述

有 n 个同学(编号为 1 到 n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 i 的同学的信息传递对象是编号为T_i的同学。

游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息, 但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自 己的生日时,游戏结束。请问该游戏一共可以进行几轮?

输入格式

共2行。

第1行包含1个正整数 n ,表示 n 个人。

第2行包含 n 个用空格隔开的正整数 T_1,T_2,\cdots\cdots,T_n,其中第 i 个整数T_i 表示编号为 i的同学的信息传递对象是编号为T_i的同学,T_i \leq nT_i \neq i

输出格式

1个整数,表示游戏一共可以进行多少轮。

思路分析

可以将其看作一个有向图,求其中的最小环

对每一个节点打一个时间戳,比较两次进入同一节点的时间戳之差即可。

代码实现

//P2661
#include <cstdio>
using namespace std;

int g[200050],t[200050];
int n;
int time,ans=1000000000;

inline void make_edge(int u,int v)
{
    g[u]=v;
}

inline void dfs(int cur)
{
    if(!g[cur]) return;
    time++;
    if(time>t[cur]&&t[cur]){
        ans=min(ans,time-t[cur]);
        t[cur]=0;
        g[cur]=0;
        return;
    }
    t[cur]=time;
    dfs(g[cur]);
    t[cur]=0;
    g[cur]=0;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int t;
        scanf("%d",&t);
        make_edge(i,t);
    }
    for(int i=1;i<=n;i++) dfs(i);
    printf("%d",ans);
    return 0;
}

PJ3 递推与分治

PJ3 递推与分治

[TOC]

递推

有些问题中,相邻两项或多项数字(或状态)之间存在某种关系,可以通过前一项或多项按照某一规律推出其后一项数字(或状态),或者是通过后一项或多项按照某一规律推出其前一项数字(或状态)。我们可将这种规律归纳成如下递推关系式:

F_n=g(F_{n-1})或F_{n-1}=g(F_n)

从前状态推出后状态称为顺推,反之称为逆推。分别对应程序中的递推递归

Fibonacci数

嗯,这个很好找,就是:

\begin{cases}
f(0)=0\
f(1)=1\
f(n)=f(n-1)+f(n-2)\quad(n>1)
\end{cases}

int f[maxn];
f[0]=0,f[1]=1;
for(int i=2;i<=n;i++)
    f[i]=f[i-1]+f[i-2]

简单组合计数

基本原理

容斥原理

n+1件东西放入n个抽屉,则至少有一个抽屉里放了两件或两件以上的东西。从另一个角度说,把n-1件东西放入n个抽屉,则至少有一个抽屉是空的。

多个集合的容斥原理

总元素=每个集合加起来-两两交集+三三交集-四四交集+五五交集….etc.

|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

加法原理

如果完成事件An种方法,完成事件Bm种方法,那么完成两者之一有n+m种方法。

乘法原理

如果完成事件An种方法,完成事件Bm种方法,那么先完成A后完成Bn\cdot m种方法。

排列

n个数中有序地取出m个数的方案:

简化:先考虑n个数有几种排列方案

考虑乘法原理,第1个数有n个可能,第2个有n-1个可能,依次类推,所以n个数的排列方案一共有n!

n\times (n-1) \times (n-2) \times (n-3)\times…….\times 1
=n!

n个数中有序地取出m个数的方案

同样考虑乘法原理,第1个数有n种可能,第2个数有n-1种可能,以此类推,一共需要取m个数,所以第m个数有n-m+1种可能。

n\times (n-1)\times(n-2)\times(n-3)\times……\times(n-m+1)\
表示为A^m_n=P^m_n=\frac{n!}{(n-m)!}

组合

n个数中无序地取出m个数的方案:

由于m个数一共有m!种排列方案,所以将A^m_n去掉重复的排列即可,即\displaystyle\frac{A^m_n}{m!}

定义

表示为C^m_n=\frac{A^m_n}{m!}=\frac{n!}{m!(n-m)!}\
也记作C(n,m)

组合数的递推

杨辉三角形

1\
1\quad1\
1\quad2\quad1\
1\quad3\quad3\quad1\
1\quad4\quad6\quad4\quad1\
1\quad5\quad10\quad10\quad5\quad1\
…………………..

我们规定C^0_n=1
则有

1\
C^0_1 \quad C^1_1\
C^0_2 \quad C^1_2 \quad C^2_2\
C^0_3 \quad C^1_3 \quad C^2_3\quad C^3_3 \
C^0_4\quad C^1_4\quad C^2_4\quad C^3_4\quad C^4_4\
…………………..

所以可推出:

C^m_n=C^{m-1}_{n-1}+C^{m}_{n-1}

它的意义:考虑选不选最后一个元素,如果不选他就是C_{n-1}^m,如果选了它,那么就要在剩下n-1个数中选出m-1个,那么就是C_{n-1}^{m-1},两者相加即可

又由杨辉三角形的对称性还可知:

C^m_n=C^{n-m}_n

二项式定理

(a+b)^n=\sum_{i=0}^n C^i_n\times a^i\times b^{n-i}

一些使用二项式定理的常用模型:

\sum_{i=0}^nC_n^i=2^n\tag{1}

\sum_{i=0}^n(-1)^iC_n^i=0\tag{2}

C_n^0+C_n^2+\cdots=C_n^1+C_n^3+\cdots=2^{n-1}\tag{3}

证明:

  1. 由二项式定理,当a=b=1

\begin{aligned}
(1+1)^n&=\sum_{i=0}^n C^i_n\times 1^i\times 1^{n-i}\
2^n&=\sum_{i=0}^nC^i_n
\end{aligned}

  1. 由二项式定理,当a=-1,b=1

\begin{aligned}
(-1+1)^n&=\sum_{i=0}^nC^i_n\times (-1)^i\times 1^{n-i}\
\sum_{i=0}^n (-1)^i C_n^i&=0
\end{aligned}

a=1,b=-1

\begin{aligned}
\left[1+(-1)\right]^n&=\sum_{i=0}^n C_n^i\times 1^i\times (-1)^{n-i}\
\sum_{i=0}^n C_n^i\times (-1)^{n-i}&=0
\end{aligned}

3.

\begin{aligned}
将前面的(1)(2)式相加,得到\
2C_n^0+2C_n^2+\cdots&=2^n\
C_n^0+C_n^2+\cdots&=2^{n-1}
\end{aligned}

同理也可以得到C_n^1+C_n^3+\cdots=2^{n-1}

卡特兰数

现在有n对括号,可以组成多少种合法的括号序列?

合法的括号序列:左右匹配,先左后右

C(n)n对括号时,合法的括号序列的数量

为了区分,我们给每一对括号一个编号

那么假设最后一个右括号是编号为x的,它的总方案数就是

C(x-1)\times C(n-x)

卡特兰数:

\begin{cases}
&C(0)=1\
&C(n)=\sum^{n-1}_{i=0}C(i)\times C(n-i-1), n\geq 1 \
\end{cases}

递推式:

C(n)=\frac{2(2n-1)}{n+1}\times C(n-1)

常见问题变形:

  • n对括号的括号序列数
  • n个数的出栈序列
  • n个点能构成多少种不同的二叉树

递归

递归,就是一个函数调用自己

但是递归很慢。。。。。。而且可能爆栈

但是递归是很多算法和DS的基础,比如二分(当然也可以不用),dfs,线段树,等等等

分治

分治就是分而治之,把一个问题划分成若干个同样的小问题,然后各个击破

我们发现了,分治和递归思想是一脉相承的,大化小,小化了

常见的应用:快速幂,求逆序对等等

PJ2 二分/贪心+DS2

二分

二分查找

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

每次折半搜索,复杂度为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();//返回堆顶元素的值

PJ1 基础数据结构

线性表

栈就是一个线性表,弹出和压入数据都从顶部进行。

栈的本质:先进后出 (LIFO表)。手写栈的实现:开一个数组并定义一个指针指向顶端元素。

#include <cstdio>

int s[10005];
int tot=0;

void push(int x)
{
    s[++tot]=x;//每次操作将指针往上移再插入
    return;
}

void pop()
{
    --tot;//出栈的时候直接将tot下移
}

int top()//查询栈顶操作
{
    return s[tot];
}

int size()
{
    return tot;
}

应用:括号匹配问题,火车进/出站问题等。

例题:后缀表达式

分析:后缀表达式明显满足栈的要求,只需要开一个栈,读入数字并存储,遇到符号就进行操作即可。

实现:

#include <cstdio>
#include <stack>
using namespace std;

stack<int> a;
char s[1200];

int main()
{
    scanf("%s",s);
    int p=0;
    int x,y;
    for(int i=0;s[i]!='@';i++)
    {
        switch(s[i])
        {
            case '.':
                a.push(p);
                p=0;
                break;
            case '*':
                x=a.top();
                a.pop();
                y=a.top();
                a.pop();
                a.push(x*y);
                break;
            case '+':
                x=a.top();
                a.pop();
                y=a.top();
                a.pop();
                a.push(x+y);
                break;
            case '-':
                x=a.top();
                a.pop();
                y=a.top();
                a.pop();
                a.push(y-x);
                break;
            case '/':
                x=a.top();
                a.pop();
                y=a.top();
                a.pop();
                a.push(y/x);
                break;
            default:
                p*=10;
                p+=(s[i]-'0');
                break;
        }
    }
    printf("%d",a.top());
    return 0;
}

队列

队列可以模拟收银,办事等,越早进入越早离开。

每次弹出操作在队首进行,压入从队尾进行。

本质:先进先出 (FIFO表)

手写队列的实现:使用一个大数组,定义两个指针,一个指向队首,一个指向队尾。

int s[100005],head,tail;
void push(int x)
{
    s[++tail]=x;
}
void pop()
{
    head++;
}
int front()
{
    return s[head];
}

缺点:浪费空间,可能溢出。

解决方案:使用STL或者循环队列

#include<queue>
queue<int> q;
q.front();//(返回第一个元素)
q.push(x);//元素入队
q.empty();//返回一个bool值代表队列是否为空
q.size();//返回队列中元素数量

例题:约瑟夫问题

分析:1…n这些小朋友站在队列里。接下来,队首的人队,然后走到队尾,这样一直循环,直到第k个小朋友。他淘汰出局,不再入队。队内现在只剩下了n-1名小朋友,继续重复刚刚的操作:前k-1个人出队之后走到队尾,接下来那位小朋友直接淘汰。

代码实现:

#include <cstdio>
#include <queue>
using namespace std;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    queue<int> q;
    for(int i=1;i<=n;i++)
        q.push(i);
    for(int i=1;!q.empty();i++)
    {
        int x=q.front();
        q.pop();
        if(i%m)
        {
            q.push(x);
        }
        else
        {
            printf("%d ",x);
        }
    }
    return 0;
}

双端队列:deque

#include <deque>
using namespace std;

deque<int> d;
d.push_front();
d.push_back();
d.pop_back();
d.pop_front();

d.front();
d.back();

d[i];//复杂度高,返回第i个元素

链表

链表是一种链式结构,相邻的元素相连接。

  • 单向链表
  • 双向链表
  • 循环链表

单链表的实现:

  • 删除任意元素
  • 任意查询元素
  • 任意插入元素
  • 连接两个链表

可以使用指针,也可以使用数组模拟。

并查集&HASH表

并查集

例题:P1551 亲戚

分析:染色法

最开始,每个人都有自己颜色。如果A,B都是亲戚,那么将所有颜色为B的人染成A。查询时只需判断A和B是否同色。

但可以不染色,进行标记数组bin。询问时可以通过查询bin数组,来知道x最后应为什么颜色。

#include <cstdio>

struct unionFind//使用一个结构体代表并查集
{
    int bin[100005];
    unionFind()//构造初始化时
    {
        for(int i=1;i<=100003;i++) bin[i]=i;//初始化,每个人一开始是自己的颜色
    }
    int anc(int x)//查询最终颜色
    {
        if(bin[x]==x)
            return x;
        else return anc(bin[x]);//递归查找最终的颜色
    }
    void uni(int x,int y)//连接操作
    {
        bin[anc(x)]=anc(y);
    }
    void ask(int x,int y)//查询操作
    {
        printf("%s\n",anc(x)==anc(y)?"Yes":"No");//如果x最终颜色与y相同,输出。
    }
}u;

int main(void)
{
    int n,m,p;
    scanf("%d %d %d",&n,&m,&p);
    while(m--)
    {
        int i,j;
        scanf("%d %d",&i,&j);
        u.uni(i,j);
    }
    while(p--)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        u.ask(x,y);
    }
    return 0;
}

把一个集合的bin最终指向的元素,叫做该集合的代表。上述操作中实现了合并集合和查询两元素是否在同一集合的操作。

最坏时间复杂度:链式。

解决方法:路径压缩,每次查询回来时直接将该路的元素的bin值直接指向代表元素。时间复杂度约等于O(n)

例题:P3367 【模板】并查集

#include <cstdio>
using namespace std;

struct Uf
{
    int bin[10005];

    Uf()
    {
        for(int i=1;i<=10002;i++)
            bin[i]=i;
    }
    int anc(int x)
    {
        if(bin[x]==x) return x;
        return bin[x]=anc(bin[x]);//改变原bin值,进行路径压缩
    }
    void uni(int x,int y)
    {
        bin[anc(x)]=anc(y);
    }
    void ask(int x,int y)
    {
        printf("%c\n",anc(x)==anc(y)?'Y':'N');
    }
}u;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int z,x,y;
        scanf("%d%d%d",&z,&x,&y);
        if(z==1) u.uni(x,y);
        if(z==2) u.ask(x,y);
    }
    return 0;
}

总结:并查集的实现:结构体,bin数组,查询祖先操作的同时进行路径压缩。

HASH表

问题:给出你朋友的身份证号,再给出几个号判断是否为好友。

分析:不能直接使用bool数组,会严重MLE。

hash表的本质:映射,定义一函数f(x),一个关键字k放在一个存储地址f(k)上,可以加快查找的速度,但是如果对于两个不同的关键字k_1k_2,HASH函数返回了相同的值,此时就发生了HASH碰撞,实现时一定要减小碰撞。

常用的映射方法有取余运算,有定理:期望每\sqrt{p}个朋友有两个人的id%p会相等,为了减少碰撞,p要取尽量大。

减少碰撞的方法:双取余,拉链法

struct zip
{
    vector<int> w[ha+5];//ha代表要取模的数
    void ins(int x)
    {
        w[x%ha].push_back(x);//对应的地址插入该数据,避免直接使用bool值带来的碰撞
    }
    void ask(int x)//查询操作
    {
        for(auto i=w[x%ha].begin();i!=w[x%ha].end();i++)//遍历对应地址的vector,判断
            if(*i==x) {printf("Yes\n");return;}
        printf("No\n");
        return;
    }
};

双模数:两个模数同时认为此人为朋友时,才是朋友(不能避免碰撞)

最常用:STL,复杂度O(n\log n)

//前面加#include <set>
unordered_set <int> S;
S.insert(x);
//判定:
S.count(x);//判断之是否为0

取模的数p一般取质数:加大有效位数,稀释碰撞概率