解题报告 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太好用了

解题报告 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序列。

代码实现:

#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,仔细读题

法二:线段树/树状数组

updated on 2020/10/02

权值线段树维护的是一个数的出现次数,比如如果 f[k] 维护的是区间 [l,r],那么 f[k] 的值就为 [l,r] 中每个数的出现次数之和。

在处理逆序对时,我们可以这样做:从后往前,当处理到某个数 x 时,如果 x 要和后面的数产生逆序对,则必须后面的数要小于 x。又由于后面的数都是已经加入了线段树的,所以 x 产生的逆序对个数就是当前在线段树内严格小于 x 的数的个数之和。依次处理即可

由于值域很大(1e9)级别,所以需要离散化。

排序和离散化和线段树的复杂度都是 O(n\log n),所以总复杂度也为 O(n\log n),介于使用线段树/树状数组需要先进行离散化,所以常数会远大于归并排序,但仍需掌握用法。

线段树的代码:

#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;
typedef long long ll;

#define L (k<<1)
#define R (L|1)
#define M ((i+j)>>1)

inline int read()
{...}

const int maxn=5e5+5;
int n,cnt,raw[maxn],a[maxn],f[maxn<<2];

void ins(int i,int j,int x,int k)
{
    if(i==j)
    {
        f[k]++;
        return;
    }
    if(x<=M)
        ins(i,M,x,L);
    else
        ins(M+1,j,x,R);
    f[k]=f[L]+f[R];
    return;
}

ll query(int i,int j,int x,int y,int k)
{
    if(x>y)
        return 0;
    if(x<=i && y>=j)
        return f[k];
    ll ans=0;
    if(x<=M)
        ans+=query(i,M,x,y,L);
    if(y>M)
        ans+=query(M+1,j,x,y,R);
    return ans;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=raw[i]=read();
    sort(a+1,a+n+1);
    cnt=unique(a+1,a+n+1)-a-1;
    ll ans=0;
    for(int i=n;i>=1;i--)
    {
        int cur=lower_bound(a+1,a+cnt+1,raw[i])-a;
        ins(1,cnt,cur,1);
        ans+=query(1,cnt,1,cur-1,1);
    }
    printf("%lld\n",ans);
}

树状数组

#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;
typedef long long ll;

inline int read()
{...}

const int maxn=5e5+5;
int n,cnt,raw[maxn],a[maxn],f[maxn];

void ins(int x)
{
    for(;x<=cnt;x+=(x&-x))
        f[x]++;
    return;
}

ll query(int x)
{
    ll ans=0;
    for(;x;x-=(x&-x))
        ans+=f[x];
    return ans;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=raw[i]=read();
    sort(a+1,a+n+1);
    cnt=unique(a+1,a+n+1)-a-1;
    ll ans=0;
    for(int i=n;i>=1;i--)
    {
        int cur=lower_bound(a+1,a+cnt+1,raw[i])-a;
        ins(cur);
        ans+=query(cur-1);
    }
    printf("%lld\n",ans);
}