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取模！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const LL MOD = 530600414; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 2e5 + 6666; LL dp[maxn], k[maxn], len[maxn], s[maxn];; int main() { dp[1] = dp[2] = 0; k[1] = 1, k[2] = 0, len[1] = 1, len[2] = 2, s[1] = 0, s[2] = 0; for (int i = 3; i < maxn; i++) { dp[i] = dp[i-2] % MOD + dp[i-1] % MOD + ((k[i-1] % MOD) * ((((k[i-2] % MOD) * (len[i-2] % MOD)) % MOD - s[i-2] % MOD + MOD) % MOD)) % MOD + (k[i-2] % MOD) * (s[i-1] % MOD) % MOD; dp[i] %= MOD; s[i] = s[i-2] + s[i-1] + k[i-1] * len[i-2]; s[i] %= MOD; k[i] = k[i-2] + k[i-1]; k[i] %= MOD; len[i] = len[i-2] + len[i-1]; len[i] %= MOD; } // CPPFF; int t, flag = 1; cin >> t; while (t--) { int n; cin >> n; cout << "Case #" << flag++ << ": " << dp[n] <<endl; } return 0; } |
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的值)的第一个元素和第二个元素的值的相对大小关系，输出相对较大的那个值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 5e6 + 66; struct node { LL v, id; }; node aa[maxn], bb[maxn]; bool cmp (node aa, node bb) { return aa.v > bb.v; } int main() { // CFF; int t; int flag = 1; scanf ("%d",&t); while (t--) { printf ("Case #%d: ", flag++); LL a, b, n; scanf ("%lld%lld%lld", &n, &a, &b); for (int i = 1; i <= n; i++) { LL v; scanf ("%lld", &v); aa[i].v = a * v * v; aa[i].id = i; bb[i].v = b * v; bb[i].id = i; } sort (aa + 1, aa + 1 + n, cmp); sort (bb + 1, bb + 1 + n, cmp); if (aa[1].id != bb[1].id) printf ("%lld\n", aa[1].v + bb[1].v); else { LL ta = aa[1].v + bb[2].v; LL tb = aa[2].v + bb[1].v; printf ("%lld\n", max (ta, tb)); } } return 0; } |