Hash表

概念：
Hash表又称散列表，是一种通过建立一种一一对应的键值关系来便于查找的数据结构，其键是由一个Hash函数（即散列函数）得到，在查找时时间复杂度为$O(1)$

冲突情况：
在储存地址时，可能会有一个键指向两个值的情况

冲突解决：(线性探测再散列技术)
当$h(k)$位置已经存储有元素时，就依次探查$(h(k)+i)$mod$ S,i=1,2,3,…，指导找到空的存储单元为止。
S为数组的长度
（如果扫描一圈未发现空单元，说明哈希表已满，可以扩大数组范围）

题目特点：
1. 数据量大（$1e7$）
2. 数据在一定的范围

基本操作：
1. Hash表初始化
2. 哈希函数运算
3. 插入元素（包含冲突解决）

主要应用：
1. 查找元素是都属于集合
2. 搜索中的状态表示

HDU 1425 sort (排序)

【问题描述】
给你n个整数，请按从大到小的顺序输出其中前m大的数。
【输入形式】
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
【输出形式】
对每组测试数据按从大到小的顺序输出前m大的数。

/*
in 
5 3
3 -35 92 213 -644

out 
213 92 3
*/
#include<bits/stdc++.h>
using namespace std;
int a[10000005];//数组不可以存负数，故数组开大一倍
int main(){
    int n,m;
    while(cin >> n >>m){
        int q;
        for(int i=1;i<=n;i++){
            cin >> q;
            q+=500000;
            a[q]++;//桶排序
        }
        int cnt = 0;
        for(int i=10000000;i>0;i--){
            if(cnt==m) break;
            if(a[i]!=0) {
                a[i]--;
                cout<<i-500000<<" ";
                cnt++;
            }
        }
    }
    return 0;
} 

HDU-解方程

【问题描述】
给定一方程如下:
$a$$x^2$ + $b$$x^2$ + $c$$x^2$ + $d$$x^2$=0

其中：
$a$, $b$, $c$, $d$在整数区间$[-50,50]$内取值，并且都不等于0.

求方程在区间$[-100,100]$内的非零整数解的个数。
【输入形式】
输入包含多组测试数据。

法一：桶排序
/*
巧妙:
1) 把ab 和cd组成等式放在两边
2) x的取值范围左右正负对称，
    且原式是个偶函数，算一半，最后结果*16就好了 
in 
1 2 3 -4
1 1 1 1


out 
39088
0

*/
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;
int p[105];
int hash_[2000005];
int main(){
    for(int i=1;i<=100;i++){
            p[i] = i*i;
        }
    while(cin >> a>> b >>c >>d){
        if((a<0&&b<0&&c<0&&d<0)|| (a>0&&b>0&&c>0&&d>0)){
            cout<<"0"<<endl;
            continue;
        }
        memset(hash_,0,sizeof(hash_));
        for(int i=1;i<=100;i++){
            for(int j=1;j<=100;j++)
                hash_[a*p[i]+b*p[j]+1000000]++;
        }
        int sum =0;
        for(int i=1;i<=100;i++){
            for(int j=1;j<=100;j++){
                sum+=hash_[-(c*p[i]+d*p[j])+1000000];
            }
        }
        cout<<sum*16<<endl;
    }
} 

-------------------------------------------------------------------------------

法二：开小数组+处理冲突
/*
in 
1 2 3 -4
1 1 1 1

out 
39088
0

*/
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,x,y;
const int MAX = 50021;
int p[105];
int f[MAX], g[MAX];
int hash_(int k){
    int t = k%MAX;
    if(t<0) t+=MAX;
    while(f[t]!=0 && g[t]!=k) 
        t = (t+1)%MAX;
    return t;
}

int main(){
    for(int i=1;i<=100;i++){
            p[i] = i*i;
        }
    while(cin >> a>> b >>c >>d){
        if((a<0&&b<0&&c<0&&d<0)|| (a>0&&b>0&&c>0&&d>0)){
            cout<<"0"<<endl;
            continue;
        }
        memset(f,0,sizeof(f));
        for(int i=1;i<=100;i++){
            for(int j=1;j<=100;j++){
                x = a*p[i]+b*p[j];
                y = hash_(x);g[y] = x;f[y]++; 
            }

        }
        int sum =0;
        for(int i=1;i<=100;i++){
            for(int j=1;j<=100;j++){
                x = -(c*p[i]+d*p[j]);
                y = hash_(x);
                sum+=f[y]; 
            }
        }
        cout<<sum*16<<endl;
    }
} 

补充一下：康托展开

全排列到一个自然数的双射，其实质计算当前排列是从小到大全排列的顺序

！康拓展开

int f[20];
string str;

void jie_cheng(int n){
    f[0] = f[1] = 1;
    for(int i=2;i<=n;i++) f[i] = f[i-1]*i;
}

int kangtuo(){//12345是第一个
    int ans = 1;//康拓展开是从 0 开始编号，所以ans初始化为1 
    int len = str.length();
    for(int i = 0;i<len;i++){
        int tem=0;
        for(in j =i+1;j<=n;j++){
            if(str[j]<str[i]) tep++;
        }
        ans+=tep*f[len-1];
    }
    return ans;
}

P5367 【模板】康托展开

    int ans=0;
    for(int i=1;i<=n;i++){
      int sum=0;
      for(int j=i;j<=n;j++)
        if(a[i]<a[j])sum++;//统计sum
     ans=(ans+sum*jc[n-i])%998244353;//计算ans                       
    }
    printf("%d",ans+1);//别忘了+1

这么写的，你是不是又想$TLE$了？？？
好吧，以上代码没问题，
但是这个题的数据很友（du）善（liu），$O(n^2)$的复杂度是跑不过的......那要多少呢？
$O(logn)$差不多，带$logn$的就那几样数据结构，
经过精挑细选，我们就用常数小，操作方便，代码又好写的树状数组吧！
能优化的，无非就是 统计$sum$的那一步

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll tree[1000005];//树状数组
int n;
  //树状数组的“老三件”：lowbit，修改，求和
int lowbit(int x){
    return x&-x;
}
void update(int x,int y){
    while(x<=n){
        tree[x]+=y;
        x+=lowbit(x);   
    }
}
ll query(int x){
    ll sum=0;
    while(x){
        sum+=tree[x];
        x-=lowbit(x);   
    }
    return sum;
}
const ll mod=998244353;
ll jc[1000005]={1,1};
int a[1000005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        jc[i]=(jc[i-1]*i)%mod;
        update(i,1);
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ans=(ans+((query(a[i])-1)*jc[n-i])%mod)%mod;
        update(a[i],-1);
    }
    printf("%lld",ans+1);
   return 0;
}

//康托逆展开！
代码如下：
vector<char> vec;

void rev_kangtuo(int k){//求12345的第127个序列 
    int n = vec.size();
    int len = 0;
    string ans="";
    k--; //从 0 开始计数 
    for(int i =1;i<=n;i++){
        int t = k/f[n-i];//第 i 位需要t+1大的数字
        k%=f[n-i];
        ans+=vec[t];
        vec.erase(vec.begin()+t);//删前当前已经用过的元素 ！！
} 
    cout<<ans<<endl;

}

//主函数：
for(int i =1;i<=num;i++) vec.push_back(i+'0'); 

字符串哈希

字符串哈希实质上就是把每个不同的字符串转成不同的整数，要处理某一个前缀的hash值，要把字符串当成一个P进制的数，然后每一位的字母的ASCII值就代表这一位的数字

$(P取131，Q取2^{64})$ $Q$直接用unsigned long long存储

$hash[0]=0$
$hash[1]=hash[0]∗p+str[1]=str[1]$
$hash[2]=hash[1]∗p+str[2]=str[1]∗p^1+str[2]$
$hash[3]=hash[2]∗p+str[3]=str[1]∗p^2+str[2]∗p^1+str[3]$
$hash[4]=hash[3]∗p+str[4]=str[1]∗p^3+str[2]∗p^2+str[3]∗p^1+str[4]$
故可以得到:
$$hash[i] = (hash[i - 1] * P + str[i]) mod Q$$
则字符串 $str$[3]到 $s[4]$的$hash$是$s[3]∗p1+s[4]s[3]∗p1+s[4]$
得到公式：求字符串 $str[L]$ 到 $str[R]$的哈希是 $hash[R]−hash[L−1]$
即某一区间的哈希值： $$hash[R]−hash[L−1]∗p^{R−L+1}$$

Acwing 841. 字符串哈希

#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+10,maxn2=31*maxn;
const int P= 131;
ull h[maxn],p[maxn];
char s[maxn];
int n,m;
void init()
{
    for(int i=1;i<=n;i++)
    {
        p[i]=p[i-1]*P;//计算p为几次幂
        h[i]=h[i-1]*P+s[i];//到当前字符串哈希值
    }
}
ull check(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    p[0]=1;    //注意！
    scanf("%d%d%s",&n,&m,s+1);
    init();
    while(m--)
    {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(check(l1,r1)==check(l2,r2))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
}