哈希hash + 康托展开

桶排序

例题一

任务： 给定n个整数，请按从大到小的顺序输出其中前m大的数。

输入： 每组测试数据有两行； 第一行有两个整数n,m（0<n,m<1000000）； 第二行包含n个各不相同，且都处于区间[0,1000000]的整数。

输出： 对每组测试数据按从大到小的顺序输出前m大的数。

……

可以用桶排序或哈希处理

直接创建多个桶，输入即输出

加强版： 第二行包含n个各不相同，且都处于区间 [-500000, 500000] 的整数

解决: 建立映射关系：x+500000建立桶排序

加强版++(思考)： 如果整数允许相同怎么处理？

解决: 输出的时候找到下标：储存数量

hash哈希：

1. 哈希表（散列表） 冗余四倍以上
2. 哈希函数（散列函数）》》描述对应关系

第一种构造方法：除余法 - 无定式，方法很多 - 最常见的方法：除余法 \[ \text{H(k) = k mod p} \] （p一般选取适当大的素数）

• 由于不能够保证每个元素的关键字与函数值是一一对应的，因此很有可能出现如下情况：
• “对于不同的元素关键字，Hash函数计算出了相同的函数值”，这就是产生了所谓的“冲突”。
• 换句话说，冲突就是Hash函数把不同的元素分在了相同的下标单元。

需要将冲突解决：

方法很多～

常用方法：线性探测再散列技术

即：当 \(h(k)\) 位置已经存储有元素的时候，依次探查 \((h(k)+i) \bmod S\)，\(i=1,2,3\cdots\)，直到找到空的存储单元止。

其中，\(S\) 为数组长度。

特别地，如果将数组扫描一圈仍未发现空单元，则说明哈希表已满，这会带来麻烦，但是，该情况完全可以通过扩大数组范围来避免。

哈希小结：

• Hash函数评价标准：
  • 低冲突率
  • 易于编码
• Hash函数特点：
  • 优点：数据存储和查找效率高（几乎是常数时间）
  • 缺点：消耗较多内存（内存很便宜～）

例题二：方程

给定一方程如下： \[a*x_1^2 + b*x_2^2 + c*x_3^2 + d*x_4^2 = 0\] 其中： \(a\), \(b\), \(c\), \(d\)在整数区间\([-50, 50]\)内取值，并且都不等于0。 求方程在区间 \([-100, 100]\) 内的非零整数解的个数。

方法一：枚举4循环超时

方法二：枚举3，求解x4，

方法三：两次循环hash找存在

参考代码

#include <bits/stdc++.h>
using namespace std;
int pin[101];
int hash[2000003];
int main()
{
    int a,b,c,d;
    int i,j,sum;
    for(i=1;i<101;i++)
        pin[i] = i*i;
    while(scanf("%d%d%d%d", &a,&b,&c,&d)!=EOF)
    {
        if( (a>0 && b>0 && c>0 && d>0 )||
		    (a<0 && b<0 && c<0 && d<0) )
			{printf("0\n"); continue; }
		memset(hash,0,sizeof(hash));
		for(i=1;i<=100;i++)
			for(j=1;j<=100;j++)
				hash[a * pin[i] + b * pin[j] + 1000000]++;
		sum = 0;
		for(i=1;i<=100;i++)
			for(j=1;j<=100;j++)
				sum += hash[-(c * pin[i] + d * pin[j]) + 1000000];
		printf("%d\n",sum);
    }
    return 0;
}

数组大小可以再优化

经验之谈：

两层循环最多只可能产生10000个不同的结果，开200W的数组将会浪费很多初始化的时间．

所以——

    开小数组+处理冲突效果会更好。

解决方案：

#include <bits/stdc++.h>
using namespace std;
#define MAX 50021
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() {
    int a, b, c, d, p, i, j, s, n, t[101];
    for (i = 1; i <= 100; i++)
        t[i] = i * i;
    while (scanf("%d%d%d%d", &a, &b, &c, &d) > 0) {
        if (a > 0 && b > 0 && c > 0 && d > 0 || a < 0 && b < 0 && c < 0 && d < 0) {
            printf("0\n");
            continue;
        }
        memset(f, 0, sizeof(f));
        n = 0;
        for (i = 1; i <= 100; i++)
            for (j = 1; j <= 100; j++) {
                s = a * t[i] + b * t[j];
                p = hash(s); g[p] = s; f[p]++;
            }
        for (i = 1; i <= 100; i++)
            for (j = 1; j <= 100; j++) {
                s = -(c * t[i] + d * t[j]);
                p = hash(s);
                n += f[p];
            }
        printf("%d\n", n * 16);
    }
    return 0;
}

例题三：军队扫把

Flying to the Mars

方法一：离散化

方法二：可行的 map键值对

方法三：hash

杭电ACM－LCY算法培训-例3－参考代码

#include <bits/stdc++.h>
using namespace std;
#define MAXN 7003

inline int ELFhash(char *key)
{
    unsigned long h = 0;
    unsigned long g;
    while( *key )
    {
        h = ( h << 4 ) + *key++;
        g = h & 0xf0000000L;
        if( g ) h ^= g >> 24;
        h &= ~g;
    }
    return h;
}

int hash[MAXN], count[MAXN];
int maxit, n;

inline void hashit(char *str)
{ 
    int k,t;
    while( *str == '0' )  str++;
    k = ELFhash(str);   t = k % MAXN;
    while( hash[t] != k && hash[t] != -1 )
        t = ( t + 10 ) % MAXN;
    if( hash[t] == -1 )  count[t] = 1, hash[t] = k;
    else if( ++count[t] > maxit ) maxit = count[t];
}

int main()
{ 
    char str[100];
    while(scanf("%d",&n)!=EOF) {
        memset(hash,-1,sizeof(hash));
        for(maxit=1; gets(str); n--) {
            gets(str);       hashit(str);
        }
        printf("%d\n",maxit);
    }
}

例题四：八数码

如何转换到下表，最小空间表示状态？

最小空间全排列9！=362880，解决方式康托展开

康托（逆）展开

出现全排列时可用

关于搜索状态的标记：采用对应的整数来表示？

推荐一个新方法——康托展开

康托展开是一个全排列到一个自然数的双射，其实质是计算当前排列在所有由小到大全排列中的顺序，是可逆的。

\[ X = a_n (n-1)! + a_{n-1} (n-2)! + \cdots + a_1 \cdot 0! \]

康托展开代码：

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()
{ int ans = 1;   //12345是第一个，但康拓展开是从0开始编号，所以ans初始化为1
  int len = str.length();
  for(int i = 0; i < len; i++){
    int tmp = 0;
    for(int j = i + 1; j < len; j++){
      if(str[i] > str[j]) tmp++;   //计算有几个比str[i]小的数
    }
    ans += tmp * f[len - i - 1];
  }
  return ans;
}

康托逆展开：

/4! /3! 来展现出有几个比它小

任务：假设初始序列是12345（第一个），请问字典序递增的第107个序列是什么？

因为康托展开的初始序列编号为0，先把107减1；
\(106 / 4! = 4 \cdots 10\) 有4个比它小的所以是5 从（1,2,3,4,5）里选
\(10 / 3! = 1 \cdots 4\) 有1个比它小的所以是2 从（1,2,3,4）里选
\(4 / 2! = 2 \cdots 0\) 有2个比它小的所以是4 从（1,3,4）里选
\(0 / 1! = 0 \cdots 0\) 有0个比它小的所以是1 从（1,3）里选
\(0 / 0! = 0 \cdots 0\) 有0个比它小的所以是3 从（3）里选

所以第107个序列是52413。

逆展开优势：相比于next_permutation()更快，小于log级

逆展开代码：

vector<char> vec;      //存需要排列的字符
void rev_kangtuo(int k) //输出序号为 k 的字符序列
{ int n = vec.size(), 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[t] 就是第 t + 1 大的数
    vec.erase(vec.begin() + t);
  }
  cout << ans << '\n';
}
主程序中vec的初始化：
for(int i = 1; i <= num; i++) vec.push_back(i + '0'); //num是前面计算好的需要位数

小结：需要多种方式

1. Hash的基本思想；（位值）
2. Hash函数的设计；
3. 字符串Hash；
4. 搜索状态的Hash表示；
5. 康托展开与康托逆展开的原理与实现；