自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 22:02:21，当前版本为作者最后更新于2019-02-08 22:49:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在博客园食用更佳：https://www.cnblogs.com/PinkRabbit/p/10356919.html

菜菜只能靠写简单字符串哈希维持生活。

题意简述：

题面讲得很清楚了。

题解：

很显然从两边往中间推，能选的就选上这个贪心策略是对的。

如何判断能不能选上，直接字符串哈希吧。

有一个小细节：中间那块要不要选，即ans要不要加1？判一下串长即可。

#include <cstdio>
#include <cstring>

typedef unsigned long long UL;
const int B = 79;

int T, N;
char str[1000005];

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%s", str); N = strlen(str);
		UL s1 = 0, s2 = 0, b = 1;
		int ans = 0;
		for (int i = 0; i < N / 2; ++i) {
			s1 = s1 * B + str[i];
			s2 = s2 + str[N - i - 1] * b;
			b = b * B;
			if (s1 == s2) {
				ans += 2;
				s1 = s2 = 0, b = 1;
			}
		}
		if (N % 2 || s1) ++ans;
		printf("%d\n", ans);
	}
	return 0;
}