HDU 6046 - hash | 2017 Multi-University Training Contest 2

思路来自题解和一些博客

最麻烦的是样例没啥用- -

/*

HDU 6046 - hash [ hash,鸽巢 ]  |  2017 Multi-University Training Contest 2

题意：

	给出一个1e3*1e3的矩阵以及 一个 生成1e6*1e6的矩阵的随机函数

	在1e6*1e6的矩阵中找到1e3*1e3的矩阵的位置

分析：

	将1e3*1e3的矩阵每一个位置压入哈希表中，哈希值为其与之后63位所组成64位的值（不满64位就不压入）

	由于 2^64 远大于 1e12 故可认为哈希值相同的是同一个位置

	枚举大矩阵中的位置，若能在哈希表中找到这个位置的哈希值，则小矩阵头部的相对位置可以确定

	但不需要枚举大矩阵中的每个位置，可以每隔1000行，隔900列枚举一个位置

	这样根据鸽巢原理，枚举的这些位置至少有一个被小矩阵覆盖

	选隔900列而不是1000列的原因是 小矩阵每行最右端63个点没被压入哈希表，所以哈希表中的矩阵是 1000 * (1000-63)的

*/

#include <bits/stdc++.h>

using namespace std;

#define LL unsigned long long

const int N = 1e3+5;

const int L = 1000;

const int ZIP = 64;

inline unsigned sfr(unsigned h, unsigned x) {

  return h >> x;

}

int f(LL i, LL j) {

    LL w = i * 1000000ll + j;

    int h = 0;

    for (int k = 0; k < 5; ++k) {

        h += (int) ((w >> (8 * k)) & 255);

        h += (h << 10);

        h ^= sfr(h, 6);

    }

    h += h << 3;

    h ^= sfr(h, 11);

    h += h << 15;

    return sfr(h, 27) & 1;

}

namespace HashMap{

    const int MOD = 1313131;

    struct Node {

        LL pos, val;

        int nxt;

    }node[N*N];

    int head[MOD], tot;

    void init() {

        memset(head, 0, sizeof(head));

        tot = 0;

    }

    void insert(LL v, LL p) {

        int t = v % MOD; tot++;

        node[tot].pos = p;

        node[tot].val = v;

        node[tot].nxt = head[t];

        head[t] = tot;

    }

    LL find(LL v) {

        for (int i = head[v%MOD]; i; i = node[i].nxt)

            if (node[i].val == v) return node[i].pos;

        return 0;

    }

}

char s[N];

LL hs[N];

int main()

{

    int t; scanf("%d", &t);

    for (int tt = 1; tt <= t; tt++)

    {

        HashMap::init();

        for (int i = 1; i <= L; i++)

        {

            scanf("%s", s+1);

            hs[L+1] = 0;

            for (int j = L; j >= 1; j--)

                hs[j] = hs[j+1]<<1|(s[j]-'0');

            for (int j = 1; j <= L-ZIP+1; j++)

                HashMap::insert(hs[j], i*1024+j);

        }

        LL ans = 0; int x, y;

        for (int i = 1; i <= 1e6 && (!ans); i += 1000)

            for (int j = 1; j <= 1e6 && (!ans); j += 900)

            {

                if (j+ZIP-1 > 1e6) continue;

                LL val = 0;

                for (int k = ZIP-1; k >= 0; k--)

                    val = val<<1|(f(i,j+k));

                ans = HashMap::find(val);

                if (ans != 0) x = i, y = j;

            }

        int px = x - ans / 1024 + 1, py = y - ans % 1024 + 1;

        printf("Case #%d :%d %d\n", tt, px, py);

    }

}