初学数据结构:字符串哈希 — Luogu P3370

字符串哈希 在 初学数据结构:哈希表的运用 — POJ 3349 Snowflake Snow Snowflakes 一文中,我们曾提及哈希表的概念。那么,什么是字符串哈希呢? 字符串哈希可以理解为一个P进制的数字,其哈希函数如下

H(i)=( H(i-1)*p+a(i) )%mod
其中i表示从1 – i i-1表示从1 – i-1 a(i) 表示这个字符的值(通常取acill码) p p进制数 mod 取模防止爆炸 仔细一看是个什么???进制转换! 经过这个函数基本上每个字符串都会对应一个整数
是不是有点像 康拓展开? 实际上康拓展开也是一种设计的十分好的哈希
可是我们依然会发现,得出来的值还是有一定几率重的,这个状况就叫做哈希碰撞 一个哈希函数产生碰撞的可能性越低,我们就说这个哈希函数设计的越好 那么如何使自己的字符串哈希函数尽可能的变好呢? 如果mod与p是大质数,那么碰撞可能性会很低Qwq 但是这样依然有可能重复,所以我们一般用两个哈希函数,只有两个值相等时才判等

【模板】字符串哈希

明白了概念就来到模板题目把

题目


题意真的是水到了一个境界,所以我们直接上代码吧qwq

代码


#include <cstdio>
#include <cstring>
using namespace std;
int n;
int p=19260817,mod=1000007,temp,temp2,cnt=0;
int p2=99983,mod2=10000007;
// 双哈希
char a[1600];//读入用
long long hash_tmp[1600],hash_tmp2[1600]// 计算哈希;
bool hash[1100000],hash2[11000000];// 哈希表
long long H(){//第一个哈希函数
    int len=strlen(a+1);
    for(int i=1;i<=len;i++){
        hash_tmp[i]=(hash_tmp[i-1]*p+a[i])%mod;
    }
    return hash_tmp[len];
}
long long H2(){//第二个哈希函数
    int len=strlen(a+1);
    for(int i=1;i<=len;i++){
        hash_tmp2[i]=(hash_tmp2[i-1]*p2+a[i])%mod2;
    }
    return hash_tmp2[len];
}
int main(){// 读入
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",a+1);
        temp=H();
        temp2=H2();
        if((!hash[temp])||(!hash2[temp2])){// 有任意一个没有出现过都表示这个字符串没有出现过
            hash[temp]=true;
            hash2[temp2]=true;
            cnt++;
        }
    }
    printf("%d",cnt);
}

END

]]>

Caioj 1220:康托展开和康托展开的逆运算

宽搜剪枝法!智障展开康托展开

何为康托展开


对于一个有n个不同元素的集合{1,2,3,4,…,n}的从小到大排序(从大到小 同理)的全排列
显然它有n!项。如n=4,那么就有4!=4×3×2×1=24项。 那么问题来了,如果我们已经知道他的顺序了,要求他是中剪第几个该怎么办呢? 比如下面这道题:
求4132是第几个排列?
我们来看,它是从小到大排的序,我们就要考虑,比它小的有几个 先看千位:4 小于 4 的数有: 3 2 1 那么总共有几种呢? 这时问题就变成了
有三个数进行全排列,总共有多少种可能?
3!=321=6 又因为他有三个比它小的数 所以有 3*3!=18种排列 那么以此类推,我们再往下一位看,此时问题变成这样
求132是第几个排列?
先看最高位-1 小于 1 的数有0个 所以有0种排列 问题继续转化,变成
求32是第几个排列?
小于最高位: 3 并且没有出现过的数有: 2
将一个数进行全排列,总共有多少种排列?
1!=1 综上所述,小于4132的排序有 18+1=19 种 那么,4132就是第20种 上面这些就是康托展开

逆运算?


看看这个问题
1~4从小到大全排列中,找出第20个排列? 和上面的刚好反过来了,怎么办呢?
还是一样,比它小的有19个 我们先考虑一下它的千位 我们想一下,如果千位上的数是固定的,有多少种排列? 3!=321=6 种 所以每过六种排序,千位上的数就会加1 19/6=3…1 所以千位上应该1-4中从小到大第四个没有出现过的数: 4 继续转化问题,上面那个除法算出来还余 2 呢!
1-3从小到大的全排列中,求第2个排列?
1/2!=0…1 所以千位上应该1-4中从小到大第一个没有出现过的数: 1 带着1继续转化问题:
2-3从小到大的全排列中,求第1个排列?
1/1!=1 所以千位上应该1-4中从小到大第二个没有出现过的数: 3 那么最后一位就是剩下唯一没有用过的数字: 2 也就是说,这个排列是4 1 3 2 是不是和上面那个吻合呢? 自己试几个吧!

代码


康托展开

long long zys(){
    long long ans=0;// ans 储存和
    memset(x,false,sizeof(x));// 清空判重数组
    for(long long i=1;i<=n-1;i++){
        long long tcnt=0;
        for(long long j=1;j<a[i];j++) if(x[j]==false) tcnt++;// 寻找有几个比当前数小的
        ans=ans+tcnt*p[n-i];// 结果相加
        x[a[i]]=true;
    }
    ans++;// 加上自己
    return ans;// 返回
}

康托展开逆运算

void nys(long long cnt){
    cnt--;// cnt 第cnt个排列
    memset(x,true,sizeof(x));
    for(long long i=1;i<=n;i++){
        long long tcnt=cnt/p[n-i];
        cnt-=tcnt*p[n-i];// 将cnt的值变成余数
        long long j;
        for(j=1;j<=n;j++){
            if(x[j]==true){
                if(tcnt==0) break;
                tcnt--;
            }
        }
        x[j]=false;
        a[i]=j;
    }
  // 输出
    for(long long i=1;i<n;i++) printf("%lld ",a[i]);
    printf("%lld\n",a[n]);
}
]]>