头图
Source：qoj
pkusc 2024 Day1
T1 (回文路径)
原中原：P4324
给定 \(2\times n\) 网格，每个格子上有一个字符，考虑一条只能向下和向右走的路径，如果路径上每个字符连成的字符串是回文串，称这条路径是好的，求最长好路径。
\(1\le n\le 10^5\)
$\texttt{solution}$
枚举回文中心在啥位置，不妨设在第一行。二分出在第一行能走到的最长距离（容易证明这样贪心是对的），然后往下走，再二分在第二行能移动到最长距离。
判断回文用哈希即可，复杂度 \(O(n)\)。