题目来源于《挑战程序设计竞赛》，题目涉及的算法只对应相关章节 （不一定是最优解的，思路写的有点简陋）

例题1 Constellations 传送门

题意:
给1个n行m列的大01矩阵 和 t个p行q列的小01矩阵，求这t个小矩阵有多少个在大矩阵中。

思路:
二维hash。算出整个矩阵的所有的P*Q小矩阵的hash值，存在set中，同时求出目标矩阵的hash值，判断该值是否出现即可。若出现，将该hash值从set中删除。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

typedef unsigned int UI;

const int N = 1010;
const int M = 60;

int n, m, t, x, y;
char mp[N][N], s[M][M];

const UI p0 = 1413;
UI p[N * N], hash1[N][N], hash2[N];
multiset<UI>se;

//计算大01矩阵 
void pre(int n, int m, int x, int y)
{
    p[0] = 1;
    for (int i = 1; i <= n * m; i++) p[i] = p[i - 1] * p0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        hash1[i][j] = hash1[i][j - 1] * p[1] + mp[i][j];

    for (int i = y; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        hash2[j] = hash1[j][i] - hash1[j][i - y] * p[y];
        for (int j = 1; j <= n; j++)
        hash2[j] = hash2[j - 1] * p[y] + hash2[j];
        for (int j = x; j <= n; j++)
        se.erase(hash2[j] - hash2[j - x] * p[x * y]);
    }
}

int main()
{
    int cas = 0;
    while (~scanf("%d %d %d %d %d", &n, &m, &t, &x, &y))
    {
        if (n + m + t + x + y == 0) break;
        se.clear();

        for (int i = 1; i <= n; i++)
            scanf("%s", mp[i] + 1);

        for (int T = 1; T <= t; T++)
        {
            for (int i = 1; i <= x; i++)
                scanf("%s", s[i] + 1);

            //计算小01矩阵 
            UI ans = 0;
            for (int i = 1; i<= x; i++)
                for (int j = 1; j <= y; j++)
                ans = ans * p0 + s[i][j];
            se.insert(ans);
        }

        pre(n, m, x, y); 

        int cnt = t - se.size();
        printf("Case %d: %d\n", ++cas, cnt);
    }

    return 0;
}

习题1 Constellations 传送门

题意:
给定3个字符串 s1, s2, s3,试求一个字符串 S
使 s1, s2, s3 都是这个字符串的子串，问这个字符串的最短长度。

思路:
先考虑简单情况，合并两个字符串t1, t2, （t1在t2的左侧）
有以下两种情况：
1. t1包含t2, 则合并结果为t1
2. t1不包含t2, 设 len 为 t1的后缀串 和 t2的前缀串 的最长公共子串T, 则合并时去掉T即可

利用以上方法，枚举3个字符串的全排列，根据顺序依次合并s1, s2, s3, 最后对结果取最小值即可

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;

const int N = 3e5 + 10;

string s[5];
int num[N], tot;
ULL p[N], hash1[N], hash2[N];

void init(int n)
{
    p[0] = 1;
    for (int i = 1; i <= n; i++) p[i] = p[i - 1] * 131;
}

string merge(string a, string b)
{
    a = " " + a; b = " " + b;
    int lena = a.length() - 1, lenb = b.length() - 1;
    for (int i = 1; i <= lena; i++) hash1[i] = hash1[i - 1] * 131 + a[i] - '0';
    for (int i = 1; i <= lenb; i++) hash2[i] = hash2[i - 1] * 131 + b[i] - '0';

    for (int i = 1; i <= lena - lenb + 1; i++)
        if (hash1[i + lenb - 1] - hash1[i - 1] * p[lenb] == hash2[lenb]) 
            return a.substr(1);
    for (int i = max(1, lena - lenb + 2); i <= lena; i++)
    {
        int len = lena - i + 1;
        if (hash1[lena] - hash1[i - 1] * p[len] == hash2[len]) 
            return a.substr(1) + b.substr(len + 1);
    }
    return a.substr(1) + b.substr(1);

}

string merge(string a, string b, string c)
{
    return merge(merge(a, b), c);
}

int main()
{
    init(300005);

    for (int i = 1; i <= 3; i++) cin >> s[i];

    for (int i = 1; i <= 3; i++) num[i] = i;

    int mi = N;
    do{
        string ans = merge(s[num[1]], s[num[2]], s[num[3]]);
        mi = min(mi, (int)ans.length());
    }while (next_permutation(num + 1, num + 4));
    printf("%d\n", mi);

    return 0;
}

习题2 Where’s Wally 传送门

题意:
从w行h列的大图中找出p行p列的小图，旋转翻转皆可，共8种。问大图中共有多少个小图。

思路:
直接对大图不好处理，可采取对小图进行旋转翻转8种操作对应hash值的计算，将其存入set中。
遍历大图，对每个p*p的块，求出对应的hash值，判断是否在set中即可。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e3 + 10;
const int M = 1e2 + 10;

int w, h, p;
char s[N][N], t[N][N];
char ns[N][N], nt[N][N], backup[N][N];

int get_val(char c)
{
    if (c >= 'A' && c <= 'Z') return c - 'A';
    if (c >= 'a' && c <= 'z') return 26 + c - 'a';
    if (c >= '0' && c <= '9') return 52 + c - '0';
    if (c == '+') return 62;
    if (c == '/') return 63;
}

void change_matrix(int n, int m, char (&s)[N][N], char (&e)[N][N])
{
    for (int i = 1; i <= n; i++)
    {
        int tot = 0;
        for (int j = 1; s[i][j]; j++)
        {
            int val = get_val(s[i][j]);
            for (int k = 5; k >= 0; k--)
                if (val & (1 << k)) e[i][++tot] = '1';
                else e[i][++tot] = '0';
        }
    }
}

ULL P[N * N], ha[N][N];
void init(int n)
{
    P[0] = 1;
    for (int i = 1; i <= n; i++) P[i] = P[i - 1] * 131;
}

int main()
{
    init(1000005);

    while (~scanf("%d %d %d", &w, &h, &p))
    {
        if (w + h + p == 0) break;

        for (int i = 1; i <= h; i++) scanf("%s", s[i] + 1);
        for (int i = 1; i <= p; i++) scanf("%s", t[i] + 1);

        change_matrix(h, w, s, ns);
        change_matrix(p, p, t, nt);

        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w; j++)
            ha[i][j] = ha[i][j - 1] * 131 + ns[i][j] - '0';

        set<ULL>se; 

        for (int t = 1; t <= 8; t++)
        {
            if (t == 5)
            {
                memcpy(backup, nt, sizeof nt);
                for (int i = 1; i <= p; i++)
                    for (int j = 1; j <= p; j++)
                    nt[i][p - j + 1] = backup[i][j];
            }

            ULL val = 0;
            for (int i = 1; i <= p; i++)
                for (int j = 1; j <= p; j++)
                val = val * 131 + nt[i][j] - '0';
            se.insert(val);

            memcpy(backup, nt, sizeof nt);
            for (int i = 1; i <= p; i++)
                for (int j = 1; j <= p; j++)
                nt[p - j + 1][i] = backup[i][j];
        }

        int cnt = 0;
        for (int i = 1; i + p - 1 <= h; i++)
            for (int j = 1; j + p - 1 <= w; j++)
            {
                ULL val = 0;
                for (int k = i; k <= i + p - 1; k++)
                    val = val * P[p] + ha[k][j + p - 1] - ha[k][j - 1] * P[p];
                if (se.find(val) != se.end()) cnt++;
            }
        printf("%d\n", cnt);
    }

    return 0;
}

习题3 The Oculus 传送门

题意:
数字可以被唯一分解成为一系列斐波那契数的加和的形式。
现在给定两个这样的 数字a 和 数字b 将他们的乘积 c 也表示成为斐波那契数的加和的形式。
随后将 c 其中非首位的一个1改成0，题目要求哪一位是被修改的一位。

思路:
将题目转换一下，记X=A×B−C，判断X是斐波那契数列的第几项。
对每个斐波那契数都取个模数，可采取自然溢出、双哈希等等来避免冲突
由于杭电OJ，RE报WA，导致我的代码里是三哈希，事实上只要自然溢出即可
求出A×B的值后，枚举答案，判断修改位置

代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ULL;

const int N = 2e6 + 10;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1e9 + 9;

ll f1[N], f2[N];
ULL f3[N];

int t;
int alen, a[N];
int blen, b[N];
int clen, c[N];

set<pair<ll,ll> >se;

int main()
{
    f1[1] = 1; f1[2] = 2;
    f2[1] = 1; f2[2] = 2;
    f3[1] = 1; f3[2] = 2;
    for (int i = 3; i <= 2000005; i++)
    {
        f1[i] = (f1[i - 1] + f1[i - 2]) % mod1;
        f2[i] = (f2[i - 1] + f2[i - 2]) % mod2;
        f3[i] = f3[i - 1] + f3[i - 2];
    }

    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &alen);
        for (int i = 1; i <= alen; i++)
            scanf("%d", &a[i]);
        scanf("%d", &blen);
        for (int i = 1; i <= blen; i++)
            scanf("%d", &b[i]);
        scanf("%d", &clen);
        for (int i = 1; i <= clen; i++)
            scanf("%d", &c[i]);

        ll aval1 = 0, bval1 = 0;
        ll aval2 = 0, bval2 = 0;
        ULL aval3 = 0, bval3 = 0;
        for (int i = 1; i <= alen; i++)
            if (a[i])
            {
                aval1 = (aval1 + f1[i]) % mod1;
                aval2 = (aval2 + f2[i]) % mod2;
                aval3 += f3[i];
            }
        for (int i = 1; i <= blen; i++)
            if (b[i])
            {
                bval1 = (bval1 + f1[i]) % mod1;
                bval2 = (bval2 + f2[i]) % mod2;
                bval3 += f3[i];
            }

        ll res1 = aval1 * bval1 % mod1;
        ll res2 = aval2 * bval2 % mod2;
        ULL res3 = aval3 *bval3;

        ll cval1 = 0, cval2 = 0;
        ULL cval3 = 0;
        for (int i = 1; i <= clen; i++)
            if (c[i])
            {
                cval1 = (cval1 + f1[i]) % mod1;
                cval2 = (cval2 + f2[i]) % mod2;
                cval3 += f3[i];
            }
        int ans = 0;
        for (int i = 1; i <= clen; i++)
        {
            if (c[i]) continue;
            ll tmp1 = (cval1 + f1[i]) % mod1;
            ll tmp2 = (cval2 + f2[i]) % mod2;
            ULL tmp3 = cval3 + f3[i];
            if (tmp1 == res1 && tmp2 == res2 && tmp3 == res3)
            {
                ans = i;
                break;
            }
        }

        printf("%d\n", ans);
    }

    return 0;
}

附
本人不太会写博客，若有错误，敬请指出，有点丑见谅