P9453 [ZSHOI-R1] 有效打击题解

Link_Cut_Y · 2023-07-08 23:27:12 · 题解

抢个题解。

题意应该都知道了，就不放了。

首先分析一下部分分，排序按照本人思考的顺序。

以下将数字称为颜色，将数字段称为颜色段。默认颜色段连续且最长。

Substack 2

最简单的部分分。由于 b 两两相等，所以找到 A 序列中的一个与 b 同色的长度为 k 的颜色段，对答案的贡献就是 C_k^2。

Substack 3

在 sub2 上稍微加了点难度。b 的颜色分为两段，设为 x, y。找到颜色不同的分界点，然后再 A 序列中也找颜色不同的分界点。如果 A 中某个分界点前后的颜色与 x, y 分别相同，那么累计答案。

Substack 1

考虑将 A, B 转化为如下两个序列：第一个序列称为 颜色序列，维护的是 A, B 中不同颜色段的颜色；第二个序列称为 长度序列，维护的是不同颜色段的长度。下文中 C 代表颜色序列，L 代表长度序列。

然后考虑匹配的情况是怎样的。首先考虑放缩倍数为 1 的匹配。显然，就是在 A 中找到一个子串 s，使得 s 串的 C, L 串与 B 串的 C, L 串完全相等。然后考虑放缩倍数为 k 的情况。显然 s 的 C 与 B 完全相等，而 L 为 B 的 k 倍。

实现时需要注意一些细节：对于选取子串 s 的首位不一定与 B 匹配。例子如：

s = \{1, 1, 1, 2, 2, 3, 3, 3\}

B = \{1, 1, 2, 2, 3, 3\}

所以需要从 B 的 2 \sim |C| - 1 段进行匹配，再对首尾分类讨论。

暴力匹配的复杂度 O(|C| ^ 2)。

Substack 4

显然，匹配过程可以利用哈希实现。对于 A, B 的 C, L 串分别建立哈希。然后发现子串的 k 倍放缩可以体现为其哈希的 k 倍放缩。所以匹配时直接判断其颜色哈希是否相等，长度哈希是否满足倍数关系即可。

由于我们实现时对于放缩比例需要化为最简，所以需要求最大公约数。因此时间复杂度 O(n \log n)。

下面是对于 substack 2, 3, 4 的代码实现：

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

using namespace std;

using ULL = unsigned int;
const int N = 5000010;
const ULL P = 1000000007;

int n, m;
int a[N], b[N];
vector<pair<int, int> > A, B;
ULL h1[N], h2[N], h3[N], h4[N], p1[N], p2[N];
long long ans;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; i ++ )
        scanf("%d", &b[i]);
    for (int i = 1; i <= m; ) {
        int j = i;
        for (; j <= m and b[j] == b[i]; j ++ );
        B.push_back({b[i], j - i}); i = j;
    }
    for (int i = 1; i <= n; ) {
        int j = i;
        for (; j <= n and a[j] == a[i]; j ++ );
        A.push_back({a[i], j - i}); i = j;
    }

    if (B.size() == 1) {
        for (auto i : A) {
            if (i.first == B.front().first)
                ans += 1ll * i.second * (i.second + 1) >> 1;
        }
        cout << ans << endl;
        return 0;
    }
    if (B.size() == 2) {
        int p = B.front().first;
        int q = B.back().first;
        int x = B.front().second;
        int y = B.back().second;
        int d = __gcd(x, y);
        x /= d, y /= d;
        for (int i = 0; i < A.size() - 1; i ++ ) {
            if (A[i].first == p and A[i + 1].first == q) {
                if (1ll * A[i].second * y > 1ll * A[i + 1].second * x)
                    ans += A[i + 1].second / y;
                else ans += A[i].second / x;
            }
        }
        cout << ans << endl; return 0;
    }
    else {
        p1[0] = p2[0] = 1;
        for (int i = 1; i <= A.size(); i ++ ) {
            h1[i] = h1[i - 1] * P + A[i - 1].first;
            h2[i] = h2[i - 1] * P + A[i - 1].second;
            p1[i] = p1[i - 1] * P;
        }
        for (int i = 1; i <= B.size(); i ++ ) {
            h3[i] = h3[i - 1] * P + B[i - 1].first;
            h4[i] = h4[i - 1] * P + B[i - 1].second;
            p2[i] = p2[i - 1] * P;
        }
        auto get = [](int l, int r, ULL p[], ULL h[]) -> ULL {
            return ULL(h[r] - h[l - 1] * p[r - l + 1]);
        };
        for (int l = 1; l <= A.size(); l ++ ) {
            int r = l + B.size() - 1;
            if (r > A.size()) break;
            ULL H1 = get(l, r, p1, h1);
            ULL H2 = get(1, B.size(), p2, h3);
            if (H1 != H2) continue;
            ULL H3 = get(l + 1, r - 1, p1, h2);
            ULL H4 = get(2, B.size() - 1, p2, h4);
            ULL p = A[l].second, q = B[1].second;
            ULL d = __gcd(p, q); p /= d, q /= d;
            if (ULL(H3 * q) != ULL(H4 * p)) continue;
            if (1ll * A[l - 1].second * q < 1ll * B.front().second * p) continue;
            if (1ll * A[r - 1].second * q < 1ll * B.back().second * p) continue;
            ans ++ ;
        }
        cout << ans << endl;
        return 0;
    }
    return 0;
}
/*
17 3
1 1 2 2 3 3 3 1 1 2 2 3 1 2 1 2 3
1 2 3
*/

关于此题的严格线性做法

很显然，复杂度瓶颈卡在求解最大公约数上。对于 1 \sim 9 点，可以直接暴力处理出这些连续段的 \gcd。然而对于第十个点，~~需要线性 \gcd 的高级魔法~~。由于赛时没有看到额外奖励，所以没拿到/kk/kk。

严格线性的代码没写，有写的神巨可以私我一下，~~我白嫖挂上~~。

P9453 [ZSHOI-R1] 有效打击 题解