题解 P1955 【[NOI2015]程序自动分析】

· · 题解

#P1955 程序自动分析 题解

大家都在用algorithm头文件离散，这时有一个问题：单次映射查询O（logN），还想优化怎么办？O（1）可不可以？！

下面来介绍我的算法：利用Hash表维护映射

   了解哈希的dalao知道如果维护的好，可以实现O（1）查询

我来大概点一点Hash表(散列表）

   它一般由Hash函数与邻接表（链表结构）共同实现，与离散
化思想类似，与离散化不同的是：同样将值域、范围变小，哈希
可能造成两个原始值不同的信息被Hash函数映射为相同的值

   所以我们主要处理“Hash函数”和“冲突情况”
   1. 一般Hash函数的构造需要一个mod数，通常定义为 不大于
n的最大素数 ，这样随机数据可以均匀的映射在构建的链表里。
   2. 同一个链中可能出现多个数，有一种“开散列”的解决案
是，将原始值映射后值相同的归为一类，构成一个链，接在表头
（映射值）之后，每条链的节点可以保存一些数据（我这道题就
是利用开散列），之后依次遍历即可，因为依赖于Hash函数，构
造的越好越接近O（1）

下面上代码：

#define Max 100010
#define mod 99991 
struct node{
    int real,map;//真实值，映射值（此映射非彼映射，我们需要map参与并查集运算，real%mod才是hash映射）
}
vector <node> hash[Max]; 
int tot;//即结构体中的map映射，后面运算你会发现我们只考虑一个数出现的时间++tot，而不需要依靠大小相对映射，这里没必要
int map(int i,int j,bool k)
{
    int x,y,ok=1;
    int a = i % mod, b = j % mod;
  以下即映射查询的过程，看不懂发评论
    if(!hash[a].empty()){
        for(int l = 0; l < hash[a].size(); l++)
            if(i==hash[a][l].real) x = hash[a][l].map,ok = 0;
        if(ok) hash[a].push_back((node){i,++tot}),x = tot;
    }
    else hash[a].push_back((node){i,++tot}),x = tot;
    ok = 1;
    if(!hash[b].empty()){
        for(int l = 0; l < hash[b].size(); l++)
            if(j==hash[b][l].real) y = hash[b][l].map,ok = 0;
        if(ok) hash[b].push_back((node){j,++tot}),y = tot;
    }
    else hash[b].push_back((node){j,++tot}),y = tot;
    return ask(x,y,k); 
}

与其他题解区别主要就是离散方式

下面AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector> 
#define Max 100010
#define mod 99991 

using namespace std;

int fa[2*Max],d[2*Max];
struct node{
    int real,map;
}un[Max];
vector <node> hash[Max]; 
int tot,cnt;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int ask(int i,int j,bool k)
{
    if(find(i)==find(j)) return 1;
    else if(k){
        fa[find(j)] = find(i);
        return 0;
    }
    return 0;
}
int map(int i,int j,bool k)
{
    int x,y,ok=1;
    int a = i % mod, b = j % mod;
    if(!hash[a].empty()){
        for(int l = 0; l < hash[a].size(); l++)
            if(i==hash[a][l].real) x = hash[a][l].map,ok = 0;
        if(ok) hash[a].push_back((node){i,++tot}),x = tot;
    }
    else hash[a].push_back((node){i,++tot}),x = tot;
    ok = 1;
    if(!hash[b].empty()){
        for(int l = 0; l < hash[b].size(); l++)
            if(j==hash[b][l].real) y = hash[b][l].map,ok = 0;
        if(ok) hash[b].push_back((node){j,++tot}),y = tot;
    }
    else hash[b].push_back((node){j,++tot}),y = tot;
    return ask(x,y,k); 
}
int main()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        for(int i = 1; i <= 200010; i++)
            fa[i] = i;
        for(int i = 0; i < 100000; i++)
            hash[i].clear();
        memset(d,0,sizeof(d));
        memset(un,0,sizeof(un));
        //以上每步的初始化不能丢
        cnt = tot = 0;
        int num,now = 1;
        cin >> num;
        for(int i = 1; i <= num; i++)
        {
            int x,y,z;
            cin >> x >> y >> z;
            if(z) map(x,y,1);
            else un[++cnt].real = x, un[cnt].map = y;   
        }
        for(int i = 1; i <= cnt; i++)
            if(map(un[i].real,un[i].map,0)){
                now = 0;
                cout << "NO" <<endl;
                break;
            }
        if(now) cout << "YES" << endl;
    }
    return 0;
}
 对比其他题解AC代码：3.13s 27.50MB
                 我：1.45s 8.52MB
           加入读优：334ms！！！

下面还需注意初始化问题：

我因为for(int i = 1; i <= 200010; i++) fa[i] = i;

写成for(int i = 1; i <= n; i++) fa[i] = i; WA了4个点

写成for(int i = 1; i <= 100000; i++) fa[i] = i; WA了第二个点

     大家有意可以翻我的记录（公开的）

本蒟蒻仅浅懂一些数据结构dalao勿喷