牛客2020寒假训练营5-H

Hash

题意
这里有一个hash函数
const int LEN = 6;
int mod;
int Hash(char str[])
{
int res = 0;
for (int i = 0; i < LEN; i++)
{
res = (res * 26 + str[i] - ‘a’) % mod;
}
return res;
}
现给定一个长度为6的仅由小写字母构成的字符串s和模数
mod，请找到字典序最小且大于s的一个长度为6的仅由小写字母构成的字符串s′使得其hash值和s的hash相等。

题解
观察给的哈希函数可以轻松看出，这个哈希函数就仅仅是把一个只由小写字符组成的字符串当成了一个26进制的数，不取模的情况下，任意小写字符串和自然数是一一对应的。因此，只要把给的字符串转换成对应的26进制整数，加上模数后转换回字符串，一定可以得到一个最小字典序大于原串的字符串。只要这个新字符串长度为6即是满足要求的字符串

hash本质
用str[1]×num^(k-1) + str[2]×num^(k-2)+…..str[k] %mod 表示字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll Hash(char s[]){
    ll res=0;
    for(int i=0;i<6;i++){
        res=(res*26+s[i]-'a');
    }
    return res;
}
char s[10];
int main(){
    int mod;
    while(scanf("%s %d",s,&mod)!=EOF){
        ll res=Hash(s)+mod;
        for(int i=5;i>=0;i--){
            s[i]=(res%26+'a');
            res/=26;
        }
        //cout<<1;
        if(res!=1)cout<<s<<endl;
        else cout<<-1<<endl;
    }
}