一、数列（sequence.pas/c/cpp, 1s,128M）
【问题描述】
一个数列定义如下：f(1)=1，f(2)=1，f(n)=(A*f(n-1)+B*f(n-2))%7。给定A, B和n的值，要求计算f(n)的值。
【输入格式】
输入文件sequence.in仅一行，包含3个整数A, B和n，其中（1<=A, B<=1000，1<=n<=100,000,000）。
【输出格式】
输出文件sequence.out仅一行，一个整数，即f(n)的值。
【输入样例1】
1 1 3
【输出样例1】
2
【输入样例2】
1 2 10
【输出样例2】
5
【数据规模】
20%的数据：n<=1000；
40%的数据：n<=100,000；
100%的数据：n<=100,000,000；
二、最长路（path.pas/c/cpp, 1s,128M）
【问题描述】
设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当<i,j>为G的一条边时有i<j。设w(i,j)为边<i,j>的长度，请设计算法，计算图G中<1,n>间的最长路径。
【输入格式】
输入文件path.in的第一行有两个整数n和m，表示有n个顶点和m条边，其中2<=n<=1500，m<=50000；接下来m行中每行输入3个整数a, b, v表示从a点到b点有条边，边的长度为v。
【输出格式】
输出文件path.out，一个整数，即1到n之间的最长路径。如果1到n之间没连通，输出-1。
【输入样例1】
2 1
1 2 1
【输出样例1】
1
【输入样例2】
2 0
【输出样例2】
-1
【数据规模】
20%的数据：n<=100, m<=1000；
40%的数据：n<=1000, m<=10000；
100%的数据：n<=1500, m<=50000；
3．木棍（wooden.cpp/pas/c, 1s,128M）
【问题描述】
有n根木棍，每根的长度L和重量W已知。这些木棍将被一台机器一根一根地加工。机器需要一些启动时间来做准备工作，启时间与木棍被加工的具体情况有关。启动时间遵循以下规则：
1． 加工第一根木棍的启动时间为1分钟。
2． 加工完长度为L[i]，重量为W[i]的木棍后，紧跟着加工长度为L[i+1]，重量为W[i+1]的木棍，若L[i]<=L[i+1]且W[i]<=W[i+1]，则加工木棍i+1时，不需要启动时间。例如：有5根木棍，它们的长度和重量为(9,4),(2,5),(1,2),(5,3),(4,1)，则最小启动时间为2分钟（加工序列为(4,1),(5,3),(9,4),(1,2),(2,5)）。
【输入格式】
输入文件wooden.in的第一行是一个整数n（1<=n<=5000）,表示木棍的数量。第二行2*n个整数，L1,W1,L2,W2,……,Ln,Wn（1<=Li,Wi<=10000），为各木棍的长度和重量，这2*n个整数以若干个空格分隔。
【输出格式】
输出文件wooden.out仅一行一个整数，即最小总启动时间。
【样例输入1】
5
4 9 5 2 2 1 3 5 1 4
【样例输出1】
2
【样例输入2】
3
2 2 1 1 2 2
【样例输出2】
1
四、括号匹配（bracket.pas/c/cpp, 1s,128M）
【问题描述】
定义如下括号匹配序列：
1． 空序列是匹配序列；
2． 如果S是匹配序列，那么(S),[S],{S}和<S>也是匹配序列；
3． 如果A和B都是匹配序列，那么AB也是匹配序列。
例如，下面的字符串都是匹配序列：
()，[]，(())，([])，()[]，/em>()[()]，{{}}<>，([]<>{{}})，<<{}>>
而以下几个则不是：
(，[，]，)(，())，([()，<<，{(})，<{}>)
序列中可能包含通配符，含义如下：
/表示任意1个左括号
#表示任意2个左括号
@表示任意4个左括号
?表示任意8个左括号
\表示任意1个右括号
*表示任意2个右括号
&表示任意4个右括号
!表示任意8个右括号
现在，给你一些由“(”、“)”、“[”、 “]”、 “{”、“}”、“<”、“>”和通配符构成的序列。你要做的是判断该序列是否为匹配序列。
【输入格式】
第一行：一个正整数N，表示测试数据组数；
接下来N行：每行一个括号序列(长度不超过L)。
【输出格式】
共N行：对于每一个括号序列，判断其是否匹配。
对于不匹配的序列，直接输出FALSE。
对于匹配的序列，输出用单一空格隔开的3个信息：
第一个信息为TRUE；
第二个信息为括号的最大深度(层数)；
第三个信息为达到最大深度的次数。
【样例输入】
3
{()}@<>{})))>
([})
?\\\\\\\]
【样例输出】
TRUE 5 2
FALSE
TRUE 8 1
【样例解释】
对于第一组数据，@相当于<(((，是匹配的，括号的最大深度为5，该深度出现了2次。
对于第二组数据，[和}不匹配。
第三组数据想要说明的是通配符间可以匹配。
【数据规模】
对于20%的数据：N=1，0<L<=20；
对于60%的数据：0<N<=5，0<L<=2E+3；
对于100%的数据：0<N<=10，0<L<=2E+6；
对于40%的数据：序列中没有通配符。
Leave a Reply