1
已解决
中级守护
从三个元素的集合[A, B, C]中选取元素生成一个N个字符组成的序列，使得没有两个相邻字的子序列（子序列长度=2）相同。例：N=5时ABCBA是合格的，而序列ABCBC与ABABC是不合格的，因为其中子序列BC，AB是相同的。 对于由键盘输入的N（1<=N<=12），求出满足条件的N个字符的所有序列和其总数。
样例输入 Sample Input
1
样例输出 Sample Output
A
B
C
3
0
已采纳
资深光能
注意，这里有一个巨大大大大大大大大的坑，我也掉过，
每一个字母后面有一个空格，重要的事说三遍：空个空格空格！！！
望采纳，谢谢。
这样例太坑了，我试了1小时。
算了，核心来了。
if(t>n)
{
total++;
输出；
return ;
}
if(t>3)
{
for(char i='A';i<='C';i++)
{
if(a[t-2]!=i || a[t-3]!=a[t-1])
{
a[t]=i;
搜索
}
}
}
else
{
for(char i='A';i<='C';i++)
{
a[t]=i;
搜索
}
}
}
0
高级天翼
难，唉
0
高级天翼
难，唉
0
资深天翼
1
0
资深光能
用DFS枚举所有串，再分别判断是否符合条件。
时间复杂度 O(3^n*n^2) ，我计算过了，不会超时。
0
高级光能
DFS，类似全排列
0
初级天翼
void search(int t)
{
if(t>n)
{
输出，计数
}
for (int i=1;i<=3;i++) // A,B,C三个字母循环。
{
if ((i!=result[t-2]) || (result[t-1] != result[t-3])) //使得没有两个相邻字的子序列（子序列长度=2）相同
{
result[t]= i;
search（下一个。）
}
}
}
栾峻岩在2018-01-30 18:06:20追加了内容
计数时ans/count是全局变量，每次输出要换行，最后输出ans/count(都可以）
思路：
A,B,C三个字母循环， 使得没有两个相邻字的子序列（子序列长度=2）相同 ，
例如：
abcde
--->> a b c d e（拆开）
从a到b判断。（从1到长度-3的字母判断）。
a!=c b!=d 满足！ b!=d c!=e 也满足，则输出，并换行！！
