前几晚 BC 的第二题，官方给出的题解是：
然后我结合昨天刚看的 Manacher 算法试着写了下，发现 pre、suf 数组挺难构造的，调试了好久，然后就对中间进行枚举了，复杂度应该是 O(n2) 吧，我第一次交时超时了，以为真的要用什么暴力压位，可是我还不会啊，然后作了一些少许的优化提交本想再 T 一次的，没想到竟然神奇的过了，900+ms 水过，原来还是能卡过的……于是我把更多的细节进行优化，把 *2 和 /2 操作都改为移位运算，再提交时就下降到了 700+ms :-D
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N = 20003; 6 7 char s[N], s2[N << 1]; 8 int p[N << 1]; 9 bool pre[N], suf[N]; 10 11 int main() { 12 int t; 13 scanf("%d",&t); 14 while(t--) { 15 scanf("%s",s); 16 int n = strlen(s); 17 s2[0] = '$'; 18 s2[1] = '#'; 19 for(int i = 0; i < n; ++i) { 20 s2[(i << 1) + 2] = s[i]; 21 s2[(i << 1) + 3] = '#'; 22 } 23 n = (n << 1) + 2; 24 s2[n] = ' '; 25 int right = 0, id = 0; 26 p[0] = 0; 27 for(int i = 1; i < n; ++i) { 28 if(right > i) 29 p[i] = min(p[(id << 1) - i], right - i); 30 else p[i] = 0; 31 while(s2[i + p[i] + 1] == s2[i - p[i] - 1]) ++p[i]; 32 if(i + p[i] > right) { 33 right = i + p[i]; 34 id = i; 35 } 36 } 37 38 int slen = (n >> 1) - 1; 39 40 for(int i = 0; i < slen; ++i) { 41 int s2id = i + 2; 42 pre[i] = (s2id - p[s2id] == 1); 43 } 44 for(int i = slen - 1; i >= 0; --i) { 45 int s2id = i + slen + 1; 46 suf[i] = (s2id + p[s2id] == n - 1); 47 } 48 49 bool flag = 0; 50 for(int i = 4; i <= n - 4; ++i) { 51 int j = s2[i] == '#' ? 2 : 1; 52 for(; j <= p[i]; j += 2) { 53 int id1 = i - j - 1; 54 int id2 = i + j + 1; 55 if(pre[(id1 >> 1) - 1] && suf[(id2 >> 1) - 1]) { 56 flag = 1; 57 break; 58 } 59 } 60 if(flag) break; 61 } 62 puts(flag ? "Yes": "No"); 63 } 64 return 0; 65 }