题解：P6080 [USACO05DEC] Cow Patterns G

· · 题解

思路

考虑 hash，合法条件转化为相等个数相同与相对大小相同，拆位，将同一大小的位合并，直接枚举不同大小的具体值，找出所有合法状态，用 dfs 实现。将序列用 hash 维护，从前往后扫一遍长度为 k 的区间判断是否在合法状态集合中即可。

code

#include <bits/stdc++.h>

#define ULL unsigned long long
#define PUU pair<ULL, ULL>
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int N = 1e5 + 10;
const int M = 25010;
const ULL B1 = 13331;
const ULL B2 = 131;
const int K = 5500000;

int n, k, s;
int a[N], b[M];
pii d[M];
int tot, num;
ULL c1[M], c2[M], b1[M], b2[M];
PUU Hash[K];

void dfs(ULL u, int cnt, ULL ha1, ULL ha2)
{
    if (cnt == tot) 
    {
        Hash[ ++ num] = mp(ha1, ha2);
        return;
    }
    if (u == s) return;
    dfs(u + 1, cnt, ha1, ha2);
    dfs(u + 1, cnt + 1, ha1 + c1[cnt + 1] * (u + 1), ha2 + c2[cnt + 1] * (u + 1));
    return;
}

int ans, res[N];

bool find(PUU x)
{
    int p = lower_bound(Hash + 1, Hash + num + 1, x) - Hash;
    return Hash[p] == x;
}

int main()
{
    b1[0] = b2[0] = 1;
    for (int i = 1; i <= 25000; ++ i) b1[i] = b1[i - 1] * B1, b2[i] = b2[i - 1] * B2;
    scanf("%d%d%d", &n, &k, &s);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    for (int i = 1; i <= k; ++ i) scanf("%d", &b[i]), d[i] = mp(b[i], k - i);
    sort(d + 1, d + k + 1);
    for (int i = 1; i <= k; ++ i) 
    {
        // cout << d[i].fi << " " << d[i].se << endl;
        if (d[i].fi != d[i - 1].fi) ++ tot;
        c1[tot] += b1[d[i].se];
        c2[tot] += b2[d[i].se];
    }
    dfs(0, 0, 0, 0);
    sort(Hash + 1, Hash + num + 1);
    ULL s1 = 0, s2 = 0;
    for (int i = 1; i <= n; ++ i) 
    {
        s1 = s1 * B1 + a[i];
        s2 = s2 * B2 + a[i];
        if (i > k) 
        {
            s1 -= a[i - k] * b1[k];
            s2 -= a[i - k] * b2[k];
        }
        if (i >= k) 
        {
            if (find(mp(s1, s2)))
                res[ ++ ans] = i - k + 1;
        }
    }
    printf("%d\n", ans);
    for (int i = 1; i <= ans; ++ i) printf("%d\n", res[i]);
    return 0;
}