离散hash优化总结

发布于 2018-12-06  112 次阅读


离散优化总结

离散优化是一种常见的高效数据结构,它通过建立数据与存储结构(数组)之间(不一定)一一对应的映射关系来达到对复杂数据的优化。

离散优化最重要的一点是建立映射,对于特殊的线段、点而言,这些映射可以是对一个区间的映射,即将某段线或者某块区域映射到数组里面去,从而在计算时降低时间复杂度。

Hash优化:是对于字符串和数字的一种优化方式。它通过将数据映射到数组内的某个元素从而达到节省空间的效果。

根据hash算法的不同,可能会引起数据的碰撞,即hash(key1)==hash(key2),会使得数据存储出现错误。有两个方法可以解决:

  1. 拉链法,将hash所对密码指向链表头,每次查找元素遍历整串链表,直到找到该元素为止(编程复杂度较高)
  2. 开地址法,当hash所对密码冲突时,将数据存入另外的位置(可以是下一个空位置,也可以是计算出的任意位置),当然如果使用线性开地址法,只要有一个数据碰撞,那么其余所有数据都很有可能进行至少一次碰撞,非常耗费时间。所以我们运用hash算出另一个位置并存储:

while(hashtable[ad]!=0){

    ad+=ad%3+1;//可以是异于主hash算法的另一hash算法

}

 

       通常Hash算法分为两个板块:

  1. 查找元素,hash(key)对应的不一定是目标元素,需要对目标进行搜索,推荐使用开地址法进行搜索
  2. 插入元素,与查找同理,在插入之前必须检查此元素是否已被插入,再用开地址法存入相应的地址

 

Hash可用的构造方法

  1. 直接定址
  2. 取模法
  3. 平均取中值
  4. 随机数
  5. 数字分析法,将最有代表特色的位置作为特征码
  6. 折叠法,将数拆分成几部分并求和
  7. 基数法,将低进制数当作高进制数转化为原进制的数,并进行分析,取特征码(两个进制之间应该是互质的关系)

 

 

 

 

 

 

 

1640: 线段覆盖

时间限制:1 Sec  内存限制: 128 MB
提交:43  解决: 27
[提交][状态][讨论版]

题目描述

X轴上方有若干条平行于X轴的线段,求这些线段能覆盖到的X轴的总长度?

输入

第一行一个数n(n<=1000),表示线段的个数;
接下来n行,每行两个整数ai,bi
(-10^8<=ai,bi<=10^8),代表一个线段的两个端点。

输出

输出覆盖x轴的长度。

样例输入

2
10 12
2 4

样例输出

4

将每个点存入数组进行排序,然后遍历所有线段,将线段所覆盖到的点全部记录,输出结果

#include
#include
#include
using namespace std;
int n,a[1200],b[1200],t[2400],flag[2400],tot,sum;
//flag[i]表示i到i+1之间是否被覆盖 
int find(int s,int e,int aim){
    int mid;
    while(s<=e){
        mid=(s+e)>>1;
        if(t[mid]==aim){
            while(t[mid-1]==t[mid]) mid--;
            return mid;
        }else if(t[mid]>aim)
            e=mid-1;
        else s=mid+1;
    }
}

int main(){
//   freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        if(a[i]>b[i]) swap(a[i],b[i]);
        t[++tot]=a[i]; t[++tot]=b[i];
    }
    sort(t+1,t+1+tot);
    for(int i=tot;i>=2;i--)
        if(t[i]==t[i-1]) flag[i]=-1;
    for(int i=1;i<=n;i++){
        int top=find(1,tot,a[i]),tail=find(1,tot,b[i]);
        for(int j=top;j<=tail-1;j++)
            if(flag[j]!=-1) flag[j]=1;
    }
    for(int i=1;i<=tot-1;i++){
        int nxt=i+1;
        while(flag[nxt]==-1) nxt++;
        if(flag[i]==1) sum+=t[nxt]-t[i];
    }
    printf("%d",sum);
        
    return 0;
}

 

1234: 图形面积

时间限制:0 Sec  内存限制: 128 MB
提交:11  解决: 2
[提交][状态][讨论版]

题目描述

桌面上放了N个矩形,这N个矩形可能有互相覆盖的部分,求它们组成的图形的面积。

输入

输入第一行为一个数N(1≤N≤100),表示矩形的数量。下面N行,每行四个整数,分别表示每个矩形的左下角和右上角的坐标,坐标范围为–10^8到10^8之间的整数。

输出

输出只有一行,一个整数,表示图形的面积。

样例输入

3
1 1 4 3
2 -1 3 2
4 0 5 2

样例输出

10

二维离散优化,将图形在x轴上投影的点找出,并且分析相邻两点间的距离(即图形的宽),以及投影这段线的图形在y轴上的投影(即图形的高),ans+=d*h即可

http://noi.openjudge.cn/ch0305/1551/

Sumsets

描述

给出一个整数集合s,找到集合中最大的d,让等式a+b+c=d成立,

其中,a,b,c,d是集合S中不同的元素。

输入

Several S, each consisting of a line containing an integer 1 <= n<= 1000 indicating the number of elements in S, followed by the elements ofS, one per line. Each element of S is a distinct integer between -536870912 and+536870911 inclusive. The last line of input contains 0.

输出

For each S, a single line containing d, or a single line containing"no solution".

样例输入

5

2

3

5

7

12

5

2

16

64

256

1024

0

样例输出

12

no solution

经过变形可得a+b=d-c,先枚举a+b用hash表存储

再枚举d-c,如果在hash表中有值,且该值对应的a,b异于d,c,那么将此时的d存起来,取最大值

#include
#include
#include
using namespace std;
const int ADD=536870911;
int flag[1000020],in[1020],ha1[1000020],ha2[1000020],data[1000000];
int hashh(int key){
//   key+=ADD;
    int ad=((key%1000000)+10061894)%1000000;
    while(flag[ad]!=0){
        ad+=ad%11+1;
        if(ad>1000000) ad%=1000000;
    }
    return ad;
}

int find(int key){
//   key+=ADD;
    int ad=((key%1000000)+10061894)%1000000;
    while(data[ad]!=key&&flag[ad]!=0){
        ad+=ad%11+1;
        if(ad>1000000) ad%=1000000;
    }
    return flag[ad]==0?-1:ad;
}

int main(){
//   freopen("in.txt","r",stdin);
    int n,maxx;
    while(scanf("%d",&n)!=EOF&&n!=0){
        memset(flag,0,sizeof(flag));
        maxx=-1;
        for(int i=1;i<=n;i++)
            scanf("%d",&in[i]);
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++){
                int ans=hashh(in[i]+in[j]);
                flag[ans]=1,ha1[ans]=in[i],ha2[ans]=in[j],data[ans]=in[i]+in[j];
            }
                
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                int ans=find(in[i]-in[j]);
                if(i==j||ans==-1) continue;
                if(flag[ans]&&ha1[ans]!=in[i]&&ha1[ans]!=in[j]&&ha2[ans]!=in[i]&&ha2[ans]!=in[j])
                    maxx=max(maxx,in[i]);
            }
        if(maxx!=-1) printf("%d\n",maxx);
        else printf("no solution\n");
    }
    
    
    return 0;
}