首页 > 试题广场 >

暗黑的字符串

[编程题]暗黑的字符串

热度指数：14072 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。例如：
BAACAACCBAAA 连续子串"CBA"中包含了'A','B','C'各一个，所以是纯净的字符串
AABBCCAABB 不存在一个长度为3的连续子串包含'A','B','C',所以是暗黑的字符串
你的任务就是计算出长度为n的字符串(只包含'A'、'B'和'C')，有多少个是暗黑的字符串。

输入描述:

输入一个整数n，表示字符串长度(1 ≤ n ≤ 30)

输出描述:

输出一个整数表示有多少个暗黑字符串

示例1

输入

2 3

输出

9 21

算法知识视频讲解

查看答案及解析

Python

lx的流星

while True:
    try:
        n=input()
        #print(n)
        n=int(n)
        #print(n)
        result=0
        dp=[]
        for i in range(n+1):
            dp.append([0])
        dp[0]=3
        dp[1]=9
        if n>2:
            for i in range(3,n+1):
                dp[i-1]=dp[i-3]+2*dp[i-2]
            #print(dp)
            result=dp[n-1]
        elif n==2:
            result=9
        elif n==1:
            result=3
        print(result)
    except:
        break

惭愧，刚开始居然没有反应过来要用动态规划，没弄懂题，看来还要练习

编辑于 2019-05-22 10:21:22 回复(0)

Python

三三四四萨达

n = int(input()) 
arr = [0, 3, 9] 
for i in range(3, n+1):
     arr.append(2*arr[i-1]+arr[i-2])   print(arr[n])

人生苦短，我用python

编辑于 2018-10-10 15:43:39 回复(0)

Python

新鲜菜鸡🐔

其他人的思路（很标准）：
在第n位填和第n-1位或第n-2位一样的字母一定是暗黑串，此时种数是2a[n-1]，而这些种数中多包含了一个重复的第n-1位和第n-2位一样的情况，第n-1位和第n-2位一样的种数显然位a[n-2],此时有2a[n-1]-a[n-2]种，但是当n-1位和n-2位一样的时候最后一位填什么都可以，前面已经计算过了和这两位一样的情况，因此还要加上其他两个字母的情况即2*a[n-2].

自己的思路（低智商观察法）：

首先是个递进的问题，长n的黑暗字串只能在n-1上面添加字符诞生。而添加字符只用考虑长n-1字符串的最后两位。分为两种情况，不相同，有两种添加法，相同则有3种添加法。现在就是挑出相同的情况有多少种，很明显n-1中相同的来自n-2黑暗字串，而把n-2的黑暗字串全部添加和末尾相同的字符，一定还是黑暗字串，所以n-1的尾巴相同的黑暗字串和n-2黑暗字串数量相同。所以f(n)=2f(n-1)+f(n-2).

N = int(input())
ans = [0 for i in range(31)]
ans[1] = 3
ans[2] = 9
for i in range(3,31):
    ans[i] = ans[i-1]*2+ans[i-2]
print(ans[N])

发表于 2018-05-24 23:09:08 回复(0)

Python

离疏

while 1:
    try:
        n=int(input())
    except:
        break
    ans=[3,9,21]
    for i in range(4,31):
        temp=2*ans[-1]+ans[-2]
        ans.append(temp)
    print(ans[n-1])

发表于 2018-05-17 12:59:09 回复(0)

Python

吉事有祥

n = int(input())
a, b = 3, 3
for _ in range(n-1):
    a, b = 2*a+b, a
print(a)

发表于 2017-10-12 13:39:56 回复(0)

Python

周昆

(***请大家) 顶我吧。

看到大家都是动态规划，时间复杂度应该是O(N)。下面提供一个O(logN)的算法。当然单次循环计算量比之前动态规划大很多。但是循环数目是logN。所以n很大是必然比之前动态规划优。

之前思想：f(n) = 2f(n-1) + f(n-2)

可是这题能用的信息比这个迭代式多。有两种结尾aa型和ab型。分别计算他们的数目。在下一个长度暗黑字符串中，aa = aa + ab 和 ab = 2 * aa + ab。那么我们可以得到矩阵式子。每增加一个长度，就是左乘一个矩阵 [[1, 1], [2, 1]]。那么接下来快速幂等计算。以下是Python代码。因为矩阵小就直接枚举计算每个元素。不然就会用循环。

n = int(raw_input())
if n == 1:
	print 3
else:
	# initialization, aa-type:3, ab-type:6
	ans = [3, 6] 
	mat = [[1, 1], [2, 1]]
	temp_ans = [0, 0]
	temp = [[0, 0], [0, 0]]
	# number of interation
	n = n - 2
	while n != 0:
		if n & 1 == 1:
			# update ans
			temp_ans[0] = mat[0][0] * ans[0] + mat[0][1] * ans[1]
			temp_ans[1] = mat[1][0] * ans[0] + mat[1][1] * ans[1]
			ans[0] = temp_ans[0]
			ans[1] = temp_ans[1]
		# update the matrix
		temp[0][0] = mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0]
		temp[0][1] = mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1]
		temp[1][0] = mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0]
		temp[1][1] = mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1]
		# assign temp back to mat
		mat[0][0] = temp[0][0]
		mat[1][0] = temp[1][0]
		mat[0][1] = temp[0][1]
		mat[1][1] = temp[1][1]
		n = n >> 1
	print ans[0] + ans[1]

发表于 2017-04-24 12:09:27 回复(1)