试题 G: 游园安排
本题总分：20 分
我的思路：
这题就是最长上升子序列
首先把单词分割开来，给定每个单词一个排序值，再求这个排序值数组的最长上升子序列
算法模板忘记咋写了，所以自己暴力模拟的，思路很暴躁
【问题描述】
L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。小蓝是 L 星球 游乐园的管理员。 为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系 统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始，后面跟 0 个或多个小写英文字母。游客可能重名。 小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部 分游客在上午游玩，其他的游客都在下午游玩，在上午游玩的游客要求按照预 约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的 名字。
一个名字 A 小于另一个名字 B 是指：存在一个整数 i，使得 A 的前 i 个字 母与 B 的前 i 个字母相同，且 A 的第 i+ 1 个字母小于 B 的第 i+ 1 个字母。（如 果 A 不存在第 i + 1 个字母且 B 存在第 i + 1 个字母，也视为 A 的第 i + 1 个字 母小于 B 的第 i + 1 个字母）
作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽 量多的游客游玩，请告诉小蓝让哪些游客上午游玩。如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案，请输出第一 个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。
【输入格式】
输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名
字之间没有字符分隔。
【输出格式】
按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。
【样例输入】
WoAiLanQiaoBei
【样例输出】
AiLanQiao
【评测用例规模与约定】
对于 20% 的评测数据，输入的总长度不超过 20 个字母。
对于 50% 的评测数据，输入的总长度不超过 300 个字母。
对于 70% 的评测数据，输入的总长度不超过 10000 个字母。
对于所有评测数据，每个名字的长度不超过 10 个字母，输入的总长度不超
过 1000000 个字母。
1. string scanfString[10000]; 2. string sortString[10000]; 3. int rankString[10000]; 4. int num; 5. int ansUp[10000]; 6. int ansLen; 7. int anssUp[10000]; 8. int anssLen; 9. // 求最长上升子序列 10. void calMaxUpSonArray() { 11. ansLen = 1; 12. ansUp[0] = rankString[0]; 13. anssLen = 1; 14. anssUp[0] = rankString[0]; 15. for (int k = 0; k < num; k++) { 16. ansLen = 1; 17. ansUp[0] = rankString[k]; 18. for (int i = k + 1; i < num; i++) { 19. if (rankString[i] < ansUp[ansLen - 1] && (ansLen == 1 || ansLen > 1 && rankString[i] >= ansUp[ansLen - 2])) { 20. ansUp[ansLen - 1] = rankString[i]; 21. } 22. else if (rankString[i] >= ansUp[ansLen - 1]) { 23. ansUp[ansLen] = rankString[i]; 24. ansLen++; 25. } 26. } 27. if (ansLen < anssLen) break; 28. else if (ansLen > anssLen) { 29. anssLen = ansLen; 30. for (int i = 0; i < ansLen; i++) { 31. anssUp[i] = ansUp[i]; 32. } 33. } 34. else { 35. bool flag = true; 36. for (int i = 0; i < ansLen; i++) { 37. if (ansUp[i] > anssUp[i]) { 38. flag = false; 39. break; 40. } 41. } 42. if (flag) { 43. for (int i = 0; i < ansLen; i++) { 44. anssUp[i] = ansUp[i]; 45. } 46. } 47. } 48. } 49. for (int i = 0; i < anssLen; i++) { 50. for (int j = 0; j < num; j++) { 51. if (rankString[j] == anssUp[i]) { 52. cout << scanfString[j]; 53. break; 54. } 55. } 56. } 57. cout << endl; 58. } 59. int main() { 60. string str; 61. while (cin >> str) { 62. num = 0; 63. string temp; 64. // 字符分解 65. for (int i = 0; i < str.length(); i++) { 66. if (str[i] >= 'A' && str[i] <= 'Z' && i > 0) { 67. scanfString[num] = temp; 68. sortString[num++] = temp; 69. temp = ""; 70. } 71. temp += str[i]; 72. } 73. scanfString[num] = temp; 74. sortString[num++] = temp; 75. sort(sortString, sortString + num); 76. // 排序后名次给rankString数组 77. for (int i = 0; i < num; i++) { // scanfString 78. for (int j = 0; j < num; j++) { // sortString 79. if (scanfString[i]._Equal(sortString[j])) { 80. rankString[i] = j; 81. break; 82. } 83. } 84. } 85. // 求最长上升子序列 86. calMaxUpSonArray(); 87. } 88. return 0; 89. }
试题 H: 答疑
本题总分：20 分
我的思路：
进入办公室的时间和答疑的时间可以看做一个整体
贪心，优先看总时间最少的，其次看答疑速度快的
比如进办公室+答疑时间5秒，离开5秒，肯定比 进办公室+答疑时间6秒，离开4秒划算
比如进办公室+答疑时间6秒，离开4秒，肯定比 进办公室+答疑时间4秒，离开7秒划算
【问题描述】
有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。 老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。
一位同学答疑的过程如下：
1. 首先进入办公室，编号为 i 的同学需要 si 毫秒的时间。
2. 然后同学问问题老师解答，编号为 i 的同学需要 ai 毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。
4. 最后同学收拾东西离开办公室，需要 ei 毫秒的时间。一般需要 10 秒、 20 秒或 30 秒，即 ei 取值为 10000，20000 或 30000。
一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。 答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群 里面发消息的时刻之和最小。
【输入格式】
输入第一行包含一个整数 n，表示同学的数量。
接下来 n 行，描述每位同学的时间。其中第 i 行包含三个整数 si, ai, ei，意
义如上所述。
【输出格式】
输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。
【样例输入】
3
10000 10000 10000
20000 50000 20000
30000 20000 30000
【样例输出】
280000
【样例说明】
按照 1, 3, 2 的顺序答疑，发消息的时间分别是 20000, 80000, 180000。
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ n ≤ 20。
对于 60% 的评测用例，1 ≤ n ≤ 200。
对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ si ≤ 60000，1 ≤ ai ≤ 1000000，
ei ∈ {10000, 20000, 30000}，即 ei 一定是 10000、20000、30000 之一。
1. struct ss { 2. long long a; 3. long long b; 4. }peo[1002]; 5. bool cmp(ss a, ss b) { 6. if ((a.a + a.b) != (b.a + b.b)) { 7. return (a.a + a.b) < (b.a + b.b); 8. } 9. return a.b > b.b; 10. } 11. int main() { 12. int n; 13. while (cin >> n) { 14. for (int i = 0; i < n; i++) { 15. long long aa, bb, cc; 16. cin >> aa >> bb >> cc; 17. peo[i].a = aa + bb; 18. peo[i].b = cc; 19. } 20. sort(peo, peo + n, cmp); 21. long long ans = 0; 22. long long nowTimes = 0; 23. for (int i = 0; i < n; i++) { 24. nowTimes += peo[i].a; 25. ans += nowTimes; 26. nowTimes += peo[i].b; 27. } 28. cout << ans << endl; 29. } 30. return 0; 31. }
试题 I: 出租车
本题总分：25 分
等待大神认领
【问题描述】
小蓝在 L 市开出租车。 L 市的规划很规整，所有的路都是正东西向或者正南北向的，道路都可以 看成直线段。东西向的道路互相平行，南北向的道路互相平行，任何一条东西 向道路垂直于任何一条南北向道路。
从北到南一共有 n 条东西向道路，依次标号为 H1, H2, · · · , Hn。从西到东一共有 m 条南北向的道路，依次标号为 S 1, S 2, · · · , S m。 每条道路都有足够长，每一条东西向道路和每一条南北向道路都相交，Hi 与 S j 的交叉路口记为 (i, j)。 从 H1 和 S 1 的交叉路口 (1, 1) 开始，向南遇到的路口与 (1, 1) 的距离分别 是 h1, h2, · · · , hnn1，向东遇到路口与 (1, 1) 的距离分别是 w1, w2, · · · , wmm1。 道路的每个路口都有一个红绿灯。
时刻 0 的时候，南北向绿灯亮，东西向红灯亮，南北向的绿灯会持续一段 时间（每个路口不同），然后南北向变成红灯，东西向变成绿灯，持续一段时间 后，再变成南北向绿灯，东西向红灯。 已知路口 (i, j) 的南北向绿灯每次持续的时间为 gi j，东西向的绿灯每次持 续的时间为 ri j，红绿灯的变换时间忽略。 当一辆车走到路口时，如果是绿灯，可以直行、左转或右转。如果是红灯， 可以右转，不能直行或左转。如果到路口的时候刚好由红灯变为绿灯，则视为 看到绿灯，如果刚好由绿灯变为红灯，则视为看到红灯。 每段道路都是双向道路，道路中间有隔离栏杆，在道路中间不能掉头，只 能在红绿灯路口掉头。掉头时不管是红灯还是绿灯都可以直接掉头。掉头的时间可以忽略。
小蓝时刻 0 从家出发。今天，他接到了 q 个预约的订单，他打算按照订单 的顺序依次完成这些订单，就回家休息。中途小蓝不准备再拉其他乘客。
小蓝的家在两个路口的中点，小蓝喜欢用 x1, y1, x2, y2 来表示自己家的位 置，即路口 (x1, y1) 到路口 (x2, y2) 之间的道路中点的右侧，保证两个路口相邻 （中间没有其他路口）。请注意当两个路口交换位置时，表达的是路的不同两边， 路中间有栏杆，因此这两个位置实际要走比较远才能到达。 小蓝的订单也是从某两个路口间的中点出发，到某两个路口间的中点结束。
小蓝必须按照给定的顺序处理订单，而且一个时刻只能处理一个订单，不能图 省时间而同时接两位乘客，也不能插队完成后面的订单。
小蓝只对 L 市比较熟，因此他只会在给定的 n 条东西向道路和 m 条南北向 道路上行驶，而且不会驶出 H1, Hn, S 1, S m 这几条道路所确定的矩形区域（可 以到边界）。
小蓝行车速度一直为 1，乘客上下车的时间忽略不计。
请问，小蓝最早什么时候能完成所有订单回到家。
【输入格式】
输入第一行包含两个整数 n, m，表示东西向道路的数量和南北向道路的数 量。
第二行包含 n n 1 个整数 h1, h2, · · · , hnn1。
第三行包含 m m 1 个整数 w1, w2, · · · , wmm1。
接下来 n 行，每行 m 个整数，描述每个路口南北向绿灯的时间，其中的第 i 行第 j 列表示 gi j。
接下来 n 行，每行 m 个整数，描述每个路口东西向绿灯的时间，其中的第 i 行第 j 列表示 ri j。
接下来一行包含四个整数 x1, y1, x2, y2，表示小蓝家的位置在路口 (x1, y1) 到路口 (x2, y2) 之间的道路中点的右侧。
接下来一行包含一个整数 q，表示订单数量。
接下来 q 行，每行描述一个订单，其中第 i 行包含八个整数 xi1, yi1, xi2, yi2, xi3, yi3, xi4, yi4，表示第 i 个订单的起点为路口 (xi1, yi1) 到路口 (xi2, yi2) 之间的道 路中点的右侧，第 i 个订单的终点为路口 (xi3, yi3) 到路口 (xi4, yi4) 之间的道路中 点的右侧。
【输出格式】
输出一个实数，表示小蓝完成所有订单最后回到家的最早时刻。四舍五入
保留一位小数。
【样例输入】
2 3
200
100 400
10 20 10
20 40 30
20 20 20
20 20 20
2 1 1 1
1
2 2 1 2 1 2 1 3
【样例输出】
1620.0
【样例说明】
小蓝有一个订单，他的行车路线如下图所示。其中 H 表示他家的位置，S
表示订单的起点，T 表示订单的终点。小明在最后回家时要在直行的红绿灯路
口等绿灯，等待时间为 20。
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n, m ≤ 5，1 ≤ q ≤ 10。
对于 50% 的评测用例，1 ≤ n, m ≤ 30，1 ≤ q ≤ 30。
对于所有评测用例，1 ≤ n, m ≤ 100，1 ≤ q ≤ 30，1 ≤ h1 < h2 < · · · < hnn1 ≤ 100000，1 ≤ w1 < w2 < · · · < wmm1 ≤ 100000，1 ≤ gi j ≤ 1000，1 ≤ ri j ≤ 1000，给 定的路口一定合法。
试题 J: 质数行者
本题总分：25 分
等待大神认领
【问题描述】
小蓝在玩一个叫质数行者的游戏。 游戏在一个 n × m × w 的立体方格图上进行，从北到南依次标号为第 1 行到 第 n 行，从西到东依次标号为第 1 列到第 m 列，从下到上依次标号为第 1 层到 第 w 层。
小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第 n 行第 m 列第 w 层。每一步，他可以向东走质数格、向南走质数格或者向上走质数格。每走到 一个位置，小蓝的角色要稍作停留。 在游戏中有两个陷阱，分别为第 r1 行第 c1 列第 h1 层和第 r2 行第 c2 列第 h2 层。这两个陷阱的位置可以跨过，但不能停留。也就是说，小蓝不能控制角 色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。 小蓝最近比较清闲，因此他想用不同的走法来完成这个游戏。所谓两个走法不同，是指小蓝稍作停留的位置集合不同。
请帮小蓝计算一下，他总共有多少种不同的走法。
提示：请注意内存限制，如果你的程序运行时超过内存限制将不得分。
【输入格式】
输入第一行包含两个整数 n, m, w，表示方格图的大小。
第二行包含 6 个整数，r1, c1, h1, r2, c2, h2，表示陷阱的位置。
【输出格式】
输出一行，包含一个整数，表示走法的数量。答案可能非常大，请输出答 案除以 1000000007 的余数。
【样例输入】
5 6 1
3 4 1 1 2 1
【样例输出】
11
【样例说明】
用 (r, c, h) 表示第 r 行第 c 列第 h 层，可能的走法有以下几种：
1. (1, 1, 1) ) (1, 3, 1) ) (1, 6, 1) ) (3, 6, 1) ) (5, 6, 1)。
2. (1, 1, 1) ) (1, 3, 1) ) (3, 3, 1) ) (3, 6, 1) ) (5, 6, 1)。
3. (1, 1, 1) ) (1, 3, 1) ) (3, 3, 1) ) (5, 3, 1) ) (5, 6, 1)。
4. (1, 1, 1) ) (3, 1, 1) ) (3, 3, 1) ) (3, 6, 1) ) (5, 6, 1)。
5. (1, 1, 1) ) (3, 1, 1) ) (3, 3, 1) ) (5, 3, 1) ) (5, 6, 1)。
6. (1, 1, 1) ) (3, 1, 1) ) (5, 1, 1) ) (5, 3, 1) ) (5, 6, 1)。
7. (1, 1, 1) ) (3, 1, 1) ) (5, 1, 1) ) (5, 4, 1) ) (5, 6, 1)。
8. (1, 1, 1) ) (1, 4, 1) ) (1, 6, 1) ) (3, 6, 1) ) (5, 6, 1)。
9. (1, 1, 1) ) (1, 6, 1) ) (3, 6, 1) ) (5, 6, 1)。
10. (1, 1, 1) ) (3, 1, 1) ) (3, 6, 1) ) (5, 6, 1)。
11. (1, 1, 1) ) (3, 1, 1) ) (5, 1, 1) ) (5, 6, 1)。
【评测用例规模与约定】
对于 30% 的评测用例 1 ≤ n, m,w ≤ 50。
对于 60% 的评测用例 1 ≤ n, m,w ≤ 300。
对于所有评测用例，1 ≤ n, m, w ≤ 1000，1 ≤ r1,r2 ≤ n, 1 ≤ c1, c2 ≤ m,
1 ≤ h1, h2 ≤ w，陷阱不在起点或终点，两个陷阱不同。
