昨晚的bc做得好忧郁-----
第一题改了好久好久好久----等改完发现比赛已经结束了（发现是枚举子集的位运算那儿写错了--）
第二题是判断能否将一个字符串划分成三段回文串
今天学了一点点 Manacher
http://wenku.baidu.com/view/3031d2d3360cba1aa811da42.html
模板大概是这样的--
void Manacher(){
for(int i = ;i <= len;i++){
t[*i-] = '#';
t[*i] = s[i];
}
t[] = '?';t[len*+] = '#';
t[*len+] = '\0';
int tmax = ,id = ;
len = len* + ;
for(int i = ;i <= len;i++){
if(tmax > i) p[i] = min(p[*id-i],tmax-i);
else p[i] = ;
while(t[i-p[i]] == t[i+p[i]]) p[i]++;
if(i+p[i] > tmax){
tmax = i+p[i];
id = i;
}
}
}
hdu 3068
求最长回文串
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std; #define getmid(l,r) ((l) + ((r) - (l)) / 2)
#define MP(a,b) make_pair(a,b)
#define PB push_back typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-;
const int INF = ( << ) - ;
const int maxn = *; char s[maxn];
char t[maxn];
int p[maxn]; void Manacher(){
int len = strlen(s+);
for(int i = ;i <= len;i++){
t[*i-] = '#';
t[*i] = s[i];
}
t[] = '?';
t[*len+] = '#';
t[*len+] = '\0';
int tmax = ,id = ;
int ans = ;
len = *len + ;
for(int i = ;i <= len;i++){
if(tmax > i) p[i] = min(p[*id-i],tmax-i);
else p[i] = ;
while(t[i-p[i]] == t[i+p[i]]) p[i]++;
if(i+p[i] > tmax){
tmax = i+p[i];
id = i;
}
ans = max(ans,p[i]);
}
printf("%d\n",ans-);
} int main(){
while(scanf("%s",s+) != EOF){
Manacher();
}
return ;
}
hdu 5340
先用一遍Manacher
然后如果从1到这个位置是回文串的话，把这个位置加进L[]数组
如果从这个位置到结尾是回文串的话，把这个位置加进R[]数组
再枚举L,R,判断L---R这个区间是不是回文串
判断方法就是看一下，这个区间的中点的p[i]能否覆盖这个中间部分---
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; const int maxn = ; char s[maxn],t[maxn];
int p[maxn],L[maxn],R[maxn];
int len; void Manacher(){
for(int i = ;i <= len;i++){
t[*i-] = '#';
t[*i] = s[i];
}
t[] = '?';t[len*+] = '#';
t[*len+] = '\0';
int tmax = ,id = ;
len = len* + ;
for(int i = ;i <= len;i++){
if(tmax > i) p[i] = min(p[*id-i],tmax-i);
else p[i] = ;
while(t[i-p[i]] == t[i+p[i]]) p[i]++;
if(i+p[i] > tmax){
tmax = i+p[i];
id = i;
}
}
} bool solve(){
Manacher();
int l = ,r = ;
int length = strlen(s+);
for(int i = ;i <= len-;i++){
if(i - p[i] == ) L[l++] = i;
if(i + p[i] == len+) R[r++] = i;
} for(int i = ;i < l;i++){
for(int j = r-;j >= ;j--){
// printf("R[%d] = %d ",j,R[j]);
int lb = L[i] + p[L[i]],ub = R[j] - p[R[j]];
if(lb > ub) break;
int mid = (lb + ub)/;
// printf("lb = %d ub = %d mid = %d\n",lb,ub,mid);
if(p[mid] > mid - lb) return true;
}
}
return false;
} int main(){
int T;
scanf("%d",&T);
while(T--){
memset(p,,sizeof(p));
scanf("%s",s+);
len = strlen(s+);
if(solve()) printf("Yes\n");
else printf("No\n");
}
return ;
}
题解的暴力压位还是不会的说啊～～～