试题 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，陷阱不在起点或终点，两个陷阱不同。