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;
}

解题报告 HDU4707 Pet

题目内容

HDU4707

注意读题:本题的题意是让我们求出仓鼠可能在多少个位置。由于trap在距离d以内可以捕获仓鼠,所以仓鼠一定在d以外,题目要求求的是距离根节点距离大于d的点的个数

解题思路

给出了边的条数是点数减一,所以这张图是一棵树。使用dfs遍历一遍树然后统计距离大于d的点数即可

坑点:

  • 本题有多组测试数据,每次要重新初始化一遍相关变量。
  • 遍历树的时候记得打vis标记(因为太久没做树的题了所以忘记打标记造成无限递归
  • 节点是从0开始编号的

这里使用了OOP编程(真的香

每次处理新的测试数据时清空即可

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

int T;
const int maxn=100000+5;

class tree//tree类
{
public:
    vector<int> g[maxn];//邻接表存树
    bool vis[maxn];//vis数组
    int depth[maxn];//记录每个节点的深度
    int n,d;//注意节点从0开始编号
    inline void ins(int x,int y)//插入操作
    {
        g[x].push_back(y);
        g[y].push_back(x);
    }

    void dfs(int cur,int dep)//dfs
    {
        //printf("%d ",cur);
        depth[cur]=dep;//更新遍历到的节点的深度
        for(int i=0;i<g[cur].size();i++)//寻找该节点与哪些节点相连
            if(!vis[g[cur][i]])//判重
            {
                vis[g[cur][i]]=1;
                dfs(g[cur][i],dep+1);//继续遍历
            }
        return;
    }
    int ans()//统计答案的函数
    {
        int ret=0;
        for(int i=0;i<n;i++)
            if(depth[i]>d)
                ret++;//统计答案
        return ret;
    }
    void clear()//每次操作前记得清空
    {
        n=d=0;
        memset(depth,0,sizeof(depth));
        memset(g,0,sizeof(g));//我也是服了居然vector可以用memset
        memset(vis,0,sizeof(vis));
        vis[0]=1;//vis[0]必须设为1,不然会WA
    }
}t;

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        t.clear();//每次使用记得清空
        scanf("%d %d",&t.n,&t.d);
        for(int i=1;i<t.n;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            t.ins(x,y);
        }
        t.dfs(0,0);//开始遍历,从0号节点开始
        printf("%d\n",t.ans());
    }
    return 0;
}

反思

太久没做树的题果然会手生qwq

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();//返回堆顶元素的值

解题报告 P1083 借教室【NOIP2015TGD2T2】

题目内容

P1083

解题思路

嗯,这道题一看,暴力枚举

分析:这道题满足二分答案,为什么:

我们将订单挨个标号,很显然,订单越多,越难满足要求,这满足二分答案要求的单调性。我们只需将订单挨个枚举即可。

二分的答案是订单的标号,订单越多越到后面越不能满足,因此很容易找到那个”1″和”0″的分界,使用一个check函数即可判断。

至于check函数的实现,这里使用了差分的重要思想。每一个订单会给出起始时间s和末尾时间t,相当于在[s,t]这段时间内多租借d个教室,很像区间加问题。所以我们定义一个数组c存储需要使用的教室的差分,处理每个订单的时候就c[s[i]]+=d[i],c[t[i]+1]-=d[i]注意是t[i]+1,并且是-=,已掉坑不止5次。然后将差分数组加起来(求前缀和)判断这么多个订单能否满足能提供教室的条件,返回即可。

代码实现:

#include <cstdio>
#include <cstring>
#define f(i,a,b) for(int i=a;i<=b;++i)

const int maxn=1e6+5;
int n,m,r[maxn],d[maxn],s[maxn],t[maxn],diff[maxn];//r,d,s,t见题意,diff为差分数组

inline int read()//我喜欢快读
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

bool check(int mid)
{
    memset(diff,0,sizeof(diff));//每次使用的时候要清零差分数组
    f(i,1,mid)
        diff[s[i]]+=d[i],diff[t[i]+1]-=d[i];//操作差分数组实现区间加
    int ans=0;//记录前缀和
    f(i,1,n)
    {
        ans+=diff[i];//每次加起来
        if(ans>r[i])//如果不能满足需要
            return 0;
    }
    return 1;//否则return true
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    n=read(),m=read();
    f(i,1,n)
        r[i]=read();
    f(i,1,m)
        d[i]=read(),s[i]=read(),t[i]=read();
    //以上读入数据
    int l=1,r=m;//开始二分
    while(l<r)//mid越大越难不挨卡
    {
        int mid=l+r>>1;
        if(check(mid))//如果满足要求
            l=mid+1;//说明mid可能还可以更大
        else
            r=mid;//否则mid就太大了
    }
    if(r!=m)//如果r!=m的话说明不能满足所有订单
        printf("-1\n%d\n",r);
    else//否则可以满足所有订单
        printf("0\n");
    return 0;
}

反思

蓝题,果然在二分的思维比较难,而且二分答案的代码细节非常多。

下次再写一波

解题报告 P2678 跳石头

题目内容

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;
}

反思

二分答案,当题目中有最大的最小或者最小的最大时一般就可以使用,需要条件满足单调性和有界性。

比如这个跳石头,跳的最短距离越大需要挪走的石头越多,就可以使用二分答案枚举答案求解

然鹅我还是不会二分答案

解题报告 HDU1754 I HATE IT

题目内容

hdu1754

题意

维护一些学生成绩,支持单点修改和区间求最值操作

解题思路

嗯,造一棵线段树即可

#include <bits/stdc++.h>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)
#define f(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=200000+5;

int a[maxn],f[maxn<<2];

void build(int i,int j,int k)//造树
{
    if(i==j) f[k]=a[i];
    else
    {
        build(i,M,L);
        build(M+1,j,R);
        f[k]=max(f[L],f[R]);
    }
    return;
}

void modify(int u,int d,int i,int j,int k)//单点编辑操作
{
    if(i==j) f[k]=d;
    else
    {
        if(u<=M) modify(u,d,i,M,L);
        if(u>M) modify(u,d,M+1,j,R);
        f[k]=max(f[L],f[R]);//每次操作完记得回溯
    }
    return;
}

int query(int u,int v,int i,int j,int k)//区间查询操作
{
    if(u==i&&v==j) return f[k];
    else
    {
        if(v<=M) return query(u,v,i,M,L);
        if(u>M) return query(u,v,M+1,j,R);
    }
    return max(query(u,M,i,M,L),query(M+1,v,M+1,j,R));
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        f(i,1,n) scanf("%d",&a[i]);
        build(1,n,1);
        getchar();//嗯,读入回车符把我坑死了
        f(i,1,m)
        {
            char c;int a,b;
            scanf("%c %d %d\n",&c,&a,&b);//记得读入回车符
            if(c=='U') modify(a,b,1,n,1);
            if(c=='Q') printf("%d\n",query(a,b,1,n,1));
        }
    }
    return 0;
}

反思

tmd这个回车符把我弄得要死不活的
要么使用cin(怎么可能),要么使用getchar()直接读入回车符,要么使用scanf的格式化功能直接把回车符干掉。

然后每组数据读入完之后记得memset即可

解题报告 P1097 统计数字(NOIP2007TGT1)

题目内容

P1097

解题思路

嗯。。。提高第一题水题。

主要思想还是离散化,可以用HASH做,但我懒得写(不会),于是我选择了万能的map,这个东西真好用。

使用了一个新函数unique(),这个函数拿来在有序的序列中去重,将重复的元素都放回了序列尾端并返回去重后最后一个元素的指针。

代码实现:

#include <map>
#include <cstdio>
#include <algorithm>//sort和unique都定义在algorithm头文件中
#define R register
using namespace std;

const int maxn=200000+5;
map<int,int> m;//map用来存储这个数字出现的次数

int n,a[maxn];

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

int main()
{
    int n=read();
    for(R int i=1;i<=n;i++)
    {
        a[i]=read();//读入数据
        m[a[i]]++;//记录次数
    }
    sort(a+1,a+n+1);//先将无序的序列有序化
    int nn=unique(a+1,a+n+1)-(a+1);//去重,再获得去重后剩余元素的个数
    for(R int i=1;i<=nn;i++) printf("%d %d\n",a[i],m[a[i]]);//输出
    return 0;
}

map太好用了

解题报告 P2324/LOJ2151 [SCOI2005]骑士精神

题目内容

洛谷2324

LOJ2151

大意:在一个 5\times5 的棋盘上有 12 个白色的骑士和 12 个黑色的骑士,且有一个空位。在任何时候一个骑士都能按照骑士的走法(它可以走到和它横坐标相差为 1,纵坐标相差为 2 或者横坐标相差为 2,纵坐标相差为 1 的格子)移动到空位上。

给定一个初始的棋盘,怎样才能经过移动变成给定目标棋盘:

解题思路

该题明显是一个裸的搜索,但是暴搜铁定超时,再看到限制15步以内,于是想到打随机化使用来迭代加深。

同时这里还可以使用启发式搜索来进行剪枝,这里的估价函数可设为不在应有位置的骑士个数,然后每次枚举移动步数进行迭代加深即可。

像这种移动棋子的题选择移动空位会更好想一点,然后记得处理读入

代码(这个代码不知道为什么洛谷上没输出 LOJ 就 AC 了:

#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;

const int tar[5][5]={//目标状态,1表示黑子,0表示白子,2表示空位
    {1,1,1,1,1},
    {0,1,1,1,1},
    {0,0,2,1,1},
    {0,0,0,0,1},
    {0,0,0,0,0}
};
int board[5][5],idt;
const int fx[8]={1,1,-1,-1,2,2,-2,-2},fy[8]={2,-2,2,-2,1,-1,1,-1};//移动的数组

int h()//估价函数
{
    int res=0;//统计多少枚棋子不在目标位置上
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            if(board[i][j]!=tar[i][j]) res++;
    return res;
}

bool dfs(int x,int y,int d)//x,y为空位坐标,d为当前枚举的深度
{
    if(d+h()>idt+1) return false;//如果估价函数显示这个限制深度铁定过不了就剪枝
    if(!h()) return true;//如果已经到达目标状态,直接返回true
    for(int k=0;k<8;k++)//枚举各个方向
    {
        int x1=x+fx[k],y1=y+fy[k];
        if(x1>4||x1<0||y1>4||y1<0) continue;//判定越界
        swap(board[x][y],board[x1][y1]);//否则交换棋子和空位的位置
        if(dfs(x1,y1,d+1)) return true;//继续dfs,如果搜到了目标状态,返回
        swap(board[x][y],board[x1][y1]);//回溯
    }
    return false;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)//毒瘤题目有很多组数据
    {
        int x0,y0;
        for(int i=0;i<5;i++)
        {
            char s[5];
            scanf("%s",s);
            for(int j=0;j<5;j++)
            {
                if(isdigit(s[j])) board[i][j]=s[j]-'0';
                if(s[j]=='*')
                {
                    board[i][j]=2;
                    x0=i;
                    y0=j;
                }
            }
        }
        bool flag=0;
        for(idt=1;idt<=15;idt++)//枚举深度
        {
            if(dfs(x0,y0,0)){flag=1;break;}//如果当前限制搜到了,那么停止
        }
        printf("%d\n",flag?idt:-1);
    }
    return 0;
}

解题报告 P1908 逆序对

题目内容

P1908

前言:归并排序

这里把归并排序写了留给我这个蒟蒻以后看

归并排序:时间复杂度O(n\log n),空间复杂度O(n)的稳定排序算法。(试了一下,模板题速度比stl的sort还快,快排123ms,归并105ms,加上40行优化后77ms)

思想是递归+二分

将一个无序的序列先挨次递归分成两端两端,使左右两端先有序,然后从底往上依次合并小的分段序列,具体操作如下:

设需操作的序列左端下标为l,右端下标为r,则定义一变量mid=l+r>>1(代表l+r的和除以2,使用二进制优化常数),则左端序列是[l,mid],右端是[mid+1,r],再分别对其递归式地分割。

合并时定义三个指针l,r和k,分别指向左端序列的开头,右端序列的开头和新的临时序列b的对应位置,然后比较a[i]a[j]的值,如果a[i]<a[j],则将a[i]放入b序列中,并将指针i,k各加一,如果a[i]>a[j],同理,将a[j]放入b序列中,并将指针j,k各加一。

为什么可以这样处理,因为需要合并的两端的序列都已经是有序的了(经过上一层递归处理过),再这样合并即可。

如果有剩余,则继续将i指针指向的内容和j指针指向的内容放入b序列中排好序的元素重新复制回a序列。

,然后再将b序列中排好序的元素重新复制回a序列。

网图:
简书@CoderJed(https://www.jianshu.com/p/33cffa1ce613)

代码实现:

#include <cstdio>
using namespace std;

const int maxn=1e5+4;

int a[maxn],b[maxn],N;//开局时先定义两个数组,a存储数据,b为归并时要用的辅助数组

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

void msort(int l, int r)//排序函数
{
    if(l==r) return;//如果l=r,那么return
    int mid=l+r>>1,i=l,j=mid+1,k=l;//定义mid变量和i,j,k三个指针
    msort(l,mid);msort(mid+1,r);//递归处理左和右序列
    while(i<=mid&&j<=r)//开始归并
    {
        if(a[i]<=a[j]) b[k++]=a[i++];//如果a[i]<=a[j],将a[i]放入b序列并将指针后移
        else b[k++]=a[j++];//否则将a[j]放入序列
    }
    while(i<=mid) b[k++]=a[i++];//处理剩下的
    while(j<=r) b[k++]=a[j++];//处理剩下的
    for(int ii=l;ii<=r;ii++) a[ii]=b[ii];//复制结果回a数组
}

int main()
{
    N=read();
    for(int i=1;i<=N;i++)
        a[i]=read();
    msort(1,N);
    for(int i=1;i<=N;i++)
        printf("%d ",a[i]);
    return 0;
}

解题思路

首先要搞懂什么是逆序对

逆序对就是序列中a_i>a_j且i<j的有序对

搞清楚了什么是逆序对,让我们看看为什么归并排序能帮助我们解题

题目要求寻找的是逆序对的数目,而我们在做每一次合并的时候都会做a[i]是否大于a[j]的判断,通过这样的判断我们就可以找出逆序对的对数,如果a[i]大于a[j],那么由于合并过程中两边的序列都是有序的,那么就一定会产生mid-i+1对逆序对:

看下面例子:

要合并的序列:1 2 5 6 (下标为i)
             3 4 5 7 (下标为j)

开始合并:
step 1: i=1, j=5, 1<3, 将1放入b序列中并i++
step 2: i=2, j=5, 2<3, 将2放入b序列中并i++
step 3: i=3, j=5, 5>3, 由于左序列后面所有的数都大于3,因此会产生5->3,6->3两个逆序对,
                       即mid-i+1个,且将3放入b序列中并j++
step 4: i=3, j=6, 5>4, 由于左序列后面所有的数也都大于4,因此会产生5->4,6->4两个逆序
                       对,也是mid-i+1个,且将4放入b序列中并j++
step 5: i=3, j=7, 5=5, 将5放入b序列中并i++
step 6: i=4, j=7, 6>5, 产生1个逆序对6->5,将5放入b序列中并j++
step 7: i=4, j=8, 6<7, 将6放入b序列中,由于i已经到达上限,故结束此过程,将剩余的7放入b序列

因此我们得到一个规律,每当发现a[i]>a[j]时,会产生mid-i+1个逆序对,计入ans即可,要注意ans要开long long,否则会炸。

代码如下:

#include <cstdio>
using namespace std;
typedef unsigned long long ll;

const int maxn = 5e5 + 10;
ll ans = 0;
int a[maxn], b[maxn], n;

void msort(int l, int r)//归并排序,只是加了记录ans而已
{
    if(l==r) return;
    int mid=(l+r)/2,i=l,j=mid+1,k=l;
    msort(l,mid);msort(mid+1,r);
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) b[k++]=a[i++];
        else b[k++]=a[j++],ans+=mid-i+1;//记录ans
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(int ii=l;ii<=r;ii++) a[ii]=b[ii];
}

int main()
{
#ifndef ONLINE_JUDGE//本地调试使用
    freopen("1908.in", "r", stdin);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    msort(1, n);
    printf("%llu\n", ans);//输出记得llu
    return 0;
}

反思

第一次打归并排序,其实归并排序本质上也就是一个分治的思想,将一个大的序列细分,逐个变为有序再最后合并。

逆序对,emm,仔细读题