ACM第3周周赛试题.doc

A：Max Sum of Max-K-sub-sequence（3415） Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 525????Accepted Submission(s): 51 Problem Description Given a circle sequence A[1],A[2],A[3]......A[n]. Circle sequence means the left neighbour of A[1] is A[n] , and the right neighbour of A[n] is A[1].Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K. ? Input The first line of the input contains an integer T(1=T=100) which means the number of test cases. Then T lines follow, each line starts with two integers N , K(1=N=100000 , 1=K=N), then N integers followed(all the integers are between -1000 and 1000). ? Output For each test case, you should output a line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them. ? Sample Input 4 6 3 6 -1 2 -6 5 -5 6 4 6 -1 2 -6 5 -5 6 3 -1 2 -6 5 -5 6 6 6 -1 -1 -1 -1 -1 -1 ? Sample Output 7 1 3 7 1 3 7 6 2 -1 1 1 B：Marriage Match IV Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 295????Accepted Submission(s): 38 Problem Description Do not sincere non-interference。Like that show, now starvae also take part in a show, but it take place between city A and B. Starvae is in city A and girls are in city B. Every time starvae can get to city B and make a data with a girl he likes. But there are two problems with it, one is starvae must get to B within least time, its said that he must take a shortest path. Other is no road can be taken more than once. While the city starvae passed away can been taken more than once. So, under a good RP, starvae may have many chances to get to city B. But he dont know how many chances at most h