题解 P1154 【奶牛分厩】

Jelly_Goat · 2019-08-14 07:41:58 · 题解

我觉得这个题可以改一个名字或者题面2333

题目大意：
寻找一个最好的hash因子k
使得每一个S_i都有唯一对应的hash值
且n\leq k

前置知识：
若a\equiv b\pmod k
则k|abs(a-b)

假设k * i = abs(a - b)
对于一个k，枚举另外一个因子i，
如果不存在一个i使得k * i = abs(a - b)
那么a\equiv b \pmod k就会被推翻

因此我们只需要找到一个k
使得任何一个i(k * i\leq 1000000)都不满足

那么就使得任何一个S_i\pmod k的值是不相等的

这应该好理解。
那么我们现在先用一个黑科技：bitset
降低我们存放差值的空间大小

bitset<1000001> vst;

（关于bitset的用法去baidu或者使用bool vst[1000001];）
然后直接上手做：

1. 读入数据
2. 枚举所有的差值然后vst[差值]=1
3. 枚举 k 从 n 到 1000001
   对于每一个 k 枚举一个 i 从 1 到 i * k = 1000001
   若使得不存在 i 让 vst[i × k] = 1
   退出循环输出k

说完了，你会做了吗？
上代码：

#include <iostream>
#include <cstdio>
#include <bitset>

using namespace std;
const int maxn = 1000000;
bitset<1000001> vst;
int s[5086], n;
// 绝对值
inline int abs(int num) { return num < 0 ? -num : num; }
// 寻找一个适合的k
inline bool judge(int k)
{
    for (int i = 1; i * k <= maxn; i++)
    {
        if (vst[i * k]) return false;
    }
    return true;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&s[i]);
    }
    // 枚举差值
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            vst[abs(s[i] - s[j])]=1;
    // 枚举 k from n to maxn
    // 一个合适的k使得任何minus都不是k的倍数即可
    int k = n;
    while (!judge(k)) k++; 
    printf("%d\n", k);
    return 0;
}

另外：吐槽一下为什么几乎所有的dalao都把i那层循环放进k那层循环了