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

由于我的 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

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

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

代码：

CPP

#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;
}

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

文章操作

相关推荐

评论

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