HDOJ1005 Number Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 84538    Accepted Submission(s): 20059

Problem Description
A number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n – 1) + B * f(n – 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

 

Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

 

Output
For each test case, print the value of f(n) on a single line.

 

Sample Input
1 1 3 1 2 10 0 0 0

 

Sample Output
2 5

 

===========================================
按照PPT里面的说法,就是“对于这种题目,千万不能蛮干!实际上,有经验的同学看到本题目的数据规模,很快就能知道:这类题目有规律可循。”
由于是mod7的关系,函数f两个参数,都是0~6范围内的,所以共计7*7=49种可能性,这是其一,避免重复计算。
其二,http://www.cnblogs.com/Lyush/archive/2011/09/04/2165927.html里面所说一般,这种东西肯定是有循环的,循环节最大50,何时找到循环呢?两个参数一样的时候呗。这个问题困扰了我一晚上,今天早上实在忍不住搜博客搜到了…所以自己还是太年轻了吧
这两点搞定了,就没有任何问题了。

ZOJ Problem Set – 1002

原题:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002

试水ZOJ的第一题,果然ACM的难度比PAT大一些,入门题目都那么长…

思路其实不难,弄个二维数组来搞,有点回溯的味道,刚巧最近看书看到了分而治之还要动态规划什么的

某一步的结果= max{当前位置放置1个+后面位置放置个数, 当前位置放置0个+后面位置放置个数}

然后就能做啦~

 

HDOJ-1097 A hard puzzle

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 23989    Accepted Submission(s): 8466

Problem Description
lcy gives a hard puzzle to feng5166,lwg,JGShining and Ignatius: gave a and b,how to know the a^b.everybody objects to this BT problem,so lcy makes the problem easier than begin.
this puzzle describes that: gave a and b,how to know the a^b’s the last digit number.But everybody is too lazy to slove this problem,so they remit to you who is wise.

 

Input
There are mutiple test cases. Each test cases consists of two numbers a and b(0<a,b<=2^30)

 

Output
For each test case, you should output the a^b’s last digit number.

 

Sample Input
7 66 8 800

 

Sample Output
9 6

==========================================
死搞肯定是要超时的….
其实一共9个数字,乘方都是有规律的..写的丑陋了点,不过能用就好^^