hdu 5340 Three Palindromes

  前几晚 BC 的第二题,官方给出的题解是:

hdu 5340 Three Palindromes

  然后我结合昨天刚看的 Manacher 算法试着写了下,发现 pre、suf 数组挺难构造的,调试了好久,然后就对中间进行枚举了,复杂度应该是 O(n2) 吧,我第一次交时超时了,以为真的要用什么暴力压位,可是我还不会啊,然后作了一些少许的优化提交本想再 T 一次的,没想到竟然神奇的过了,900+ms 水过,原来还是能卡过的……于是我把更多的细节进行优化,把 *2 和 /2 操作都改为移位运算,再提交时就下降到了 700+ms  :-D

  代码如下:

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = ; char s[N], s2[N << ];
int p[N << ];
bool pre[N], suf[N]; int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%s",s);
int n = strlen(s);
s2[] = '$';
s2[] = '#';
for(int i = ; i < n; ++i) {
s2[(i << ) + ] = s[i];
s2[(i << ) + ] = '#';
}
n = (n << ) + ;
s2[n] = '\0';
int right = , id = ;
p[] = ;
for(int i = ; i < n; ++i) {
if(right > i)
p[i] = min(p[(id << ) - i], right - i);
else p[i] = ;
while(s2[i + p[i] + ] == s2[i - p[i] - ]) ++p[i];
if(i + p[i] > right) {
right = i + p[i];
id = i;
}
} int slen = (n >> ) - ; for(int i = ; i < slen; ++i) {
int s2id = i + ;
pre[i] = (s2id - p[s2id] == );
}
for(int i = slen - ; i >= ; --i) {
int s2id = i + slen + ;
suf[i] = (s2id + p[s2id] == n - );
} bool flag = ;
for(int i = ; i <= n - ; ++i) {
int j = s2[i] == '#' ? : ;
for(; j <= p[i]; j += ) {
int id1 = i - j - ;
int id2 = i + j + ;
if(pre[(id1 >> ) - ] && suf[(id2 >> ) - ]) {
flag = ;
break;
}
}
if(flag) break;
}
puts(flag ? "Yes": "No");
}
return ;
}
上一篇:JavaScript学习笔记(三)——this、原型、javascript面向对象


下一篇:推荐10个适合初学者的 HTML5 入门教程