新生赛暑假第一场 解题报告

未码出的题 C、D、E、F

超时的D、E

D题报告

D.Brackets 

This year MK is 5 years old. So he decides to learn some arithmetic. But he was confused by how to write the brackets. He has already known that the brackets should match when writing them correctly. Such as “()(())” is correct but “())(” is not.

The problem is that, if there are N pairs of brackets, how many ways that MK can write them correctly?           

Input 

   There are several test cases. Each case contains a number N (1 <= N <= 1000) indicating the pairs of brackets.

Output 

For each case, please output the answer mod 1,000,000,007.

Sample Input ：

5

7

Sample Output ：

42

429

代码

int n;
__64int f[maxn];
int main() {
    f[0] = 1;
    for(int i = 1; i <= 1000; i++) {
        for(int j = 0; j < i; j++) {
            f[i] += f[j] * f[i - j - 1] %1,000,000,007;
            f[i] %=1,000,000,007;
        }
    }
    while(scanf("%d", &n) == 1) {
        printf("%I64d\n", f[n]);
    }
    return 0;
}

原代码超时原因一、使用暴力法 二、每一处都mod所以大数越界；

总结：看要求超过100，000，000以上输入输出直接用c语言；测试数据为大数__int 64,还有用公式找关系。

公式为卡塔兰数

E题报告

E.Function

Define a function f(n)=(f(n-1)+1)/f(n-2). You already got f(1) and f(2). Now, give you a number m, please find the value of f(m).

Input

There are several test cases. Each case contains three integers indicating f(1), f(2) and m ( 1 <= f(1), f(2), m <= 1000,000,000).

Output

For each case, please output the value of f(m), rounded to 6 decimal places.

Sample Input

1 1 3

Sample Output

2．000000

代码：

int main()
{
	double f[5];
	long a,b,m;
	while(scanf("%ld %ld %ld",&a,&b,&m)!=EOF)
	{
		f[0]=a;
		f[1]=b;
		for(int i=2;i<5;i++)
		{
			f[i]=((f[i-1]+1)/f[i-2]);
		}
		printf("%.4lf\n",f[(m-1)%5]);
	}
	return 0;
}

总结：

原因基本与D的一样

最后总结：

加强算法了解和拓宽知识面，多熟悉复杂问题的分析。

7/7/2013 9:15 PM 第一次完稿。