??? }???????????????????????????????????????????????????????????????????????????????? //100000000后，保存的數(shù)據(jù)

??? return 0;????????????????????????????????????????????????????????????????????? //只有8位

}?

PS：此題用了個(gè)3維的數(shù)組，占用的空間比較大，可以考慮用兩個(gè)2維的數(shù)組代替。另外，此題用C++提交會超時(shí)且堆棧溢出，而用G++提交則不會，這說明本代碼不優(yōu)，同時(shí)也間接說明了用G++提交代碼的好處。

?

?

?

?

?

?

?

1002：Tri Tiling

Problem Description

In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.

?

?Input

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.

Output

For each test case, output one integer number giving the number of possible tilings.

Sample Input

2

8

12

-1

Sample Output

3

153

2131

Source

University of Waterloo Local Contest 2005.09.24

?

題目分析：

?

題目大意：

用2*1大小的多米諾骨排蓋3*n的矩形，問有多少種蓋法。

?

我的思路：

首先可以看出，當(dāng)n為奇數(shù)時(shí)，無論怎么蓋也不會蓋成3*n的矩形，故只需考慮n為偶數(shù)即可。可以將此題抽象為一個(gè)3*n的矩陣，用f(a,b,c)代表有多少種蓋法，其中a,b,c分別代表第1、2、3行的元素個(gè)數(shù)，由此推導(dǎo)遞歸公式。假設(shè)第n列已蓋好，那么它可由以下幾種情況組成：

（1）??? 橫放3個(gè)，此時(shí)f(a,b,c)=f(a-2,b-2,c-2);

（2）??? 豎放1個(gè)，橫放1個(gè)，此時(shí)f(a,b,c)=f(a-1,b-1,c-2);

（3）??? 橫放1個(gè)，豎放1個(gè)，此種情況與（2）對稱，故仍可用f(a,b,c)=f(a-1,b-1,c-2)。

?

于是得遞推公式：

當(dāng)a=b=c時(shí)，f(a,b,c)= 2*f(a-2,b-1,c-1)+f(a-2,b-2,c-2);

當(dāng)a<b且b=c時(shí)，f(a,b,c)= f(a,b-1,c-1)+f(a-2,b-2,c-2).

（由于f(a-2,b-1,c-1)產(chǎn)生了另一種情況：a<b且b=c,此時(shí)它由f(a,b-1,c-1)和f(a-2,b-2,c-2)兩種情總組成。f(a,b-1,c-1)表示該情況是由第二第三排豎放一個(gè)產(chǎn)生的；f(a-2,b-2,c-2)表示該情況是由3個(gè)橫放產(chǎn)生的，當(dāng)然第一排的橫放要比第二第三排縮一格。）

下一步就是要確定初始條件：

當(dāng)a=b=c=0時(shí)，f(a,b,c)=1.因?yàn)橐涣幸膊慌乓菜闶且环N方法。

當(dāng)a或b或c中有一個(gè)小于0時(shí)，f(a,b,c)=0.因?yàn)檫@種情況不可能存在。?

以下是我的代碼：

?

#include<stdio.h>

int f(int a,int b,int c)

{

??? if(a*b*c==0)return 1;

??? else if(a<0||b<0||c<0)return 0;

??? else if(a==b&&b==c)return 2*f(a-2,b-1,c-1)+f(a-2,b-2,c-2);

??? else if(a<b&&b==c)return f(a,b-1,c-1)+f(a-2,b-2,c-2);

}

int main()

{

??? int n,s;

??? while(scanf("%d",&n)!=EOF&&n!=-1)

??? {

????? if(n%2==0)s=f(n,n,n);

????? else s=0;

????? printf("%d\n",s);

??? }

??? return 0;

}?

PS：此題也可以根據(jù)遞推用數(shù)組解決，以減少題目用時(shí)。

?

?

?

?

?

?

1003：漢諾塔II

Problem Description

經(jīng)典的漢諾塔問題經(jīng)常作為一個(gè)遞歸的經(jīng)典例題存在。可能有人并不知道漢諾塔問題的典故。漢諾塔來源于印度傳說的一個(gè)故事，上帝創(chuàng)造世界時(shí)作了三根金剛石柱子，在一根柱子上從下往上按大小順序摞著64片黃金圓盤。上帝命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一回只能移動一個(gè)圓盤。有預(yù)言說，這件事完成時(shí)宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門至今仍在一刻不停地搬動著圓盤。恩，當(dāng)然這個(gè)傳說并不可信，如今漢諾塔更多的是作為一個(gè)玩具存在。Gardon就收到了一個(gè)漢諾塔玩具作為生日禮物。

　　Gardon是個(gè)怕麻煩的人（恩，就是愛偷懶的人），很顯然將64個(gè)圓盤逐一搬動直到所有的盤子都到達(dá)第三個(gè)柱子上很困難，所以Gardon決定作個(gè)小弊，他又找來了一根一模一樣的柱子，通過這個(gè)柱子來更快的把所有的盤子移到第三個(gè)柱子上。下面的問題就是：當(dāng)Gardon在一次游戲中使用了N個(gè)盤子時(shí)，他需要多少次移動才能把他們都移到第三個(gè)柱子上？很顯然，在沒有第四個(gè)柱子時(shí)，問題的解是2^N-1，但現(xiàn)在有了這個(gè)柱子的幫助，又該是多少呢？

Input

包含多組數(shù)據(jù)，每個(gè)數(shù)據(jù)一行，是盤子的數(shù)目N(1<=N<=64)。

Output

對于每組數(shù)據(jù)，輸出一個(gè)數(shù)，到達(dá)目標(biāo)需要的最少的移動數(shù)。

Sample Input

1

3

12

Sample Output

1

5

81

Author

Gardon

Source

Gardon - DYGG's contest 2

?

題目分析：

?

我的思路：

剛開始沒什么思路，于是分析數(shù)據(jù)，發(fā)現(xiàn)了下面的規(guī)律：

a[1]=1;

a[2]=a[1]+2;a[3]=a[2]+2;(2個(gè)加2^1)

a[4]=a[3]+4;a[5]=a[4]+4;a[6]=a[5]+4;(3個(gè)加2^2);

…………………………………………(4個(gè)加2^3);

……

?

以下是我的代碼：

?

#include<stdio.h>

#include<math.h>

int main()

{

??? int n,i,j,k,sum;

??? int f;

??? while(scanf("%d",&n)!=EOF)

??? {

????? k=2;

????? for(i=1;i<=n;i++)

????? {

??????? if(i==1)f=1,sum=1;

??????? else

??????? {

????????? for(j=k;sum<i;j++)sum+=j;

????????? k=j;

????????? f+=(int)pow(2,j-2);

??????? }

????? }

????? printf("%d\n",f);

??? }

??? return 0;

}?

?

?

?

?

?

?

1004：三角形

Problem Description

用N個(gè)三角形最多可以把平面分成幾個(gè)區(qū)域?

Input

輸入數(shù)據(jù)的第一行是一個(gè)正整數(shù)T(1<=T<=10000),表示測試數(shù)據(jù)的數(shù)量.然后是T組測試數(shù)據(jù),每組測試數(shù)據(jù)只包含一個(gè)正整數(shù)N(1<=N<=10000).

Output

對于每組測試數(shù)據(jù),請輸出題目中要求的結(jié)果.

Sample Input

2

1

2

Sample Output

2

8

Author

Ignatius.L

?

題目分析：

?

我的思路：

第n個(gè)三角形每條邊最多與2*（n-1）條邊相交。對于每條邊，它所截出的區(qū)域（不算第n個(gè)三角形的角）有2*（n-1）-1個(gè)，于是3條邊可截出6*(n-1)-3個(gè)區(qū)域，再加上3個(gè)角即可多出6*(n-1)個(gè)區(qū)域。

于是得遞推公式：f(n)=f(n-1)+ 6*(n-1)

初始條件是：f(1)=2

?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

?????? int t,n;

?????? __int64 f;

?????? while(scanf("%d",&t)!=EOF)

?????? while(t--)

?????? {

????????????? scanf("%d",&n);

????????????? f=2;

????????????? while(n!=1)f+=6*(n-1),n--;

????????????? printf("%I64d\n",f);

?????? }

?????? return 0;

}?

PS：由以上遞推公式可得到最終公式，使得代碼更加優(yōu)化，這里就不再細(xì)說了。

另外，平面是2維的，它跟二次多項(xiàng)式a*x^2+b*x+c有關(guān)，我們可以用1、2、3個(gè)平面的情況推出系數(shù)a,b,c，這樣同樣可以得到最終公式！

?

?

?

?

?

?

1005：下沙的沙子有幾粒？

Problem Description

2005年11月份，我們學(xué)校參加了ACM/ICPC 亞洲賽區(qū)成都站的比賽，在這里，我們獲得了歷史性的突破，盡管只是一枚銅牌，但獲獎那一刻的激動，也許將永遠(yuǎn)銘刻在我們幾個(gè)人的心頭。借此機(jī)會,特向去年為參加ACM亞洲賽而艱苦集訓(xùn)了近半年的各位老隊(duì)員表示感謝。

實(shí)際上，除了獲獎以外，在這次比賽期間還有一件事也讓我們記憶深刻。那是比賽當(dāng)天等待入場的時(shí)候，聽到某個(gè)學(xué)校的一個(gè)隊(duì)員在說：“有個(gè)學(xué)校的英文名很有意思，叫什么Hangzhou Dianzi University”. 哈哈，看來我們學(xué)校的英文名起的非常好，非常吸引人呀。

不過，事情的發(fā)展誰也沒有料到，隨著杭電英文校名的這一次曝光，影響越來越大，很多人開始對杭電英文校名進(jìn)行研究，不久以后甚至還成立了一個(gè)專門的研究機(jī)構(gòu)，叫做“HDU 校名研究會”。并不斷有報(bào)道說-相-當(dāng)-多的知名科學(xué)家改行，專門對該問題進(jìn)行研究，學(xué)術(shù)界稱之為“杭電現(xiàn)象”。很多人在國際知名期刊上發(fā)表了研究論文，這其中，尤以中國超級女科學(xué)家宇春小姐寫的一篇研究報(bào)告最為著名，報(bào)告發(fā)表在science上，標(biāo)題是“杭電為什么這樣紅？” 文中研究發(fā)現(xiàn)：Hangzhou Dianzi University這個(gè)校名具有深刻的哲學(xué)思想和內(nèi)涵，她同時(shí)提出了一個(gè)大膽的猜想：“假定一個(gè)字符串由m個(gè)H和n個(gè)D組成，從左到右掃描該串，如果字符H的累計(jì)數(shù)總是不小于字符D的累計(jì)數(shù),那么，滿足條件的字符串總數(shù)就恰好和下沙的沙粒一樣多。”

這就是當(dāng)今著名的“宇春猜想”！

雖然還沒能從數(shù)學(xué)上證明這個(gè)猜想的正確性，但據(jù)說美國方面在小布什的親自干預(yù)下，已經(jīng)用超級計(jì)算機(jī)驗(yàn)證了在（1<=n<=m<=1000000000000）時(shí)都是正確的。my god! 這是一個(gè)多么偉大的猜想！雖然我們以前總說，21世紀(jì)是屬于中國的，可還是沒想這一天來的這么早，自豪ing... + 感動ing...

感動和自豪之余，問題也來了，如果已知m和n的值，請計(jì)算下沙的沙粒到底有多少。

Ps:

1. 中國有關(guān)方面正在積極行動，著手為宇春小姐申報(bào)諾貝爾獎。

2、“宇春猜想”中提到的H和D組成的字符串現(xiàn)在被學(xué)術(shù)界成為“杭電串串”（“杭電串串”前不久被一個(gè)賣羊肉串的注冊了商標(biāo)，現(xiàn)在我校正在積極聯(lián)系買斷，據(jù)說賣方的底價(jià)是1000萬歐元，絕不打折，看來希望不大，sigh...）

Input

輸入數(shù)據(jù)包含多個(gè)測試實(shí)例，每個(gè)占一行，由兩個(gè)整數(shù)m和n組成，m和 n 分別表示字符串中H和D的個(gè)數(shù)。由于我們目前所使用的微機(jī)和老美的超級計(jì)算機(jī)沒法比，所以題目給定的數(shù)據(jù)范圍是（1<=n<=m<=20）。

Output

對于每個(gè)測試實(shí)例，請輸出下沙的沙粒到底有多少，計(jì)算規(guī)則請參考“宇春猜想”，每個(gè)實(shí)例的輸出占一行。

Sample Input

1 1

3 1

Sample Output

1

3

Author

lcy

Source

HDU 2006-4 Programming Contest

?

題目分析：

?

?

我的思路：

設(shè)由m個(gè)H和n個(gè)D組成的串有f(m,n)個(gè)，它是由m+n-1個(gè)再加上一個(gè)H或D組成的。

于是得遞推公式：

f(m,n)=f(m-1,n)+f(m,n-1);

下一步確定初始條件：

f(0,1)=0; f(1,0)=1.

另外，當(dāng)m<n時(shí)，f(m,n)=0; 當(dāng)m=0時(shí)，f(m,n)=0; 當(dāng)n=0時(shí)，f(m,n)=1.?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

??? int n,m,i,j;

??? __int64 f[22][22];

??? while(scanf("%d%d",&m,&n)!=EOF)

??? {

?????? for(i=0;i<=m;i++)

??????? for(j=0;j<=n;j++)

??????? {

????????? if((i==0)||(i<j))f[i][j]=0;

????????? else if(j==0)f[i][j]=1;

????????? else f[i][j]=f[i-1][j]+f[i][j-1];

??????? }

?????? printf("%I64d\n",f[m][n]);

??? }

??? return 0;

}?

PS：本題與1001類似，但不同的是，1001中拿50塊錢的人是不同的，所以交換位置也是一種排法；而本題中m個(gè)H是相同的，所以加進(jìn)的H無需與前m-1個(gè)H交換位置。另外，本題數(shù)據(jù)量比較小，因此更加簡單！

?

?

?

?

?

?

1006：錢幣兌換問題

Problem Description

在一個(gè)國家僅有1分，2分，3分硬幣，將錢N兌換成硬幣有很多種兌法。請你編程序計(jì)算出共有多少種兌法。

Input

每行只有一個(gè)正整數(shù)N，N小于32768。

Output

對應(yīng)每個(gè)輸入，輸出兌換方法數(shù)。

Sample Input

2934

12553

Sample Output

718831

13137761

Author

SmallBeer(CML)

Source

杭電ACM集訓(xùn)隊(duì)訓(xùn)練賽（VII）

?

?

題目分析：

?

我的思路：

假設(shè)數(shù)N/3得到的商為S，則可以分成S+1種大情況（即0~S個(gè)3）討論，對于每種大情況i (0<=i<=S)，設(shè)(N-i*3)/2=W, 則又可以分為W+1種小情況（即0~W個(gè)2），而每個(gè)小情況中2的個(gè)數(shù)X則為X種兌法，因?yàn)?和2確定后，1也確定了，此時(shí)即為一種兌法。

?

我的代碼如下：

?

#include<stdio.h>

int main()

{

??? int i,j,n,tempi,tempj;

??? __int64 f;

??? while(scanf("%d",&n)!=EOF)

? ??{

????? tempi=n/3;

????? f=0;

????? for(i=0;i<=tempi;i++)f+=(n-i*3)/2+1;

????? printf("%I64d\n",f);

??? }

??? return 0;

}?

?

?

?

1007：獻(xiàn)給杭電五十周年校慶的禮物

Problem Description

或許你曾經(jīng)牢騷滿腹

或許你依然心懷憂傷

或許你近在咫尺

或許你我天各一方

對于每一個(gè)學(xué)子

母校

永遠(yuǎn)航行在

生命的海洋

今年是我們杭電建校五十周年，這是一個(gè)值得祝福的日子。我們該送給母校一個(gè)怎樣的禮物呢？對于目前的大家來說，最好的禮物當(dāng)然是省賽中的好成績，我不能參賽，就送給學(xué)校一個(gè)DOOM III球形大蛋糕吧，這可是名牌，估計(jì)要花掉我半年的銀子呢。

想象著正式校慶那一天，校長親自操刀，把這個(gè)大蛋糕分給各地趕來祝賀的校友們，大家一定很高興，呵呵，流口水了吧...

等一等，吃蛋糕之前先考大家一個(gè)問題：如果校長大人在蛋糕上切了N刀（校長刀法極好，每一刀都是一個(gè)絕對的平面），最多可以把這個(gè)球形蛋糕切成幾塊呢？

做不出這個(gè)題目，沒有蛋糕吃的！

為-了-母-校-，為-了-蛋-糕-（不是為了DGMM，楓之羽最會浮想聯(lián)翩...），加-油-！

Input

輸入數(shù)據(jù)包含多個(gè)測試實(shí)例，每個(gè)實(shí)例占一行，每行包含一個(gè)整數(shù)n(1<=n<=1000)，表示切的刀數(shù)。

Output

對于每組輸入數(shù)據(jù)，請輸出對應(yīng)的蛋糕塊數(shù)，每個(gè)測試實(shí)例輸出一行。

Sample Input

1

2

3

Sample Output

2

4

8

Author

lcy

Source

杭電ACM集訓(xùn)隊(duì)訓(xùn)練賽（VIII）

?

?

題目分析：

?

我的思路：

這其實(shí)是考我們n個(gè)平面最多可以把空間分成幾個(gè)部分的問題。

使第n個(gè)平面與前面n-1個(gè)平面都相交，且交線都不重合，那么n-1條直線最多可以把平面劃分成為n(n-1)/2+1個(gè)部分

于是得遞推公式f(n)=f(n-1)+n(n-1)/2

初始條件：f(1)=2

?最后可以推出公式：f(n)=(n^3+5n+6)/6

?

我的代碼如下：

?

#include<stdio.h>

int main()

{

??? int n;

??? while(scanf("%d",&n)!=EOF)

????? printf("%d\n",(n*n*n+5*n+6)/6);

??? return 0;

}?

PS：空間是3維的，它跟三次多項(xiàng)式a*x^3+b*x^2+c*x+d有關(guān)，我們可以由4種特殊情況（例如x=1、2、3、4）列四個(gè)方程，解出系數(shù)a,b,c,d，從而求出最終公式！

?

?

?

?

?

?

1008：Children’s Queue

Problem Description

There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like

FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM

Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?

Input

There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (1<=n<=1000)

Output

For each test case, there is only one integer means the number of queue satisfied the headmaster’s needs.

Sample Input

1

2

3

Sample Output

1

2

4

Author

SmallBeer (CML)

Source

杭電ACM集訓(xùn)隊(duì)訓(xùn)練賽（VIII）

?

題目分析：

?

題目大意：

一個(gè)隊(duì)伍中有n個(gè)學(xué)生，但規(guī)定女生不能單獨(dú)站，也就是說，要么隊(duì)伍中沒有女生，要么有兩個(gè)或兩個(gè)以上的女生站在一起（這是保護(hù)弱勢力的體現(xiàn)！）。問有多少這樣的隊(duì)伍。

?

我的思路：

設(shè)n個(gè)學(xué)生生按規(guī)則排成的隊(duì)列有f(n)種，那么當(dāng)總?cè)藬?shù)少一個(gè)時(shí)會是什么情況呢？顯然，要么少一個(gè)男的，要么少一個(gè)女的。故有如下情況：

（1）??? 少一個(gè)男的，也就是說，第n個(gè)加進(jìn)去的是男生。此時(shí)，隊(duì)列n-1只需按規(guī)則站好即可，故有f(n-1)種方法。

（2）??? 少一個(gè)女的，也就是說，第n個(gè)加進(jìn)去的是女生。此時(shí)，前面的肯定不能是男生，因?yàn)楹竺婕舆M(jìn)去的女生只有一個(gè)，不符合規(guī)則，因此第n-1個(gè)(也就是前1個(gè))必須是女生。若n-2個(gè)是按規(guī)則站好的，則有f(n-2)種方法；若n-2個(gè)不是按規(guī)則站好的（因?yàn)榈趎-1,第n個(gè)是女生，所以第n-2個(gè)可以是女生，第n-3個(gè)可以是男生。當(dāng)沒加進(jìn)第n-1和第n個(gè)女生的時(shí)候，這是不合規(guī)則的），即第n-2個(gè)是女生，第n-3個(gè)是男生，此后第n-4個(gè)必須按規(guī)則站好，故有f(n-4)種方法。

于是得遞推公式：

f(n)=f(n-1)+f(n-2)+f(n-4);

下一步就要確定初始條件：

由于遞推公式有f(n-1)、f(n-2)和f(n-4)，故必須給出f(1)、f(2) 、f(3)和 f(4)

由題意得：f(1)=1；f(2) =2；f(3)=4； f(4)=7。

?

注意：由于本題數(shù)據(jù)量比較大，必須要用高精度，同時(shí)用數(shù)組保存結(jié)果來代替遞歸。

下面是我的代碼：

?

#include<stdio.h>

#define c 31

#define d 100000000

int main()

{

??? int n,i,j;

??? int f[1000][c]={0};

??? f[0][0]=1;

??? f[1][0]=2;

??? f[2][0]=4;

??? f[3][0]=7;

??? for(i=4;i<1000;i++)

??? {

????? for(j=0;j<c;j++)

??????? f[i][j]=f[i-1][j]+f[i-2][j]+f[i-4][j];

????? for(j=0;j<c-1;j++)

??????? if(f[i][j]>d)

??????? {

????????? f[i][j+1]+=f[i][j]/d;

????????? f[i][j]%=d;

?????? ?}

??? }

??? while(scanf("%d",&n)!=EOF)

??? {

????? for(i=c-1;i>0;i--)if(f[n-1][i]!=0)break;

????? printf("%d",f[n-1][i]);

????? for(j=i-1;j>=0;j--)printf("%08d",f[n-1][j]);

????? printf("\n");

??? }

??? return 0;

}?

?

?

?

?

?

?

1009：Counting Triangles

Problem Description

Given an equilateral triangle with n the length of its side, program to count how many triangles in it.

?

Input

The length n (n <= 500) of the equilateral triangle's side, one per line.

process to the end of the file

Output

The number of triangles in the equilateral triangle, one per line.

Sample Input

1

2

3

Sample Output

1

5

13

Author

JIANG, Jiefeng

Source

ZOJ Monthly, June 2003

?

?

題目分析：

?

題目大意：

邊長為n的等邊三角形由若干個(gè)邊長為1的等邊三角形組成，問它里面包含多少個(gè)等邊三角形（邊長從1到n，且有正立和倒立兩種情況）。

?

我的思路：

先分析幾個(gè)邊長小的等邊三角形的情況，借此得出遞推公式。

由于邊長>1的倒三角形比較難算，故分開討論

邊長???????????? ?????? 正三角形??????????? ?????? 邊長為1的倒三角????????? 邊長>1的倒三角形

1?????????????????? ?????? h(1)=1??????????????????????? g(1)=0????????????????????????????????????? 0

2?????????????????? ?????? h(2)=h(1)+3??????????????? g(2)=g(1)+1????????????????????????????? 0

3?????????????????? ?????? h(3)=h(2)+6??????????????? g(3)=g(2)+2????????????????????????????? 0

……

n?????????????????? h(n)=h(n-1)+ n*(n+1)/2???? g(n)=g(n-1)+n-1?????????????????????? ?

?

現(xiàn)在討論邊長>1的倒三角形數(shù)：

顯然當(dāng)邊長>=4時(shí)才有邊長>1的倒三角形。

邊長????? 底邊等分點(diǎn)數(shù)????????????????? 邊長為i（i>1）的倒三角形數(shù)量

4??????????? 4-1???????????????????????????????????? u(4)=(4-1)-2*(2-1)

5??????????? 5-1???????????????????????????????????? u(5)=u(4)+ (5-1)-2*(2-1)+ (5-1)-2*(3-1)

6??????????? 6-1???????????????????????????????????? u(6)=u(5)+ [(6-1)-2*(2-1)]+ [(6-1)-2*(3-1)]

……

n??????????? n-1???????? u(n)=u(n-1)+[(n-1)-2*(2-1)]+[(n-1)-2*(3-1)]+…+[(n-1)-2*(i-1)]+…

?

于是得遞推關(guān)系：

當(dāng)n<4時(shí)，f(n)=f(n-1)+n*(n+1)/2+(n-1);

當(dāng)n>=4時(shí)，f(n)=f(n-1)+n*(n+1)/2+(n-1)+u(n);

初始條件為: f(1)=1;

?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

?????? int n,i,j;

?????? __int64 f;

?????? while(scanf("%d",&n)!=EOF)

?????? {

?????? ? for(i=1;i<=n;i++)

????????????? if(i==1)f=1;

????????????? else

????????????? {

????????????? ? f+=i*(i+1)/2+(i-1);??????? //加上正立三角形數(shù)和邊長為1的倒三角形數(shù)

????????????? ? if(i>=4)

????????????? ??? for(j=3;i-j>=1;j+=2)f+=i-j;????? //當(dāng)n>=4時(shí)，加上邊長>1的倒三角形數(shù)

????????????? ? }

?????? ? printf("%I64d\n",f);

?????? }

?????? return 0;

}?

?

?

?

?

?

1010：Tiling a Grid With Dominoes

Problem Description

We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and 2 units wide may be tiled.

Write a program that takes as input the width, W, of the grid and outputs the number of different ways to tile a 4-by-W grid.

Input

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.

Each dataset contains a single decimal integer, the width, W, of the grid for this problem instance.

Output

For each problem instance, there is one line of output: The problem instance number as a decimal integer (start counting at one), a single space and the number of tilings of a 4-by-W grid. The values of W will be chosen so the count will fit in a 32-bit integer.

Sample Input

3

2

3

7

Sample Output

1 5

2 11

3 781

Source

2008 "Shun Yu Cup" Zhejiang Collegiate Programming Contest - Warm Up（1）

?

?

題目分析：

?

題目大意：

用1×2的多米諾骨牌，拼成4×w的矩形，總共有多少種方法？

?

我的思路：

此題與1002類似，但此題比1002復(fù)雜得多，用遞歸己經(jīng)不能解決問題了，但可以借鑒它的思想，再轉(zhuǎn)用數(shù)組存儲即可。先說一下它的思想：

設(shè)f(a,b,c,d)表示第一行覆蓋a格，第二行覆蓋b格，第三行覆蓋c格，第四行覆蓋d格時(shí)的方法數(shù)，當(dāng)拼成4*w的矩形時(shí)，有f(w,w,w,w)種方法。那么在此之前，它有哪些狀態(tài)呢？由于骨排要么是橫放要么是豎放，所以在取走第w列時(shí)，有下面幾種情況：（a=b=c=d=w）

（1）f(a-1,b-1,c-2,d-2);//第一行第二行是豎放的，另外兩行是橫放的，其他情況類似

（2）f(a-2,b-2,c-1,d-1);

（3）f(a-2,b-1,c-1,d-2);

（4）f(a-2,b-2,c-2,d-2);

（5）f(a-1,b-1,c-1,d-1);

現(xiàn)在又要考慮上面的情況又是怎么得來的：

對于（1），它是由f(a-2,b-2,c,d)和f(a-1,b-1,c,d)得來的；

對于（2），它是由f(a,b,c-1,d-1)和f(a,b,c-2,d-2)得來的；

對于（3），它是由f(a,b-2,c-2,d)和f(a,b-1,c-1,d)得來的；

對于（4）和（5），它跟a=b=c=d的情況一樣；

另外，還有一種情況：當(dāng)a=d且b=c且a>b時(shí)，它是由f(a-2,b,c,d-2)得來的。

下一步就要確定初始條件：

當(dāng)a=b=c=d<0時(shí)，f(a,b,c,d)=0;

當(dāng)a=b=c=d=0或者1時(shí)，f(a,b,c,d)=1;

當(dāng)a=b=0且c=d=1或者a=b=1且c=d=0時(shí)，f(a,b,c,d)=1;

當(dāng)a=d=0且b=c=1時(shí)，f(a,b,c,d)=1;

當(dāng)a=d=1且b=c=1時(shí)，f(a,b,c,d)=0;

剛才已經(jīng)說過，用遞歸會超時(shí)，所以要轉(zhuǎn)成數(shù)組來存儲，下面是數(shù)組的轉(zhuǎn)化：

以1表示己經(jīng)覆蓋，0表示未覆蓋，故每列均可由一個(gè)二進(jìn)制數(shù)表示，情況如下：

f[t][0]:0000

f[t][1]:0011

f[t][2]:0110

f[t][3]:1001

f[t][4]:1100

f[t][5]:1111

初始條件和狀態(tài)轉(zhuǎn)換均可參考上面的思想。

?

?

以下是我的代碼：

?

#include<stdio.h>

#define c 25

int main()

{

??? int n,w,t;

??? int f[c+1][7];

??? f[1][0]=f[1][1]=f[1][2]=f[1][4]=f[1][5]=1;

??? f[1][3]=0;

??? for(t=2;t<=c;t++)

??? {

???? f[t][0]=f[t-1][5];

???? f[t][1]=f[t-1][5]+f[t-1][4];

???? f[t][2]=f[t-1][5]+f[t-1][3];

???? f[t][3]=f[t-1][2];

???? f[t][4]=f[t-1][5]+f[t-1][1];

???? f[t][5]=f[t-1][0]+f[t-1][1]+f[t-1][2]+f[t-1][4]+f[t-1][5];????

? ???}

??? while(scanf("%d",&n)!=EOF)

??? {

????? int i=1;

????? while(n--)

????? {

??????? scanf("%d",&w);

??????? printf("%d %d\n",i++,f[w][5]);

????? }

??? }

??? return 0;

}?

?

?

?

由于時(shí)間有限，只分析以上10道題，以下10道題粘代碼

?

1011：漢諾塔V

Problem Description

用1,2,...,n表示n個(gè)盤子，稱為1號盤，2號盤,...。號數(shù)大盤子就大。經(jīng)典的漢諾塔問

題經(jīng)常作為一個(gè)遞歸的經(jīng)典例題存在。可能有人并不知道漢諾塔問題的典故。漢諾塔來源于

印度傳說的一個(gè)故事，上帝創(chuàng)造世界時(shí)作了三根金剛石柱子，在一根柱子上從下往上按大小

順序摞著64片黃金圓盤。上帝命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱

子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一回只能移動一個(gè)圓盤。我們

知道最少需要移動2^64-1次.在移動過程中發(fā)現(xiàn)，有的圓盤移動次數(shù)多，有的少 。 告之盤

子總數(shù)和盤號，計(jì)算該盤子的移動次數(shù).

Input

包含多組數(shù)據(jù)，首先輸入T,表示有T組數(shù)據(jù).每個(gè)數(shù)據(jù)一行，是盤子的數(shù)目N(1<=N<=60)和盤

號k(1<=k<=N)。

Output

對于每組數(shù)據(jù)，輸出一個(gè)數(shù)，到達(dá)目標(biāo)時(shí)k號盤需要的最少移動數(shù)。

Sample Input

2

60 1

3 1

Sample Output

576460752303423488

4

?

Author

Zhousc@ECJTU

Source

ECJTU 2008 Spring Contest

?

我的代碼如下：

?

#include<stdio.h>

#include<math.h>

int main()

{

??? int t,n,k;

??? __int64 f;

??? while(scanf("%d",&t)!=EOF)

??? while(t--)

??? {

?????? scanf("%d%d",&n,&k);

?????? f=(__int64)pow(2,n-k);

?????? printf("%I64d\n",f);

??? }

??? return 0;

}?

?

1012：漢諾塔VI

Problem Description

n個(gè)盤子的漢諾塔問題的最少移動次數(shù)是2^n-1,即在移動過程中會產(chǎn)生2^n個(gè)系列。由于

發(fā)生錯移產(chǎn)生的系列就增加了，這種錯誤是放錯了柱子，并不會把大盤放到小盤上，即各柱

子從下往上的大小仍保持如下關(guān)系 ：

n=m+p+q

a1>a2>...>am

b1>b2>...>bp

c1>c2>...>cq

計(jì)算所有會產(chǎn)生的系列總數(shù).

Input

包含多組數(shù)據(jù)，首先輸入T,表示有T組數(shù)據(jù).每個(gè)數(shù)據(jù)一行，是盤子的數(shù)

目N<30.

Output

對于每組數(shù)據(jù)，輸出移動過程中所有會產(chǎn)生的系列總數(shù)。

Sample Input

3

1

3

29

Sample Output

3

27

68630377364883

Author

Zhousc@ECJTU

Source

ECJTU 2008 Spring Contest

?

?

以下是我的代碼：

?

#include<stdio.h>

#include<math.h>

int main()

{

??? double f;

??? int t,n;

??? while(scanf("%d",&t)!=EOF)

??? while(t--)

??? {

????? scanf("%d",&n);

????? f=pow(3,n);

????? printf("%.0lf\n",f);

??? }

??? return 0;

}?

?

1013：蟠桃記

Problem Description

喜歡西游記的同學(xué)肯定都知道悟空偷吃蟠桃的故事，你們一定都覺得這猴子太鬧騰了，其實(shí)你們是有所不知：悟空是在研究一個(gè)數(shù)學(xué)問題！

什么問題？他研究的問題是蟠桃一共有多少個(gè)！

不過，到最后，他還是沒能解決這個(gè)難題，呵呵^-^

當(dāng)時(shí)的情況是這樣的：

第一天悟空吃掉桃子總數(shù)一半多一個(gè)，第二天又將剩下的桃子吃掉一半多一個(gè)，以后每天吃掉前一天剩下的一半多一個(gè)，到第n天準(zhǔn)備吃的時(shí)候只剩下一個(gè)桃子。聰明的你，請幫悟空算一下，他第一天開始吃的時(shí)候桃子一共有多少個(gè)呢？

Input

輸入數(shù)據(jù)有多組，每組占一行，包含一個(gè)正整數(shù)n（1<30>

Output

對于每組輸入數(shù)據(jù)，輸出第一天開始吃的時(shí)候桃子的總數(shù)，每個(gè)測試實(shí)例占一行。

Sample Input

2

4

Sample Output

4

22

Author

lcy

Source

C語言程序設(shè)計(jì)練習(xí)（二）

?

?

#include<stdio.h>

int main()

{

?????? int f,n;

?????? while(scanf("%d",&n)!=EOF)

?????? {

????????????? f=1;

????????????? while(n!=1)f=2*(f+1),n--;

????????????? printf("%d\n",f);

?????? }

?????? return 0;

}?

?

1014：超級樓梯

Problem Description

有一樓梯共M級，剛開始時(shí)你在第一級，若每次只能跨上一級或二級，要走上第M級，共有多少種走法？

Input

輸入數(shù)據(jù)首先包含一個(gè)整數(shù)N，表示測試實(shí)例的個(gè)數(shù)，然后是N行數(shù)據(jù)，每行包含一個(gè)整數(shù)M（1<=M<=40）,表示樓梯的級數(shù)。

Output

對于每個(gè)測試實(shí)例，請輸出不同走法的數(shù)量

Sample Input

2

2

3

Sample Output

1

2

Author

lcy

Source

2005實(shí)驗(yàn)班短學(xué)期考試

?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

?????? int s[41],n,m,i;

?????? while(scanf("%d",&n)!=EOF)

?????? while(n--)

?????? {

????????????? scanf("%d",&m);

????????????? for(i=0;i<m;i++)

????????????? {

????????????? ?if((i==0)||(i==1))s[i]=1;

?????? ????? else if(i>1)s[i]=s[i-1]+s[i-2];

????????????? }

????????????? printf("%d\n",s[m-1]);

?????? }

?????? return 0;

}?

?

?

1015：一只小蜜蜂...

Problem Description

有一只經(jīng)過訓(xùn)練的蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行。請編程計(jì)算蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)。

其中，蜂房的結(jié)構(gòu)如下所示。

Input

輸入數(shù)據(jù)的第一行是一個(gè)整數(shù)N,表示測試實(shí)例的個(gè)數(shù)，然后是N 行數(shù)據(jù)，每行包含兩個(gè)整數(shù)a和b(0<50>

Output

對于每個(gè)測試實(shí)例，請輸出蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)，每個(gè)實(shí)例的輸出占一行。

Sample Input

2

1 2

3 6

Sample Output

1

3

Author

lcy

Source

遞推求解專題練習(xí)（For Beginner）

?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

?????? int s[41],n,m,i;

?????? while(scanf("%d",&n)!=EOF)

?????? while(n--)

?????? {

????????????? scanf("%d",&m);

????????????? for(i=0;i<m;i++)

????????????? {

????????????? ?if((i==0)||(i==1))s[i]=1;

?????? ????? else if(i>1)s[i]=s[i-1]+s[i-2];

????????????? }

????????????? printf("%d\n",s[m-1]);

?????? }

?????? return 0;

}?

?

?

?

1016：不容易系列之(3)—— LELE的RPG難題

Problem Description

人稱“AC女之殺手”的超級偶像LELE最近忽然玩起了深沉，這可急壞了眾多“Cole”（LELE的粉絲,即"可樂"）,經(jīng)過多方打探，某資深Cole終于知道了原因，原來，LELE最近研究起了著名的RPG難題:

有排成一行的ｎ個(gè)方格，用紅(Red)、粉(Pink)、綠(Green)三色涂每個(gè)格子，每格涂一色，要求任何相鄰的方格不能同色，且首尾兩格也不同色．求全部的滿足要求的涂法.

以上就是著名的RPG難題.

如果你是Cole,我想你一定會想盡辦法幫助LELE解決這個(gè)問題的;如果不是,看在眾多漂亮的痛不欲生的Cole女的面子上,你也不會袖手旁觀吧?

Input

輸入數(shù)據(jù)包含多個(gè)測試實(shí)例,每個(gè)測試實(shí)例占一行,由一個(gè)整數(shù)N組成，(0<=50)。< P>

Output

對于每個(gè)測試實(shí)例，請輸出全部的滿足要求的涂法，每個(gè)實(shí)例的輸出占一行。

Sample Input

1

2

Sample Output

3

6

Author

lcy

Source

遞推求解專題練習(xí)（For Beginner）

?

?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

??? int n,i;

??? __int64 f[51];

?? ?while(scanf("%d",&n)!=EOF)

??? {

????? for(i=0;i<n;i++)

??????? if(i==0)f[i]=3;

??????? else if((i==1)||(i==2))f[i]=6;

??????? else f[i]=f[i-1]+2*f[i-2];

????? printf("%I64d\n",f[n-1]);

??? }

??? return 0;

}?

?

?

?

1017：阿牛的EOF牛肉串

Problem Description

今年的ACM暑期集訓(xùn)隊(duì)一共有18人，分為6支隊(duì)伍。其中有一個(gè)叫做EOF的隊(duì)伍，由04級的阿牛、XC以及05級的COY組成。在共同的集訓(xùn)生活中，大家建立了深厚的友誼，阿牛準(zhǔn)備做點(diǎn)什么來紀(jì)念這段激情燃燒的歲月，想了一想，阿牛從家里拿來了一塊上等的牛肉干，準(zhǔn)備在上面刻下一個(gè)長度為n的只由"E" "O" "F"三種字符組成的字符串（可以只有其中一種或兩種字符，但絕對不能有其他字符）,阿牛同時(shí)禁止在串中出現(xiàn)O相鄰的情況，他認(rèn)為，"OO"看起來就像發(fā)怒的眼睛，效果不好。

你，NEW ACMer,EOF的崇拜者，能幫阿牛算一下一共有多少種滿足要求的不同的字符串嗎？

PS: 阿牛還有一個(gè)小秘密，就是準(zhǔn)備把這個(gè)刻有 EOF的牛肉干，作為神秘禮物獻(xiàn)給杭電五十周年校慶，可以想象，當(dāng)校長接過這塊牛肉干的時(shí)候該有多高興！這里，請?jiān)试S我代表杭電的ACMer向阿牛表示感謝！

再次感謝！

Input

輸入數(shù)據(jù)包含多個(gè)測試實(shí)例,每個(gè)測試實(shí)例占一行,由一個(gè)整數(shù)n組成，(0<40>

Output

對于每個(gè)測試實(shí)例，請輸出全部的滿足要求的涂法，每個(gè)實(shí)例的輸出占一行。

Sample Input

1

2

Sample Output

3

8

Author

lcy

Source

遞推求解專題練習(xí)（For Beginner）

?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

??? int n,i;

??? __int64 f[41];

??? while(scanf("%d",&n)!=EOF)

??? {

????? for(i=0;i<n;i++)

?????? if(i==0)f[i]=3;

?????? else if(i==1)f[i]=8;

?????? else f[i]=2*(f[i-1]+f[i-2]);

????? printf("%I64d\n",f[n-1]);

??? }

??? return 0;

}?

?

?

?

1018：折線分割平面

Problem Description

我們看到過很多直線分割平面的題目，今天的這個(gè)題目稍微有些變化，我們要求的是n條折線分割平面的最大數(shù)目。比如，一條折線可以將平面分成兩部分，兩條折線最多可以將平面分成7部分，具體如下所示。

Input

輸入數(shù)據(jù)的第一行是一個(gè)整數(shù)C,表示測試實(shí)例的個(gè)數(shù)，然后是C 行數(shù)據(jù)，每行包含一個(gè)整數(shù)n(0<=10000),表示折線的數(shù)量。< P>

Output

對于每個(gè)測試實(shí)例，請輸出平面的最大分割數(shù)，每個(gè)實(shí)例的輸出占一行。

Sample Input

2

1

2

Sample Output

2

7

Author

lcy

Source

遞推求解專題練習(xí)（For Beginner）

?

?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

??? int c,n,i;

??? __int64 f;

??? while(scanf("%d",&c)!=EOF)

??? while(c--)

??? {

????? scanf("%d",&n);

????? for(i=1;i<=n;i++)

??????? if(i==1)f=2;

??????? else f+=4*i-3;

????? printf("%I64d\n",f);

??? }

??? return 0;

}?

?

?

1019：漢諾塔III

Problem Description

約19世紀(jì)末，在歐州的商店中出售一種智力玩具，在一塊銅板上有三根桿，最左邊的桿上自上而下、由小到大順序串著由64個(gè)圓盤構(gòu)成的塔。目的是將最左邊桿上的盤全部移到右邊的桿上，條件是一次只能移動一個(gè)盤，且不允許大盤放在小盤的上面。

現(xiàn)在我們改變游戲的玩法，不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間桿或從中間移出)，也不允許大盤放到下盤的上面。

Daisy已經(jīng)做過原來的漢諾塔問題和漢諾塔II，但碰到這個(gè)問題時(shí)，她想了很久都不能解決，現(xiàn)在請你幫助她。現(xiàn)在有N個(gè)圓盤，她至少多少次移動才能把這些圓盤從最左邊移到最右邊？

Input

包含多組數(shù)據(jù)，每次輸入一個(gè)N值(1<=N=35)。

Output

對于每組數(shù)據(jù)，輸出移動最小的次數(shù)。

Sample Input

1

3

12

Sample Output

2

26

531440

Author

Rabbit

Source

RPG專場練習(xí)賽

?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

??? __int64 f[36];

??? int n,i;

??? while(scanf("%d",&n)!=EOF)

??? {

??????? if(n==1)f[n]=2;

??????? else for(i=2;i<=n;i++)f[i]=3*f[i-1]+2;

??????? printf("%I64d\n",f[n]);

??? }

??? return 0;

}?

?

?

1020：跳舞毯

Problem Description

由于長期缺乏運(yùn)動，小黑發(fā)現(xiàn)自己的身材臃腫了許多，于是他想健身，更準(zhǔn)確地說是減肥。

小黑買來一塊圓形的毯子，把它們分成三等分，分別標(biāo)上A,B,C，稱之為“跳舞毯”，他的運(yùn)動方式是每次都從A開始跳，每次都可以任意跳到其他塊，但最后必須跳回A，且不能原地跳.為達(dá)到減肥效果，小黑每天都會堅(jiān)持跳n次，有天他突然想知道當(dāng)他跳n次時(shí)共幾種跳法，結(jié)果想了好幾天沒想出來－_－

現(xiàn)在就請你幫幫他，算出總共有多少跳法。

Input

測試輸入包含若干測試用例。每個(gè)測試用例占一行，表示n的值(1<=n<=1000)。

當(dāng)n為0時(shí)輸入結(jié)束。

Output

每個(gè)測試用例的輸出占一行，由于跳法非常多，輸出其對10000取模的結(jié)果.

Sample Input

2

3

4

0

Sample Output

2

2

6

Author

蔥頭

Source

2008信息工程學(xué)院集訓(xùn)隊(duì)——選拔賽

?

?

以下是我的代碼：

?

#include<stdio.h>

int main()

{

??? int n,i;

??? __int64 f[1001];

??? __int64 g[1001];

??? while(scanf("%d",&n)!=EOF&&n!=0)

??? {

????? for(i=0;i<n;i++)

?????? if(i==0)f[i]=0,g[i]=1;

?????? else if(i==1)f[i]=2,g[i]=1;

?????? else

?????? {

???????? f[i]=2*g[i-1]%10000;

???????? g[i]=(f[i-1]+g[i-1])%10000;

???????? }

????? printf("%I64d\n",f[n-1]);

??? }

??? return 0;

}?

總結(jié)

以上是生活随笔為你收集整理的ACM训练赛--递推专题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。