题解：P12774 [POI 2018/2019 R1] 一对项链 Pair of necklaces

sunkuangzheng · 2025-06-21 17:11:25 · 题解

将价值对 2 取模后转化为 01 串问题，不失一般性地假设 n \ge m。

考虑枚举起点 l，尝试用 s[l,l+m-1] 匹配 t。如果奇偶性相同则匹配成功，否则考虑进行下面分讨：

• 策略一：从两个串开头一直同时删去字符，如果某次删去了两个不同的字符则成功。这本质是在找两串的 LCP，可以 Z 函数预处理。
• 策略二：从一个串开头和另一个串结尾删字符，直到 s 的开头和 t 的开头不同，删去这个字符。这本质上是在求字符串开头结尾连续段长度的 \min（如果 LCP 更短那么在上面已经讨论过了）。

注意每个字符串都可以任意翻转，需要枚举 4 种不同的翻转情况，跑 4 遍 Z 函数和预处理 4 遍连续段长度，每次询问对 8 个值取 \min 即可。

将这段文字题解喂给 chatgpt 并反复调教即可获得 AC 代码。

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

vi Zfunc(const vi &s) {
    int n = s.size();
    vi Z(n);
    int l = 0, r = 0;
    Z[0] = n;
    for (int i = 1; i < n; i++) {
        if (i <= r) Z[i] = min(r - i + 1, Z[i - l]);
        else Z[i] = 0;
        while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]]) Z[i]++;
        if (i + Z[i] - 1 > r) {
            l = i; r = i + Z[i] - 1;
        }
    }
    return Z;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        vector<int> A(n), B(m);
        for (int i = 0; i < n; i++) { cin >> A[i]; A[i] &= 1; }
        for (int j = 0; j < m; j++) { cin >> B[j]; B[j] &= 1; }
        if (n < m) {
            swap(n, m);
            swap(A, B);
        }

        vector<int> pxA(n+1, 0), pxB(m+1, 0);
        for (int i = 0; i < n; i++) pxA[i+1] = pxA[i] ^ A[i];
        for (int j = 0; j < m; j++) pxB[j+1] = pxB[j] ^ B[j];

        vector<int> runR_A(n), runL_A(n);
        runR_A[n-1] = 1;
        for (int i = n-2; i >= 0; --i) {
            runR_A[i] = (A[i] == A[i+1] ? runR_A[i+1] + 1 : 1);
        }
        runL_A[0] = 1;
        for (int i = 1; i < n; ++i) {
            runL_A[i] = (A[i] == A[i-1] ? runL_A[i-1] + 1 : 1);
        }
        vector<int> runR_B(m), runL_B(m);
        runR_B[m-1] = 1;
        for (int j = m-2; j >= 0; --j) {
            runR_B[j] = (B[j] == B[j+1] ? runR_B[j+1] + 1 : 1);
        }
        runL_B[0] = 1;
        for (int j = 1; j < m; ++j) {
            runL_B[j] = (B[j] == B[j-1] ? runL_B[j-1] + 1 : 1);
        }

        vi S1; S1.reserve(m + 1 + n);
        for (int x : B) S1.push_back(x);
        S1.push_back(2);
        for (int x : A) S1.push_back(x);
        vi Z1 = Zfunc(S1);

        vi Ar(n), Br(m);
        for (int i = 0; i < n; i++) Ar[i] = A[n-1-i];
        for (int j = 0; j < m; j++) Br[j] = B[m-1-j];
        vi S2; S2.reserve(m + 1 + n);
        for (int x : Br) S2.push_back(x);
        S2.push_back(2);
        for (int x : Ar) S2.push_back(x);
        vi Z2 = Zfunc(S2);

        vi S3; S3.reserve(m + 1 + n);
        for (int x : Br) S3.push_back(x);
        S3.push_back(2);
        for (int x : A) S3.push_back(x);
        vi Z3 = Zfunc(S3);

        vi S4; S4.reserve(m + 1 + n);
        for (int x : B) S4.push_back(x);
        S4.push_back(2);
        for (int x : Ar) S4.push_back(x);
        vi Z4 = Zfunc(S4);

        int best = 0;
        for (int l = 0; l + m <= n; l++) {

            if ((pxA[l+m] ^ pxA[l]) == pxB[m]) {
                best = m;
                break;
            }
            int rev_pos = n - (l + m);
            int a = Z1[m + 1 + l];
            int b = Z2[m + 1 + rev_pos];
            int c = Z3[m + 1 + l];
            int d = Z4[m + 1 + rev_pos];

            int x1 = runR_A[l];         
            int x2 = runL_A[l + m - 1]; 
            int x3 = runR_B[0];         
            int x4 = runL_B[m - 1];     
            int x = min({a, b, c, d, x1, x2, x3, x4});
            best = max(best, m - x - 1);
        }
        cout << best << "\n";
    }
    return 0;
}