当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ1437字符序列
272+

题目大意:3个字母a、b、c,连成一个长度为n的字符串,要求任意相邻的2个子序列都不相同,共有多少种方案?

题目描述

从三个元素的集合[A,B,C]中选取元素生成一个N个字符组成的序列,使得没有两个相邻字的子序列相同。例:N = 5时ABCBA是合格的,而序列ABCBC与ABABC是不合格的,因为其中子序列BC,AB是相同的。

输入

输入仅有一个整数n(1<=n<=15)。

输出

输出满足条件的N个字符的序列总数。

样例输入

4

样例输出

18

解题思路

n个格子,一个一个字符尝试填进去,如果不能填(出现相邻重复),则进行可行性剪枝,尝试另一个,当n个格子填完以后,累加方案数。

问题1:如何判断任意相邻2个子序列不重复?

由于进行了可行性剪枝,搜索进去以后,当前得到的字符串一定是没有相邻子序列重复的;加入一个字符后,如果会出现相邻子序列重复,那么后面的子序列一定包含最后一个字符,因此,我们只需要枚举后缀,如果出现后缀与字符串删去后缀后的后缀相同,即相邻重复。(枚举到字符串长度的一半即可)

问题2:如何比较两个后缀是否相同?

第一种是暴力枚举,逐个字符比较;第二种是用字符串函数:当前字符串长度为y,枚举子串长度x,用strncpy比较n个字符是否相等(strncpy(s+y-x, s+y-x-x, x));还可以用位运算,将字符串转成一个四进制书,每一位可以填1(01)、2(10)、3(11),如果要比较后2为,即比较s%(1<<4)和s/(1<<4)%(1<<4)。

程序实现

更多
SSOJ1437字符序列:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter