题解：P12877 [蓝桥杯 2025 国 Python A] 心意

Perfect_Youth · 2025-08-23 11:43:13 · 题解

由于我的 KMP 算法学的很差，所以这里提供一个比较简单易懂的思路，其实这个人模拟赛没切这个题。

由题意知道 x=\frac{\sum b_i-\sum a_i}{n}，知道这个后就可以做题了。

先考虑如果 x 不为整数，很显然输出 -1。

如果 x 为整数，那么我们可以使所有的 a_i-x。这样子可以把问题变成对于所有的 i 有 a_i=b_i。

现在就可以设一个 k，k 一开始等于 0。这样我们可以判断如果 b_s\ne a_p，一直使 k 加 1，直到匹配，匹配了就直接暴力判断是否满足所有的 a_i=b_i 就可以了，如果满足直接输出对应的 k 即可，k 如果大于 n 还没找到，就输出 -1。其中 s 为 [1,n] 的任意一个值，p=(k+s-1)\mod n+1。

因为 s 是任意一个值，所有我们每次都取一个随机值即可。为什么呢？因为固定值容易被卡超时，而随机值基本不会。

这个代码跑的挺快，目前最优解。

代码：

#include <bits/stdc++.h>

using namespace std;

inline
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ '0');
        ch = getchar();
    }
    return x * f;
}

const int N = 5e5 + 7;

int n, a[N], b[N], k, x;

mt19937 rd(time(0));

inline
bool pd(int x) {
    for (int i = x + 1; i <= n; i++) {
        if (a[i] != b[i - x]) return 0;
    }
    for (int i = 1; i <= x; i++) {
        if (a[i] != b[n - x + i]) return 0;
    }
    return 1;
}

inline
int xb(int x, int y) {
    return (x + y - 1) % n + 1;
}

long long ans;

bool flag;

int main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read(), ans -= a[i];
    for (int i = 1; i <= n; i++) b[i] = read(), ans += b[i];
    if (ans % n != 0) puts("-1"), exit(0);
    ans /= n;
    for (int i = 1; i <= n; i++) b[i] -= ans;
    while (k <= n) {
        x = rd() % n + 1;
        while (b[x] != a[xb(k, x)] && k <= n) k++;
        if (pd(k)) {
            printf ("%d\n", k);
            return 0;
        }
    }
    puts("-1");
    return 0;
}