题目：4.城市间紧急救援作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。时间限制：1000内存限制：65536输入输入第一行给出 4 个正整数 n、m、s、d，其中 n（2 ≤ n ≤ 500）是城市的个数，顺便假设城市的编号为 0 ~ (n-1)；m 是快速道路的条数；s 是出发地的城市编号；d是目的地的城市编号。 第二行给出 n个正整数，其中第 i 个数是第 i 个城市的救援队的数目，数字间以空格分隔。随后的 m 行中，每行给出一条快速道路的信息，分别是：城市 1、城市 2、快速道路的长度，中间用空格分开，数字均为整数且不超过 500。输入保证救援可行且最优解唯一。输出第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从 s 到 d 的路径中经过的城市编号。数字间以空格分隔。样例输入4 5 0 320 30 40 100 1 11 3 20 3 30 2 22 3 2样例输出2 600 1 3

题目：3.最短工期一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。时间限制：1000内存限制：65536输入首先第一行给出两个正整数：项目里程碑的数量 N（≤ 100）和任务总数 M。这里的里程碑从 0 到 N-1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。输出如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。样例输入样例#1：9 120 1 60 2 40 3 51 4 12 4 13 5 25 4 04 6 94 7 75 7 46 8 27 8 4样例#2：4 50 1 10 2 22 1 31 3 43 2 5样例输出样例#1：18样例#2：Impossible

题目：2.取帽子拼题er们觉得戴帽子会令自己看上去很帅，所以他们不管到哪里都会戴着帽子。有一天他们去到一家餐厅，服务员把他们的帽子收集了堆起来保管。当大家要离开的时候，发现帽子被像上图那样摞起来了。于是你的任务就是帮他们排好队，使得每个人都能按顺序顺利取到自己的帽子。已知每顶帽子的大小都不相同，并且帽子的尺寸跟帽子主人的体重有关 —— 越重的人戴的帽子就越大。时间限制：1000内存限制：65536输入输入第一行给出一个正整数 n (≤ 104)，为拼题er的人数。随后一行给出 n 个不同的帽子尺寸，为不超过 105 的正整数，顺序是从帽子堆的底部向上给出。最后一行给出 n 个不同的体重，顺序对应编号从 1 到 n 的拼题er。体重是不超过 106 的正整数。一行中的数字以空格分隔。输出在一行中按照取帽子的顺序输出帽子主人的编号。数字间以 1 个空格分隔，行首尾不得有多余空格。样例输入1012 19 13 11 15 18 17 14 16 2067 90 180 98 87 105 76 88 150 124样例输出3 4 8 6 10 2 1 5 9 7提示样例说明： 第一顶帽子的尺寸是最大的 20，所以对应第 3 个人的最大体重 180，于是第 3 个人排在最前面。 第二顶帽子的尺寸是第 6 小的 16，对应第 6 小的体重 98，是第 4 个人，于是第 4 个人下一个走。 以此类推。

题目：1.旅游规划有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。时间限制：1000内存限制：65536输入输入说明：输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2 ≤ n ≤ 500）是城市的个数，顺便假设城市的编号为 0~(n-1)；m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号。随后的 m 行中，每行给出一条高速公路的信息，分别是：城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 500。输入保证解的存在。输出在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。样例输入4 5 0 30 1 1 201 3 2 300 3 4 100 2 2 202 3 1 20样例输出3 40

题目：4.最多删除两个字符给定一个仅由小写英文字母组成的字符串，最多删两个字符后，能得到多少种不同的字符串？时间限制：5000内存限制：65536输入输入在一行中给出长度在区间 [3, 106] 内的仅由小写英文字母组成的字符串。输出在一行中输出最多删两个字符后所能得到的不同字符串的个数。样例输入ababcc样例输出15提示样例解释：1、删除 0 个字符后得到 `ababcc`；2、删除 1 个字符后得到 `babcc`, `aabcc`, `abbcc`, `abacc`, `ababc`；3、删除 2 个字符后得到 `abcc`, `bbcc`, `bacc`, `babc`, `aacc`, `aabc`, `abbc`, `abac`, `abab`。

题目：3.千手观音人类喜欢用 10 进制，大概是因为人类有一双手 10 根手指用于计数。于是在千手观音的世界里，数字都是 10 000 进制的，因为每位观音有 1 000 双手 ……千手观音们的每一根手指都对应一个符号（但是观音世界里的符号太难画了，我们暂且用小写英文字母串来代表），就好像人类用自己的 10 根手指对应 0 到 9 这 10 个数字。同样的，就像人类把这 10 个数字排列起来表示更大的数字一样，他们也把这些名字排列起来表示更大的数字，并且也遵循左边高位右边低位的规则，相邻名字间用一个点 `.` 分隔，例如 `pat.pta.cn` 表示千手观音世界里的一个 3 位数。人类不知道这些符号代表的数字的大小。不过幸运的是，人类发现了千手观音们留下的一串数字，并且有理由相信，这串数字是从小到大有序的！于是你的任务来了：请你根据这串有序的数字，推导出千手观音每只手代表的符号的相对顺序。注意：有可能无法根据这串数字得到全部的顺序，你只要尽量推出能得到的结果就好了。当若干根手指之间的相对顺序无法确定时，就暂且按它们的英文字典序升序排列。例如给定下面几个数字：patcnlao.cnlao.omspta.laopta.patcn.pat我们首先可以根据前两个数字推断 `pat` < `cn`；根据左边高位的顺序可以推断 `lao` < `pta` < `cn`；再根据高位相等时低位的顺序，可以推断出 `cn` < `oms`，`lao` < `pat`。综上我们得到两种可能的顺序：`lao` < `pat` < `pta` < `cn` < `oms`；或者 `lao` < `pta` < `pat` < `cn` < `oms`，即 `pat` 和 `pta` 之间的相对顺序无法确定，这时我们按字典序排列，得到 `lao` < `pat` < `pta` < `cn` < `oms`。时间限制：7000内存限制：65536输入输入第一行给出一个正整数 N (≤ 105)，为千手观音留下的数字的个数。随后 N 行，每行给出一个千手观音留下的数字，不超过 10 位数，每一位的符号用不超过 3 个小写英文字母表示，相邻两符号之间用 `.` 分隔。 我们假设给出的数字顺序在千手观音的世界里是严格递增的。题目保证数字是 104 进制的，即符号的种类肯定不超过 104 种。输出在一行中按大小递增序输出可推理出的符号，符号间仍然用 `.` 分隔。样例输入7patcnlao.cnlao.omspta.laopta.patcn.pat样例输出lao.pat.pta.cn.oms

题目：2.集体照拍集体照时队形很重要，这里对给定的 N 个人 K 排的队形设计排队规则如下：\- 每排人数为 N/K（向下取整），多出来的人全部站在最后一排；\- 后排所有人的个子都不比前排任何人矮；\- 每排中最高者站中间（中间位置为 m/2+1，其中 m 为该排人数，除法向下取整）；\- 每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；\- 若多人身高相同，则按名字的字典序升序排列。这里保证无重名。现给定一组拍照人，请编写程序输出他们的队形。时间限制：6000内存限制：65536输入每个输入包含 1 个测试用例。每个测试用例第 1 行给出两个正整数 N（≤ 104，总人数）和 K（≤ 10，总排数）。随后 N 行，每行给出一个人的名字（不包含空格、长度不超过 8 个英文字母）和身高（[30, 300] 区间内的整数）。输出输出拍照的队形。即 K 排人名，其间以空格分隔，行末不得有多余空格。注意：假设你面对拍照者，后排的人输出在上方，前排输出在下方。样例输入10 3Tom 188Mike 170Eva 168Tim 160Joe 190Ann 168Bob 175Nick 186Amy 160John 159样例输出Bob Tom Joe NickAnn Mike EvaTim Amy John

题目：1.City 不 City“City 不 City”因为一位外国友人保保熊直播旅游时总是用奇怪的腔调说“好 city，啊！”而走红中国社交网络，成为网络热梗。事实上，有一些叛逆的年轻人在旅行时会刻意避开网红打卡点，选择一些小众的特色地方小城镇，不追求 city，而喜欢说“好 country，啊”。下面给定各个城镇的旅游热度和城镇间的旅行花销，请你为前来咨询的旅行者规划一条最经济的路线，并且尽可能避开热度很高的网红点。时间限制：6000内存限制：65536输入输入第一行首先给出 4 个正整数：n 和 m（1 < n ≤ 103，1≤ m ≤ 5n），依次为城镇数量（于是城镇编号从 1 到 n）和城镇间的通路条数；s 和 t 依次为旅行者的出发地和目的地的城镇编号。 随后一行给出 n 个不超过 100 的正整数，依次为 n 个城镇的旅游热度。 再后面是 m 行，每行给出一条通路连接的两个城镇的编号、这条通路的最小花销（其数值为不超过 103 的正整数）。通路是双向的，题目保证任一对城镇间至多给出一条通路。 同一行的数字间均以空格分隔。输出题目要求从 s 到 t 的最小花销路线；若这样的路线不唯一，则取途径城镇的最高旅游热度值最小的那条路线。 在一行中输出从 s 到 t 的最小花销、以及途经城镇的最高旅游热度值（若没有途经的城镇，则热度值为 0）。数值间以 1 个空格分隔，行首尾不得有多余空格。 若从 s 根本走不到 t，则在一行中输出 `Impossible`。样例输入样例1：8 14 7 8100 20 30 10 50 80 100 1007 1 17 2 27 3 17 4 21 2 11 5 22 5 13 4 13 5 33 6 24 6 15 6 15 8 16 8 2样例2：3 1 1 210 20 301 3 1样例输出样例1：4 50样例2：Impossible提示样例1解释： 从 7 到 8 的最短路径有 3 条，其中 2 条都经过城镇 1，于是对应的最高旅游热度值是城镇 1 的热度值 100。解路径为 7->2->5->8，途径城镇 2 和 5，对应的最高旅游热度值是城镇 5 的热度值 50。在最短路径长度相等的情况下，取热度值小的解，故输出的热度值为 50。

题目：可怜的简单题 九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A: 1 . 最开始，数列 A 为空。 2 . 可怜会从区间 [1,n] 中等概率随机一个整数 i 加入到数列 A 中。 3 . 如果不存在一个大于 1 的正整数 w，满足 A 中所有元素都是 w 的倍数，数组 A 将会作为随机生成的结果返回。否则，可怜将会返回第二步，继续增加 A 的长度。 现在，可怜告诉了你数列 n 的值，她希望你计算返回的数列 A 的期望长度。 时间限制：60000 内存限制：1048576 输入 输入一行两个整数 n, p (1 ≤ n ≤ 1011, n < p ≤ 1012)，p 是一个质数。 输出 在一行中输出一个整数，表示答案对 p 取模的值。具体来说，假设答案的最简分数表示为 x/y，你需要输出最小的非负整数 z 满足 y × z ≡ x mod p。 样例输入 样例1： 2 998244353 样例2： 100000000 998244353 样例输出 样例1： 2 样例2： 3054970

题目：逆散列问题 给定长度为 N 的散列表，处理整数最常用的散列映射是 H(x) = x%N。如果我们决定用线性探测解决冲突问题，则给定一个顺序输入的整数序列后，我们可以很容易得到这些整数在散列表中的分布。例如我们将 1、2、3 顺序插入长度为 3 的散列表HT[]后，将得到HT[0]=3，HT[1]=1，HT[2]=2的结果。 但是现在要求解决的是“逆散列问题”，即给定整数在散列表中的分布，问这些整数是按什么顺序插入的？ 时间限制：5000 内存限制：65536 输入 输入的第一行是正整数 N（≤ 1000），为散列表的长度。第二行给出了 N 个整数，其间用空格分隔，每个整数在序列中的位置（第一个数位置为0）即是其在散列表中的位置，其中负数表示表中该位置没有元素。题目保证表中的非负整数是各不相同的。 输出 按照插入的顺序输出这些整数，其间用空格分隔，行首尾不能有多余的空格。注意：对应同一种分布结果，插入顺序有可能不唯一。例如按照顺序 3、2、1 插入长度为 3 的散列表，我们会得到跟 1、2、3 顺序插入一样的结果。在此规定：当前的插入有多种选择时，必须选择最小的数字，这样就保证了最终输出结果的唯一性。 样例输入 11 33 1 13 12 34 38 27 22 32 -1 21 样例输出 1 13 12 21 33 34 38 27 22 32