2015ACM-ICPC亚洲区沈阳站网赛(2/13)

maksyuki 发表于 比赛 分类,
0

J Jesus Is Here

Problem Description

I've sent Fang Fang around 201314 text messages in almost 5 years. Why can't she make sense of what I mean?
But Jesus is here!" the priest intoned. Show me your messages."
Fine, the first message is s1=‘‘c" and the second one is s2=‘‘ff".
The i-th message is si=si−2+si−1 afterwards. Let me give you some examples.
s3=‘‘cff", s4=‘‘ffcff" and s5=‘‘cffffcff".

I found the i-th message's utterly charming," Jesus said.
Look at the fifth message". s5=‘‘cffffcff" and two ‘‘cff" appear in it.
The distance between the first ‘‘cff" and the second one we said, is 5.
You are right, my friend," Jesus said. Love is patient, love is kind.
It does not envy, it does not boast, it is not proud. It does not dishonor others, it is not self-seeking, it is not easily angered, it keeps no record of wrongs.
Love does not delight in evil but rejoices with the truth.
It always protects, always trusts, always hopes, always perseveres."

Listen - look at him in the eye. I will find you, and count the sum of distance between each two different ‘‘cff" as substrings of the message.

Input

An integer T (1≤T≤100), indicating there are T test cases.
Following T lines, each line contain an integer n (3≤n≤201314), as the identifier of message.

Output

The output contains exactly T lines.
Each line contains an integer equaling to:

∑i<j:sn[i..i+2]=sn[j..j+2]=‘‘cff"(j−i) mod 530600414,

where sn as a string corresponding to the n-th message.

Sample Input

9
5
6
7
8
113
1205
199312
199401
201314

Sample Output

Case #1: 5
Case #2: 16
Case #3: 88
Case #4: 352
Case #5: 318505405
Case #6: 391786781
Case #7: 133875314
Case #8: 83347132
Case #9: 16520782

Source

2015 ACM/ICPC Asia Regional Shenyang Online

 

题目类型:线性DP

算法分析:使用dp[i]表示第i个序列中任意两个”cff”直接的距离和,则dp[i] = dp[i-2] + dp[i-1] + (第i - 2个序列与第i - 1个序列之间的距离和),此时易知初始条件是dp[1] = dp[2] = 0。令Si表示第i个序列中的”c”到这个序列的前端的总距离和,Leni表示第i个序列的长度,Ki表示第i个序列中”c”的个数,则序列间距离和为:

Ki-1 * (Ki-2 * Leni-2 - Si-2) + Ki-2 * Si-1

而Ki、Leni、Si都可以递推出来,其中Si = Si-2 + Si-1 + Leni-1,在递推求解时要注意取模!!!而且如果出现求解两个数差的模的话,此时要注意加上一个MOD再对MOD取模!!!

 

L Largest Point

Problem Description

Given the sequence A with n integers t1,t2,⋯,tn. Given the integral coefficients a and b. The fact that select two elements ti and tj of A and i≠j to maximize the value of at2i+btj, becomes the largest point.

Input

An positive integer T, indicating there are T test cases.
For each test case, the first line contains three integers corresponding to n (2≤n≤5×106), a (0≤|a|≤106) and b (0≤|b|≤106). The second line contains nintegers t1,t2,⋯,tn where 0≤|ti|≤106 for 1≤i≤n.

The sum of n for all cases would not be larger than 5×106.

Output

The output contains exactly T lines.
For each test case, you should output the maximum value of at2i+btj.

Sample Input

2

3 2 1
1 2 3

5 -1 0
-3 -3 0 3 3

Sample Output

Case #1: 20

Case #2: 0

Source

2015 ACM/ICPC Asia Regional Shenyang Online

 

题目类型:排序+枚举

算法分析:先将a* i ^ 2和b * i的值求出来,然后分别对点按照值从大到小排序,最后判断一次两个数组(分别存a*i^2和b*i的值)的第一个元素和第二个元素的值的相对大小关系,输出相对较大的那个值