构造字符串。。

构造字串
生成长度为n的字串，其字符从26个英文字母的前p(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时
‘a b c b a’满足条件　　
‘a b c b c’不满足条件

INPUT：

两个整数N,P；N<=10，P<=26；

5 3

OUTPUT：

所有满足条件的字串的方案总数

思路：

一道典型的dfs。但是是字符串。如样例：B C=B C所以不符合条件。每添加一个，就要判断是否有重复。如果有return；

如何判断？

1 if(s1.size()%2==0)
2             {
3                 for(int j=2;j<=s1.size()/2;j++)
4                 {
5                     x=s1.substr(s1.size()-j+1,j-1);x+=i;
6                     y=s1.substr(s1.size()-2*j+1,j);
7                     if(x==y)                  {f=0;   break;}
8                 }
9             }

但是，位数不够呢？

 1 if(s1.size()>2)
 2         {
 3             if(s1.size()%2==0)
 4             {
 5                 for(int j=2;j<=s1.size()/2;j++)
 6                 {
 7                     x=s1.substr(s1.size()-j+1,j-1);x+=i;
 8                     y=s1.substr(s1.size()-2*j+1,j);
 9                     if(x==y)                  {f=0;   break;}
10                 }
11             }
12             else
13             {
14                 for(int j=2;j<=s1.size()/2+1;j++)
15                 {
16                     x=s1.substr(s1.size()-j+1,j-1);
17                     x+=i;
18                     y=s1.substr(s1.size()-2*j+1,j);
19                     if(x==y)
20                     {f=0;   break;}
21                 }
22             }
23         }

cpp：

 1 #include<iostream>
 2 #include<string>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<iomanip>
 8 #include<queue>
 9 using namespace std;
10 string s1,x,y;
11 int n,p,sum=0;
12 void dfs(string s1)
13 {
14     if(s1.size()==n) {sum++; return;}
15     for(char i='a';i<'a'+p;i++)
16     {
17         if(i==s1[s1.size()-1])    continue;
18         bool f=1;
19         if(s1.size()>2)
20         {
21             if(s1.size()%2==0)
22             {
23                 for(int j=2;j<=s1.size()/2;j++)
24                 {
25                     x=s1.substr(s1.size()-j+1,j-1);x+=i;
26                     y=s1.substr(s1.size()-2*j+1,j);
27                     if(x==y)                  {f=0;   break;}
28                 }
29             }
30             else
31             {
32                 for(int j=2;j<=s1.size()/2+1;j++)
33                 {
34                     x=s1.substr(s1.size()-j+1,j-1);
35                     x+=i;
36                     y=s1.substr(s1.size()-2*j+1,j);
37                     if(x==y)
38                     {f=0;   break;}
39                 }
40             }
41         }
42         if(f==1)    dfs(s1+i);
43     }
44 }
45 int main()
46 {
47     
48     //freopen("a.in","r",stdin);
49     //freopen("a.out","w",stdout);
50     cin>>n>>p;
51     for(char i='a';i<'a'+p;i++)
52     {
53        s1.clear();
54         dfs(s1+i);
55     }
56     cout<<sum<<endl;
57     return 0;
58 }

View Code

P.S(cpp MADE BY MHZ)