豕の家

Stay hungry Stay foolish

算法  洛谷P1955 [NOI2015] 程序自动分析
March 15, 2021 / 17:15 / 64 °C

LOGO

contraints

​ 可以看到i,j的规模是1e9的,这样的数据范围非常大,如果开一个相应大小的数组一定超限。所以需要学习离散化的方法来解决。

​ 这里引用一篇简述离散化使用方法的博文:


​ 何为离散化?离散化,就是把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。

​ 比如给你n个数:98998988,32434234,433234556,32434234,8384733,……

​ 让你统计其中每个数出现的次数,传统的做法有好几种,比如一遍一遍的扫过去,比对叠加,这样算法的效率是O(n2),效率低下;

​ 再比如先排序,再统计连续的相同的个数,这里的效率已经有所提高了,不过假如上面的数据是一道线段树的题目给出的数据,那么建树需要的空间开销实在是太大了。

​ 再改进一下,采用哈希的方法,开一个大于其中最大数的数组并初始化为零,O(n)扫一下,在该数字对应的下标的元素上+1,如果对于比较小的数字还好说,但是对于上面出现的数字直接采用哈希对空间的开销是十分大的也是没有必要的,所以这里用到了数据的离散化。

​ 首先将数字排序:32434234,32434234,43324556,8384733,98998988

​ 去重后给予其对应的索引:0,0,1,2,3分别对应每个数,就可以简化很多操作,减少了很多不必要的资源开销。

​ 除了对于较大整数需要使用离散化之外,对于一些需要使用整型数据结构,但给出的数据却是小数的也可以使用离散化,将其索引为整数就可以了。

那么可以总结出离散化的步骤:

  1. 排序
  2. 去重
  3. 索引

为了简化代码,我们采用STL算法离散化:

int a[n], b[n], sub[n]; //a[n]是即将被离散化的数组,b[n]是a[n]的副本,sub用于排序去重后提供离散化后的值
sort(sub, sub + n);
int size = unique(sub, sub + n) - sub;
for(int i = 0; i < n; i++)
    a[i] = lower_bound(sub, sub + size, a[i]) - sub; //即a[i]为b[i]离散化后对应的值

​ 对于第3步,若离散化后序列为0, 1, 2, ..., size - 1则用lower_bound,从1, 2, 3, ..., size则用upper_bound,其中lower_bound返回第1个不小于b[i]的值的指针,而upper_bound返回第1个大于b[i]的值的指针,当然也可以用lower_bound然后再加1得到与upper_bound相同结果,两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。

离散化后查询的问题(采用的如上代码的离散方式):

1、通过离散后的值查询离散前的值:

  若离散后的值为x,那么对应的离散前的值为sub[x];

2、通过离散前的下标查询离散后的值:

  若离散前的下标为i,那么对应的离散后的值为a[i];

3、通过离散前的值查询离散后的值:

  如果没有相应的保存的话,首先要确定y在sub[]中的位置,或者在b[]中的位置,前者可以使用pos = lower_bound(sub, sub+size, y) - sub。那么pos即为下标,通过第二步再查询就好了。

出处:http://www.cnblogs.com/kevince/p/3893531.html ——By Kevince


按照以上三步可以写出来:

/*
P1955 [NOI2015] 程序自动分析
*/
#include<algorithm>
#include <iostream>
#include <cstring>
#define max 1000011
using namespace std;
int f[max*2];int b[max*2],lsh[max*2]; 

struct node{
    int a,b,e;
}arr[max];

bool cmp(node a,node b){return a.e>b.e;}

void makeSet(int n){
    for(int i=0;i<n;i++) f[i]=i;
}

int find(int x){
    if(x!=f[x]){
        f[x]=find(f[x]);
    }
    return f[x];
}

int main(){
    int t;
    cin>>t;  
    for(int i=0;i<t;i++){
        int n;cin>>n;
        int flag=true;
        //初始化b数组
        memset(b,0,sizeof(b));
        //将n条约束中的2*n个变量存入b数组
        for(int j=0;j<n;j++){
            cin>>arr[j].a>>arr[j].b>>arr[j].e;
            b[j]=arr[j].a;b[j+n]=arr[j].b;
        }
        //对b数组进行升序排序
        sort(b,b+2*n);
        //将记录去重后b数组长度的cnt置零
        int cnt=0;
        //去重
        for(int i=0;i<2*n;i++){
            if(b[i]!=b[i+1]) lsh[cnt++]=b[i];
        }
        //由于我们去重后的变量数量为cnt,所以并查集数组f只需要重置cnt个
        makeSet(cnt);
        //用STL自带的Lower_bound函数返回大于等于第三个参数的数组项的下一个位置的指针
        //减去数组基地址也就是它的位置了
        for(int i=0;i<n;i++){
            arr[i].a=lower_bound(lsh,lsh+cnt,arr[i].a)-lsh;
            arr[i].b=lower_bound(lsh,lsh+cnt,arr[i].b)-lsh;
        }
        sort(arr,arr+n,cmp);
        for(int j=0;j<n;j++){
            int fx=find(arr[j].a);int fy=find(arr[j].b);
            if(arr[j].e) {if(fx!=fy) f[fx]=fy;}
            else{
                if(fx==fy) {
                    flag=false;
                    break;
                }
            }
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

附:lower_bound函数以及upper_bound函数返回的是一个iterator,它指向在区间[first,last)标记的有序序列中可以插入value

unique函数去掉容器中的相邻的重复元素,要求容器中的元素一定要有序,所以一般在使用函数unique的时候,都要对数组或者容器中的元素进行排序,函数不是真正的去除重复,函数返回的是去重后的尾地址,在返回的尾地址之后就是重复元素(将重复的元素放到数组的后方)

erase函数表示删除迭代器所指示的某一位置或者某一区间的元素,返回值是一个迭代器,指向被删除元素后面的元素


lower_bound返回的是不小于value的第一个位置,这个位置就是value插入的位置

upper_bound返回的是大于value的第一个位置

三步走中的去重可以用STL的unique函数,这里直接手动用一个简单的循环进行去重,方便原理的理解。因为unique实际上就是将连续相同的元素进行前移的,没有真正“去重”(删除多余重复元素),真正要删除需要使用erase函数。

但是要注意的是,这样比对,一定要把存放去重元素的b数组在每个问题处理的for循环开头进行置零,否则如果这个问题中最后一个b[i]与前一个问题使用过的元素b[i+1]值相等的话就会出现错误判断。我没置零就调试了好久。

为了更好的理解lower_bound返回的位置,画出图来看:

对于离散化后的数组lsh={2,7,8,9}:

lower_bound(lsh,lsh+cnt,10)//返回0x10
lower_bound(lsh,lsh+cnt,9)//返回0x0C

lsh_lower_bound

如果要用unique函数来获取去重后的尾地址的话,只要把上面的题解中去重部分改成下面这样就行了:

    //将记录去重后b数组长度的cnt置零
    int cnt=0;
    //去重
/*********************手  动*****************/
    // for(int i=0;i<2*n;i++){
    //     if(b[i]!=b[i+1]) lsh[cnt++]=b[i];
    // }
/*********************unique*****************/
    cnt=unique(b,b+2*n)-b;
    cout<<cnt<<endl;
    for(int i=0;i<cnt;i++) lsh[i]=b[i];

当然lsh是为了保持和原来一致才缝合上去的,真正使用的话直接在接下来的步骤都使用b数组就够了。

关于lower_bound函数没有了解更多,但是它是用二分查找实现的。所以后面要继续学习一下二分查找,以便在没有STL函数的情况下也能写出简易版的离散化函数。





© Posted By @shawnt

Comment

称呼:  
邮箱:  
网址: