首页 > 代码库 > HRBUST1589(数学递推)

HRBUST1589(数学递推)

2024-07-30 17:12:29   223人阅读

彩桥

Time Limit: 1000 MS Memory Limit: 32768 KB

64-bit integer IO format: %lld , %llu Java class name: Main

[Submit] [Status] [Discuss]

题目链接：http://acm.hrbust.edu.cn/vj/index.php?c=problem-problem&id=75523

Description

Cc用了药水之后状态全满，现在出现在他们眼前的是一个悬崖，悬崖之间有一座不停在变换着颜色的桥，wd发现桥是由一个个变换着颜色的板组成，每次只能够从一个板走到相邻的一块板上，而且不能回头。每块板只会在红，黄，蓝三种颜色之间变换。如果想要到达对岸必须经过此桥，wd突然发现了桥的一个玄妙的的地方，就是经过的时候，连续的三个板如果颜色都不相同，就会有杯具发生...例如：经过的时候如果走过的连续三个是“红黄蓝”就会不妙，但是“红红蓝”“蓝蓝蓝”等情况就可以。

Cc问wd：到达对岸的方法一共有多少种？


Input

多组测试数据，第一行一个整数T，表示数据的组数。

接下来T行，每行一个整数n，表示桥是由n块板组成。

Output

输出一个整数表示经过这座桥的总的方法数，每组输出占一行。

Sample Input


	2




	2




	3

Sample Output


	9




	21

Hint

注意结果会很大请用long long



解题思路：
  姐姐一A了这道题，赛后姐姐说第一眼就对它有感觉，感觉是递推·······Orz·······姐姐数学感觉比我好·········
仰慕的听姐姐给我们讲了下思路，对于a[1]一定有3种情况，a[2]一定有9种情况，这是毋庸置疑的。接下来开始
递推，分颜色全相同和颜色有不同来考虑：
当n = 3 时
（1）颜色全相同，此时有3*3=9种情况；
（2）颜色有不同，此时有（9 - 3 = 6） * 2 = 12 种情况。综上，当n = 3时有9 + 12 = 21种。
当n = 4使
（1）颜色全相同，此时有3 * 9 = 27种；
（2）颜色由不同，此时有（21-9 = 12） * 2 = 24种。综上，当n = 4时有27 + 24 = 51种。



完整代码：
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;

/** Constant List .. **/ //{

const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;
const int maxn = 1000001;
LL a[maxn];
int main()
{
    #ifdef DoubleQ
    freopen("in.txt","r",stdin);
    #endif
    int T;
    scanf("%d",&T);
    a[1] = 3;
    a[2] = 9;
    for(int i = 3 ; i < maxn ; i ++)
    {
        a[i] = 3 * (a[i-2]) + 2 * (a[i-1] - a[i-2]);
    }
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("%lld\n",a[n]);
    }
}


HRBUST1589(数学递推)


联系
我们