ナイロン

冷却心 · 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;
}