题解 P1955 【[NOI2015]程序自动分析】
Virvan
2019-08-10 16:43:21
# **#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代码：
```cpp
#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勿喷~~