HDOJ(HDU) 1708 Fibonacci String

Problem Description
After little Jim learned Fibonacci Number in the class , he was very interest in it.
Now he is thinking about a new thing – Fibonacci String .

He defines : str[n] = str[n-1] + str[n-2] ( n > 1 )

He is so crazying that if someone gives him two strings str[0] and str[1], he will calculate the str[2],str[3],str[4] , str[5]….

For example :
If str[0] = “ab”; str[1] = “bc”;
he will get the result , str[2]=”abbc”, str[3]=”bcabbc” , str[4]=”abbcbcabbc” …………;

As the string is too long ,Jim can’t write down all the strings in paper. So he just want to know how many times each letter appears in Kth Fibonacci String . Can you help him ?

Input
The first line contains a integer N which indicates the number of test cases.
Then N cases follow.
In each case,there are two strings str[0], str[1] and a integer K (0 <= K < 50) which are separated by a blank.
The string in the input will only contains less than 30 low-case letters.

Output
For each case,you should count how many times each letter appears in the Kth Fibonacci String and print out them in the format “X:N”.
If you still have some questions, look the sample output carefully.
Please output a blank line after each test case.

To make the problem easier, you can assume the result will in the range of int.

Sample Input
1
ab bc 3

Sample Output
a:1
b:3
c:2
d:0
e:0
f:0
g:0
h:0
i:0
j:0
k:0
l:0
m:0
n:0
o:0
p:0
q:0
r:0
s:0
t:0
u:0
v:0
w:0
x:0
y:0
z:0

格式:每个案例后面都有一个空行!!!

不能直接用字符串相加来做,因为可能到后面会超内存!累加到后面的字符串太长了!!!

所以换位思考,既然是统计字母的个数,为什么不直接来建立整型数组呢。
只要统计出str0和str1中各个字母的个数就可以了。
后面各个字母个数的按照公式来推就行。

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        long num[][] = new long[56][26];
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            for(int i=0;i<num[0].length;i++){
                for(int j=0;j<num.length;j++){
                    num[j][i]=0;
                }
            }
            String str0 = sc.next();
            for(int i=0;i<str0.length();i++){
                for(int j='a';j<='z';j++){
                    if(str0.charAt(i)==(char)j){
                        num[0][j-'a']++;
                        break;
                    }
                }
            }
            String str1 = sc.next();
            for(int i=0;i<str1.length();i++){
                for(int j='a';j<='z';j++){
                    if(str1.charAt(i)==(char)j){
                        num[1][j-'a']++;
                        break;
                    }
                }
            }
            int n = sc.nextInt();
            for(int i=2;i<=n;i++){
                for(int k='a';k<='z';k++){
                    num[i][k-'a'] = num[i-1][k-'a']+num[i-2][k-'a'];
                }
            }

            for(int k='a';k<='z';k++){
                System.out.println((char)k+":"+num[n][k-'a']);
            }
            System.out.println();

        }
    }

}
时间: 2024-11-05 12:30:04

HDOJ(HDU) 1708 Fibonacci String的相关文章

HDOJ/HDU 2539 点球大战(String.endsWith()方法的一个应用~)

Problem Description 在足球比赛中,有不少赛事,例如世界杯淘汰赛和欧洲冠军联赛淘汰赛中,当比赛双方经过正规比赛和加时赛之后仍然不分胜负时,需要进行点球大战来决定谁能够获得最终的胜利.点球大战的规则非常简单,两方轮流派出球员罚点球,每方各罚5个.当5轮点球结束以后如果仍然不分胜负,则进入一轮定胜负的阶段.两方各派一名球员罚点球,直到有一方罚进而另一方没有进为止. 在北美职业冰球联赛中,也有点球大战.与足球的规则不同的是,它只先罚3轮点球,随后就进入一轮定胜负的阶段,而其他的规则完

hdu 3117 Fibonacci Numbers

点击此处即可传送到hdu 3117 **Fibonacci Numbers** Problem Description The Fibonacci sequence is the sequence of numbers such that every element is equal to the sum of the two previous elements, except for the first two elements f0 and f1 which are respectively

hdu 1568 Fibonacci

点击此处即可传送hdu 1568 **Fibonacci** Problem Description 2007年到来了.经过2006年一年的修炼,数学神童zouyu终于把0到100000000的Fibonacci数列 (f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2))的值全部给背了下来. 接下来,CodeStar决定要考考他,于是每问他一个数字,他就要把答案说出来,不过有的数字太长了.所以规定超过4位的只要说出前4位就可以了,可是CodeStar自己又记不住.于

hdu 1021 Fibonacci Again

点击此处即可传送hdu 1021 Fibonacci Again Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 44439 Accepted Submission(s): 21214 Problem Description There are another kind of Fibonacci numbers: F(0) = 7, F(1)

HDOJ/HDU 1250 Hat&amp;#39;s Fibonacci(大数~斐波拉契)

Problem Description A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1. F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4) Your task is to take

HDOJ(HDU) 2137 circumgyrate the string(此题用Java-AC不过!坑)

此题如果有用JavaACDSee,请评论,谢谢了. Problem Description Give you a string, just circumgyrate. The number N means you just circumgyrate the string N times, and each time you circumgyrate the string for 45 degree anticlockwise. Input In each case there is string

HDOJ/HDU 1161 Eddy&amp;#39;s mistakes(大写字母转换成小写字母)

Problem Description Eddy usually writes articles ,but he likes mixing the English letter uses, for example "computer science" is written frequently "coMpUtEr scIeNce" by him, this mistakes lets Eddy's English teacher be extremely disco

HDOJ/HDU 1087 Super Jumping! Jumping! Jumping!(经典DP~)

Problem Description Nowadays, a kind of chess game called "Super Jumping! Jumping! Jumping!" is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now. The game can be played by two or more t

HDOJ(HDU) 2061 Treasure the new start, freshmen!(水题、)

Problem Description background: A new semester comes , and the HDU also meets its 50th birthday. No matter what's your major, the only thing I want to tell you is:"Treasure the college life and seize the time." Most people thought that the colle