自动搬运

查看原文

来自洛谷，原作者为

	冷却心 111

搬运于2025-08-24 23:13:40，当前版本为作者最后更新于2025-06-01 15:45:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

糖题不会做 /ll。

最长回文子串首先能想到 Manacher，于是你把 Manacher 板子复制过来然后把判断回文的条件变成询问，然后喜提 13pts。原因是 Manacher 判断回文次数的上界在 $2n$ 左右，并且奇偶长度都做一遍就是 $4n$ 直接倒闭。

事实上这题不需要求出每个回文中心的最长回文半径，只需要判断是否能在当前答案的基础上再次扩展，而这样做询问就至多 $n$ 次了。询问次数上界的证明：

以奇数长度为例，设最终答案为 $d$，那么回文中心大于 $n-d$ 由于长度不够会直接跳过，对于这前面的 $n-d$ 个位置，在每个位置固定询问一次非法的基础上又询问了 $d$ 次回文串使得答案增加 $d$，一共 $n-d+d=n$ 次。当然实际情况会小于等于这个上界 $n$。

然后做完了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

bool query(int a, int b) {
	cout << "? " << a << " " << b << "\n";
	int x; cin >> x; return x;
}

int main() {
	int n; cin >> n; int d1 = 0, d2 = 0;
	for (int i = 1; i <= n; i ++) {
		while (i + d1 + 1 <= n && i - d1 - 1 >= 1 && query(i - d1 - 1, i + d1 + 1)) ++ d1;
		while (i + d2 + 1 <= n && i - d2 >= 1 && query(i - d2, i + d2 + 1)) ++ d2;
	}
	cout << "! " << max(d1 * 2 + 1, d2 * 2) << "\n";
	return 0;
}