题目描述：
有一个长度为100的只含A和B的环行串。如果这个串含有AB，那么就变为BA。 给一个串，问有多少种串可以变为这个串。
算法分析：
我们只关心ABABAB...ABAB这样的串。在原串中把这样的子串全都抽出来，再把方案数相乘就可以了。
如果成环的话，那么预处理出所有情况。递推就可以了，是组合数学中非常经典的递推式。
如果不成环，有四种情况。分别为
1. ABAB
2. BABA
3. ABABA
4. BABAB
3和4是一种情况，剩下两个是一种情况。利用预处理的结果计算就可以了。时间复杂度O(n)。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
ll dp[100][2],d[100][2][2];
char ch[205];
int vis[205];
int main(){
static ll clr[100];
dp[0][1] = dp[1][1] = dp[1][0] = 1;
for(int i=2;i<=50;i++)
dp[i][0] = dp[i-1][1],
dp[i][1] = dp[i-1][1] + dp[i-1][0];
d[1][1][1] = 1;
d[1][0][0] = 1;
d[2][0][1] = 1;
d[2][1][0] = 1;
d[2][1][1] = 1;
for(int i=3;i<=50;i++){
d[i][0][1] = d[i-1][0][1] + d[i-2][0][1] ;
d[i][0][0] = 0;
d[i][1][0] = d[i-1][1][1];
d[i][1][1] = d[i-1][1][1] + d[i-1][1][0];
}
for(int i=1;i<=50;i++)
for(int a=0;a<2;a++)
for(int b=0;b<2;b++)
clr[i] += d[i][a][b];
// for(int i=1;i<=50;i++) cout<<clr[i]<<" "; cout<< endl;
// main
while(~scanf("%s",ch)){
memset(vis,0,sizeof(vis));
ll ans = 1;
int n = strlen(ch);
for(int i=0;i<n;i++)
ch[n+i] = ch[i];
int s = 0;
if(ch[s]!=ch[n-1])while(ch[s]!= ch[s+1] && s < n-1) s ++;
for(;s<n;) {
int ed = s;
while(ch[ed]!=ch[ed+1] && ed-s+1 < n) ed ++;
int tmp = ed-s+1>>1;
if(n%2==0 && ed-s+1 == n) {ans = clr[n/2];break;}
if(ch[ed] == ch[s]) ans *= dp[tmp][1];
else if(ch[s] == 'A' ) {
tmp -= 1;
if(tmp == 0) {ans = 0;}
else if(tmp > 2) ans *= dp[tmp-1][1];
}
else ans *= dp[tmp][0] + dp[tmp][1];
//cout<<s<<" "<<ed<<" "<<ans<<endl;
s = ed + 1;
}
cout<< ans << endl;
}
}
posted on 2012-07-29 18:41
西月弦 阅读(352)
评论(0) 编辑 收藏 引用 所属分类:
解题报告