首页 > 试题广场 >

暗黑的字符串

[编程题]暗黑的字符串
  • 热度指数：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
周昆头像 周昆
(***请大家) 顶我吧。
看到大家都是动态规划，时间复杂度应该是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)
月印万川头像 月印万川

编辑于 2017-09-08 17:03:19 回复(0)
C/C++
拖仔头像 拖仔 
#include<iostream>
using namespace std;
//主要是推导公式：
//例如：在字符串BAA的后面只能有两种添加字符的方法
//1.添加和末尾相同的字符变成BAAA，一定不是暗黑的字符串
//2.添加和末尾不同的字符串变成BAAB或BAAC，一定不是暗黑字符串
//用dp[0]和dp[1]分别表示上一次的添加方式对应的暗黑字符串的个数
//所以公式为：dp[0] = temp0 + temp1; dp[1] = 2*temp0 + temp1;
long long blackNum(int n){
    if(n == 1)return 3;
    if(n == 2)return 9;
    long long dp[2];
    dp[0] = 3;
    dp[1] = 6;
    for(int i = 2;i<n;i++){
        long long temp0 = dp[0];
        long long temp1 = dp[1];
        dp[0] = temp0 + temp1;
        dp[1] = 2*temp0 + temp1;
    }
    return dp[0]+dp[1];
}
int main(){
    int n;
    while(cin>>n){
        cout<<blackNum(n)<<endl;
    }
    return 0;
}

发表于 2016-11-16 16:06:44 回复(10)
EmmaLR头像 EmmaLR
发表于 2016-12-05 17:15:15 回复(0)
Return（truth）头像 Return（truth）

/*思路是这样的，在第n位填和第n-1位或第n-2位一样的字母一定是暗黑串，此时种数是2*a[n-1]，而这些种数中多包含了一个重复的第n-1位和第n-2位一样的情况，第n-1位和第n-2位一样的种数显然位a[n-2],此时有2*a[n-1]-a[n-2]种，但是当n-1位和n-2位一样的时候最后一位填什么都可以，前面已经计算过了和这两位一样的情况，因此还要加上其他两个字母的情况即2*a[n-2],最后和在一起就是：
   2*a[n-1]-a[n-2]+2*a[n-2]=2*a[n-1]+a[n-2]
感觉不是在考动态规划，实在考容斥定理*/
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include "stdlib.h"
using namespace std;

int main(){
 int n;
 cin>>n;
 long long  dp[n+1];
 for(int i=0;i<n+1;i++){
  dp[i]=0;
 }
 dp[0]=1;
 dp[1]=3;
 dp[2]=9;
 for(int i=3;i<=n;i++){
  dp[i]=2*dp[i-1]+dp[i-2];
 }
 cout<<dp[n]<<endl;

}
发表于 2018-05-22 17:35:36 回复(2)
Bullet头像 Bullet 
import java.util.Scanner;
import java.lang.Math;

public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int input = sc.nextInt();
		long[] num = new long[input+1];
		num[1] = 3;
		num[2] = 9;
		for(int i=3; i<=input; i++){
			num[i] = 2*num[i-1] + num[i-2];
		}
		System.out.print(num[input]);
	}
}

发表于 2016-09-16 22:15:27 回复(1)
为啥要起名字头像 为啥要起名字
import sys
n=int(sys.stdin.readline().strip())
record=[0,3,9]
if n>=3:
    for i in range(3,n+1):
        record.append(2*record[i-1]+record[i-2])
print(record[n])
发表于 2018-05-14 10:29:57 回复(0)
KiKiC头像 KiKiC 
完全不用推导，规模足够小，递推可以直接过


	//





	//  main.cpp





	//  TestNewCoder





	//





	//  Created by starlight on 2018/4/4.





	//  Copyright © 2018年 sysu. All rights reserved.





	//





	







	#include <iostream>





	







	using namespace std;





	







	long long f[40][4][4], sum;





	







	int n;





	







	int main(int argc, const char * argv[]) {





	    // insert code here...





	    





	    cin >> n;





	    





	    if (n == 1) {





	        cout << 3;





	    }





	    else if (n == 2) {





	        cout << 9;





	    }





	    





	    else {





	        for (int i = 1 ; i <= 3 ; i++)





	            for (int j = 1 ; j <= 3 ; j++)





	                f[2][i][j] = 1;





	        // 初始化





	        





	        for (int i = 3 ; i <= n ; i++) {





	            for (int k1 = 1 ; k1 <= 3 ; k1++) {





	                for (int k2 = 1 ; k2 <= 3 ; k2++) {





	                    for (int k3 = 1 ; k3 <= 3 ; k3++) {





	                        f[i][k1][k2] += (k1 * k2 * k3 != 6 ? f[i-1][k2][k3] : 0);





	                    }





	                }





	            }





	        }





	        





	        for (int i = 1 ; i <= 3 ; i++) {





	            for (int j = 1 ; j <= 3 ; j++) {





	                sum += f[n][i][j];





	            }





	        }





	        





	        cout << sum;





	        





	    }





	    





	    





	    return 0;





	}

发表于 2018-04-04 00:45:58 回复(1)
DDUP4头像 DDUP4
/*
其实就是个很简单的动态规划题，
*/
import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int num;
        while(in.hasNext()){
            num=in.nextInt();
            System.out.println(doSm((long)num));
        }
    }
    public static long doSm(long n){
        int thisN=(int)n;
        long res[][]=new long[thisN+1][2];
        res[1][0]=0;
        res[1][1]=3;
        res[2][0]=3;
        res[2][1]=6;
        for(int i=3;i<=thisN;i++){
            res[i][0]=res[i-1][0]+res[i-1][1];
            res[i][1]=2*res[i-1][0]+res[i-1][1];
        }
        if(thisN==1)
            return 3;
        else if(thisN==2)
            return 9;
        return res[thisN][0]+res[thisN][1];
    } 
}

发表于 2017-09-25 17:14:33 回复(0)
Coast2头像 Coast2 
def main():
    while(True):
        try:
            n=int(raw_input().strip());
            dp=[0,3,9];
            for i in range(3,n+1):
                dp.append(2*dp[i-1]+dp[i-2]);
            print dp[n];
        except:
            break;
main();

发表于 2016-09-13 15:55:26 回复(0)
bupt渣硕头像 bupt渣硕 
#include <iostream>
using namespace std;
int main(){
    int n = 0;
    while(cin >> n){
        long long dp[31] = {0};
        dp[1] = 3, dp[2] = 9;
        for( int i = 3; i <= n; i++ )
            dp[i] = 2*dp[i-1]+dp[i-2];
        cout<<dp[n]<<endl;
    }	
}




编辑于 2016-09-13 11:12:44 回复(63)
Java
pein531头像 pein531
本来想分析分析，结果写到4的时候找到了一个递推式：
然后大胆运行了一下，结果过了 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            int n = Integer.parseInt(line);
            long[] dp = new long[n + 1];
            dp[1] = 3;
            dp[2] = 9;
            for(int i = 3; i <= n; i++){
                dp[i] = 2*dp[i - 1] + dp[i - 2];
            }
            System.out.println(dp[n]);
        }
    }
}

发表于 2022-01-07 18:26:42 回复(0)
濺亽翔头像 濺亽翔 
import java.io.*;

/**
 * 数学排列组合法，找暗黑的字符串
 * 规律：
 * 当第 1 位固定后，第 2 位有 3 种填法：第 3 位对应的第 2 位有 3 + 2 + 2 种
 *       ————————————————————————————————
 * 第一位 |A
 *       --------------------------------
 * 第二位 |AA            AB        AC
 *       --------------------------------
 * 第三位 |AAA AAB AAC   ABA ABB   ACA ACC
 *
 * 从第 4 位开始，如果前一位有 3 种排法（AAA AAB AAC），则本位可以有：3 + 2 + 2 种排法
 *              如果前一位有 2 种排法（ABA ABB），则本位可以有：3 + 2 种排法
 *
 * 可以总结出规律，从第 2 位起，就有 3 生 3+2+2，2 生 3+2 的规律
 *
 * 列式：
 * 假设第一位固定一个，只需要让最后的结果 *3 即可
 * f(2) = 3
 * f(3) = 3 + 2 + 2
 * f(4) = (3 + 2 + 2) + (3 + 2) + (3 + 2)
 * …………
 * 只需要迭代统计 3 出现的次数和 2 出现的次数，计算储结果即可
 *
 * @param n
 * @return 注意类型可能会超出 int_max
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long n3 = 1, n2 = 0, tmp;
        while(n-- > 2) {
            tmp = n3;
            n3 = tmp + n2;
            n2 += 2 * tmp;
        }
        System.out.println((n3 * 3 + n2 * 2) * 3);
    }
}

发表于 2020-08-28 13:07:36 回复(0)
C/C++
Delta_Go头像 Delta_Go
/*
关键找到三个关系式，推出递推公式：
设长度为n的暗黑字符串有f(n)个： 
(1)考察最后两个字符，相同S(n)种或不同D(n)种
    f(n)=S(n)+D(n).
(2)考察第n项和前n-1项的关系，前两个相同，后可接三种情况；前两个不同，后可接两种情况
    f(n)=3*S(n-1)+2*D(n-1).
(3)深入挖掘S(n)、D(n)和S(n-1)、D(n-1)的关系，S(n-1)后面接的三种情况中有一种是S(n)的;D(n-1)后面接的两种情况中有一种是S(n)的，即：
    S(n)=S(n-1)+D(n-1),即S(n)=f(n-1).
综合这三个关系式可导出递推式f(n)=2*f(n-1)+f(n-2).

要找关于三个字符的关系，猜应该有三个关系式才能解决，如果四个呢？五个呢？这题放在高中估计大家都会，只是高考过了太久，做题套路都扔了。     
*/

#include<iostream>

using namespace std;

long long f(int n){
    if(n==1) return 3;
    else if(n==2) return 9;
    else return 2*f(n-1)+f(n-2);
}

int main(){ 
    
    int n;
    cin>>n;
    cout<<f(n)<<endl;    
    
    return 0;
} 

编辑于 2018-09-28 11:00:26 回复(0)
C/C++
nbgao头像 nbgao 
#include <iostream>

using namespace std;

int main()
{     int n = 0;     while(cin>>n)     {         long long a[31] = {0, 3, 9};         for(int i=3;i<=n;i++)             a[i] = 2*a[i-1] + a[i-2];         cout<<a[n]<<endl;     }     return 0;
}

发表于 2018-01-15 00:29:40 回复(0)
诗妮头像 诗妮 
package LineCode.Recruit2017.网易;

import java.util.Scanner;

/**
 * 题目描述
 一个只包含'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)

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

 示例
 输入 2 3
 输出 9 21

 掉的坑：
 1.int[] f 不够，要long
 */
public class 暗黑的字符串 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            Integer n = sc.nextInt();
            long[] f = new long[n+1];
            f[1] = 3;
            f[2] = 9;
            for (int i = 3; i <= n; i++) {
                f[i] = 2 * f[i-1] + f[i-2];
            }
            System.out.println(f[n]);
        }
    }

}
发表于 2018-01-08 23:34:07 回复(0)
元气の悟空头像 元气の悟空 
#include<stdio.h>
long long dp[30];
int main(){
    dp[1]=3,dp[2]=9;
    int i,N;
    for(i=3;i<=30;i++) dp[i]=2*dp[i-1]+dp[i-2];
    while(scanf("%d",&N)!=EOF)
        printf("%lld\n",dp[N]);
}//先强行dfs找了一波答案
 //发现数列是 3 9 21 51 123...
 //好，发现规律了，a[n]=2*a[n-1]+a[n-2],那就可以秒掉了~

发表于 2017-08-30 16:50:42 回复(2)
jokervsbat头像 jokervsbat
暴力解决
import java.util.Scanner;
public class Main {
 public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  System.out.println(method(n));
 }
 
 public static long method(int n){
  if(n == 2){
   return 9;
  }
  long result = 0;
  //前两位相同
  result += 3 * search(n - 2, true);
  //前两位不同
  result += 6 * search(n - 2, false);
  return result;
 }
 
 public static long search(int n, boolean ifEqual){
  if(ifEqual){
   if(n == 1){
    return 3;
   }
   else{
    return 2 * search(n - 1, false) + search(n - 1, true);
   }
  }
  else{
   if(n == 1){
    return 2;
   }
   else{
    return search(n - 1, true) + search(n - 1, false);
   }
  }
 }
}
发表于 2017-08-25 12:54:42 回复(0)
rs勿忘初心头像 rs勿忘初心 
#include<iostream>
#include<string>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
      {
          long long f[31];  //注意结果有可能超出int型范围，需要用long long型
          f[1]=3;
          f[2]=9;
          for(int i=3;i<=n;i++)
              f[i]=2*f[i-1]+f[i-2];  //递推公式需证明
          cout<<f[n]<<endl;
      }
    return 0;
}
图片来自@bupt渣硕
发表于 2017-09-02 11:06:01 回复(0)
寻找阳光的蜗牛头像 寻找阳光的蜗牛 
//由递推算得通项公式
import java.util.*;

public class Main{
    public static void main(String[] arg){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double a = (1 + Math.pow(2,0.5));
        double b = 2 - a;
        double x = (9 - 3 * a)/(b*(b - a));
        double y = Math.pow(a,n) * (3-x) +  Math.pow(b,n) * x;
        System.out.print(Math.round(y));
        
    }
}

发表于 2016-09-13 11:27:51 回复(2)
提交观点

问题信息

动态规划
来自：网易2017秋招编程题集合
难度：
87条回答 21342浏览

热门推荐

通过挑战的用户

查看代码

相关试题

暗黑的字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号