万卷网

NOIP提高组

万卷网> 考级竞赛> 信息学奥赛> NOIP提高组

NOIP提高组

更新时间： 2023-09-02 20:23:05 试题数量： 316

我的练习

顺序练习

随机练习

章节练习

错题练习

题库预览

简答题字符串的展开【问题描述】在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或“4-8”的子串，我们就把它当作一种简写，输出时，用连续递增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：（1）遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照 ASCII 码的顺序，减号右边的字符严格大于左边的字符。（2）参数 p1：展开方式。p1=1 时，对于字母子串，填充小写字母；p1=2 时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3 时，不论是字母子串还是数字子串，都用与要填充的字母个数相同的星号“*”来填充。（3）参数 p2：填充字符的重复个数。p2=k 表示同一个字符要连续填充 k 个。例如，当 p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两侧的字符不变。（4）参数 p3：是否改为逆序：p3=1 表示维持原有顺序，p3=2 表示采用逆序输出，注意这时仍然不包括减号两端的字符。例如当 p1=1、p2=2、p3=2 时，子串“d-h”应扩展为“dggffeeh”。（5）如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照 ASCII 码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。【输入】输入文件 expand.in 包括两行：第 1 行为用空格隔开的 3 个正整数，依次表示参数 p1，p2，p3。第 2 行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。【输出】输出文件 expand.out 只有一行，为展开后的字符串。【输入输出样例 1】【输入输出样例 2】【输入输出样例 3】【限制】 40%的数据满足：字符串长度不超过 5 100%的数据满足：1<=p1<=3, 1<=p2<=8, 1<=p3<=2。字符串长度不超过 100

简答题靶形数独【问题描述】小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 1 到 9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域）每个格子为 9 分，再外面一圈（蓝色区域）每个格子为 8 分，蓝色区域外面一圈（棕色区域）每个格子为 7 分，最外面一圈（白色区域）每个格子为 6 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 2829。游戏规定，将以总分数的高低决出胜负。由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。【输入】输入文件名为 sudoku.in。一共 9 行。每行 9 个整数（每个数都在 0—9 的范围内），表示一个尚未填满的数独方格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。【输出】输出文件 sudoku.out 共 1 行。输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。【输入输出样例 1】【输入输出样例 2】【数据范围】40%的数据，数独中非 0 数的个数不少于 30。80%的数据，数独中非 0 数的个数不少于 26。100%的数据，数独中非 0 数的个数不少于 24。

简答题 Hankson 的趣味题【问题描述】Hanks 博士是 BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。今天在课堂上，老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a0,a1,b0,b1，设某未知正整数 x 满足：1． x 和 a0 的最大公约数是 a1；2． x 和 b0 的最小公倍数是 b1。Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后，他发现这样的x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。【输入】输入文件名为 son.in。第一行为一个正整数 n，表示有 n 组输入数据。接下来的 n 行每行一组输入数据，为四个正整数 a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证 a0 能被 a1 整除，b1 能被 b0 整除。【输出】输出文件 son.out 共 n 行。每组输入数据的输出结果占一行，为一个整数。对于每组数据：若不存在这样的 x，请输出 0；若存在这样的 x，请输出满足条件的 x 的个数【输入输出样例】【说明】第一组输入数据，x 可以是 9、18、36、72、144、288，共有 6 个。第二组输入数据，x 可以是 48、1776，共有 2 个。【数据范围】对于 50%的数据，保证有 1≤a0，a1，b0，b1≤10000 且 n≤100。对于 100%的数据，保证有 1≤a0，a1，b0，b1≤2,000,000,000 且 n≤2000。

简答题传纸条【问题描述】小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 0 表示），可以用一个 0-100 的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。【输入】输入文件 message.in 的第一行有 2 个用空格隔开的整数 m 和 n，表示班里有 m 行 n 列（1<=m,n<=50）。接下来的 m 行是一个 m*n 的矩阵，矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度。每行的 n 个整数之间用空格隔开。【输出】输出文件 message.out 共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。【输入输出样例】【限制】30%的数据满足：1<=m,n<=10100%的数据满足：1<=m,n<=50

简答题矩阵取数游戏【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 n*m 的矩阵，矩阵中的每个元素 aij均为非负整数。游戏规则如下：1. 每次取数时须从每行各取走一个元素，共 n 个。m 次后取完矩阵所有元素；2. 每次取走的各个元素只能是该元素所在行的行首或行尾；3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2i，其中 i 表示第 i 次取数（从 1 开始编号）；4. 游戏结束总得分为 m 次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。【输入】输入文件 game.in 包括 n+1 行：第 1 行为两个用空格隔开的整数 n 和 m。第 2~n+1 行为 n*m 矩阵，其中每行有 m 个用单个空格隔开的非负整数。【输出】输出文件 game.out 仅包含 1 行，为一个整数，即输入矩阵取数后的最大得分。【输入输出样例 1】【输入输出样例 1 解释】第 1 次：第 1 行取行首元素，第 2 行取行尾元素，本次得分为 1*21+2*21=6第 2 次：两行均取行首元素，本次得分为 2*22+3*22=20第 3 次：得分为 3*23+4*23=56。总得分为 6+20+56=82【输入输出样例 2】【输入输出样例 3】【限制】 60%的数据满足：1<=n, m<=30, 答案不超过 10^16 100%的数据满足：1<=n, m<=80, 0<=aij<=1000

简答题最优贸易【问题描述】C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城市的标号从 1~ n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。假设 C 国有 5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。假设 1~n 号城市的水晶球价格分别为 4，3，5，6，1。阿龙可以选择如下一条线路：1->2->3->5，并在 2 号城市以 3 的价格买入水晶球，在 3号城市以 5 的价格卖出水晶球，赚取的旅费数为 2。阿龙也可以选择如下一条线路 1->4->5->4->5，并在第 1 次到达 5 号城市时以 1 的价格买入水晶球，在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。【输入】输入文件名为 trade.in。第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间用一个空格隔开。如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市y 之间的双向道路。【输出】输出文件 trade.out 共 1 行，包含 1 个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出 0。【输入输出样例】【数据范围】输入数据保证 1 号城市可以到达 n 号城市。对于 10%的数据，1≤n≤6。对于 30%的数据，1≤n≤100。对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。对于 100%的数据，1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市水晶球价格≤100。

简答题树网的核【问题描述】设 T=(V, E, W) 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称 T 为树网（treenetwork），其中 V, E 分别表示结点与边的集合，W 表示各边长度的集合，并设 T 有 n 个结点。路径：树网中任何两结点 a,b 都存在唯一的一条简单路径，用 d(a,b)表示以 a,b 为端点的路径的长度，它是该路径上各边长度之和。我们称 d(a,b)为 a,b 两结点间的距离。一点 v 到一条路径 P 的距离为该点与 P 上的最近的结点的距离：d(v，P)=min{d(v，u)，u 为路径 P 上的结点}。树网的直径：树网中最长的路径称为树网的直径。对于给定的树网 T，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。偏心距 ECC(F)：树网 T 中距路径 F 最远的结点到路径 F 的距离，即任务：对于给定的树网 T=(V, E,W)和非负整数 s，求一个路径 F，它是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 s（可以等于 s），使偏心距 ECC(F)最小。我们称这个路径为树网 T=(V,E,W)的核（Core）。必要时，F 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。下面的图给出了树网的一个实例。图中，A-B 与 A-C 是两条直径，长度均为 20。点 W 是树网的中心，EF 边的长度为 5。如果指定 s=11，则树网的核为路径 DEFG（也可以取为路径 DEF），偏心距为 8。如果指定 s=0（或 s=1、s=2），则树网的核为结点 F，偏心距为 12。【输入】输入文件 core.in 包含 n 行：第 1 行，两个正整数 n 和 s，中间用一个空格隔开。其中 n 为树网结点的个数，s 为树网的核的长度的上界。设结点编号依次为 1, 2, ..., n。从第 2 行到第 n 行，每行给出 3 个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点 2 与 4 的边的长度为 7。所给的数据都是正确的，不必检验。【输出】输出文件 core.out 只有一个非负整数，为指定意义下的最小偏心距。【输入输出样例 1】【输入输出样例 2】【限制】 40%的数据满足：5<=n<=15 70%的数据满足：5<=n<=80 100%的数据满足：5<=n<=300, 0<=s<=1000。边长度为不超过 1000 的正整数

简答题统计数字【问题描述】某次科研调查时得到了 n 个自然数，每个数均不超过 1500000000（1.5*109）。已知不相同的数不超过 10000 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【输入】输入文件 count.in 包含 n+1 行：第 1 行是整数 n，表示自然数的个数。第 2~n+1 行每行一个自然数。【输出】输出文件 count.out 包含 m 行（m 为 n 个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。【输入输出样例】【限制】 40%的数据满足：1<=n<=1000 80%的数据满足：1<=n<=50000 100%的数据满足：1<=n<=200000，每个数均不超过 1 500 000 000（1.5*10^9）

简答题火柴棒等式【问题描述】给你 n 根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的 A、B、C 是用火柴棍拼出的整数（若该数非零，则最高位不能是 0）。用火柴棍拼数字 0-9 的拼法如图所示：注意：1. 加号与等号各自需要两根火柴棍2. 如果 A≠B，则 A+B=C 与 B+A=C 视为不同的等式（A、B、C>=0）3. n 根火柴棍必须全部用上【输入】输入文件 matches.in 共一行，又一个整数 n（n<=24）。【输出】输出文件 matches.out 共一行，表示能拼成的不同等式的数目。【输入输出样例 1】【输入输出样例 1 解释】2 个等式为 0+1=1 和 1+0=1。【输入输出样例 2】【输入输出样例 2 解释】9 个等式为：0+4=40+11=111+10=112+2=42+7=94+0=47+2=910+1=1111+0=11

简答题金明的预算方案【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 N 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1~5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第 j 件物品的价格为 v[j]，重要度为 w[j]，共选中了 k 件物品，编号依次为 j1，j2，„„，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ „+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件 budget.in 的第 1 行，为两个正整数，用一个空格隔开：N m（其中 N（<32000）表示总钱数，m（<60）为希望购买物品的个数。）从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数v p q（其中 v 表示该物品的价格（v<10000），p 表示该物品的重要度（1~5），q 表示该物品是主件还是附件。如果 q=0，表示该物品为主件，如果 q>0，表示该物品为附件，q 是所属主件的编号）【输出文件】输出文件 budget.out 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。【输入样例】1000 5800 2 0400 5 1300 5 1400 3 0500 2 0【输出样例】2200

简答题能量项链【问题描述】在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后释放的能量为（Mars 单位），新产生的珠子的头标记为 m，尾标记为 n。需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设 N=4，4 颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第 j，k 两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释放的能量为：(4⊕1)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。【输入文件】输入文件 energy.in 的第一行是一个正整数 N（4≤N≤100），表示项链上珠子的个数。第二行是 N 个用空格隔开的正整数，所有的数均不超过 1000。第 i 个数为第 i 颗珠子的头标记（1≤i≤N），当 i<N 时，第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。【输出文件】输出文件 energy.out 只有一行，是一个正整数 E（E≤2.1*），为一个最优聚合顺序所释放的总能量。【输入样例】 4 2 3 5 10【输出样例】710

简答题笨小猴【问题描述】笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这种方法的具体描述如下：假设 maxn 是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果 maxn-minn 是一个质数，那么笨小猴就认为这是个 Lucky Word，这样的单词很可能就是正确的答案。【输入】输入文件 word.in 只有一行，是一个单词，其中只可能出现小写字母，并且长度小于 100。【输出】输出文件 word.out 共两行，第一行是一个字符串，假设输入的的单词是 Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；第二行是一个整数，如果输入单词是 Lucky Word，输出 maxn-minn 的值，否则输出 0。【输入输出样例 1】【输入输出样例 1 解释】单词 error 中出现最多的字母 r 出现了 3 次，出现次数最少的字母出现了 1 次，3-1=2，2 是质数。【输入输出样例 2】【输入输出样例 2 解释】单词 olympic 中出现最多的字母 i 出现了 2 次，出现次数最少的字母出现了 1 次，2-1=1，1不是质数。

简答题作业调度方案【问题描述】我们现在要利用 m 台机器加工 n 个工件，每个工件都有 m 道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。每个工件的每个工序称为一个操作，我们用记号 j-k 表示一个操作，其中 j 为 1 到 n 中的某个数字，为工件号；k 为 1 到 m 中的某个数字，为工序号，例如 2-4 表示第 2 个工件第 4 道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。例如，当 n=3，m=2 时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第 1 个工件的第 1 个工序，再安排第 1 个工件的第 2 个工序，然后再安排第 2 个工件的第 1 个工序，等等。一方面，每个操作的安排都要满足以下的两个约束条件。(1) 对同一个工件，每道工序必须在它前面的工序完成后才能开始；(2) 同一时刻每一台机器至多只能加工一个工件。另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。例如，取 n=3,m=2，已知数据如下：则对于安排顺序“1 1 2 3 3 2”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10 与 12。当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。【输入文件】输入文件 jsp.in 的第 1 行为两个正整数，用一个空格隔开：m n（其中 m（<20）表示机器数，n（<20）表示工件数）第 2 行：m x n个用空格隔开的数，为给定的安排顺序。接下来的 2n 行，每行都是用空格隔开的 m 个正整数，每个数不超过 20。其中前 n 行依次表示每个工件的每个工序所使用的机器号，第 1 个数为第 1 个工序的机器号，第 2 个数为第 2 个工序机器号，等等。后 n 行依次表示每个工件的每个工序的加工时间。可以保证，以上各数据都是正确的，不必检验。【输出文件】输出文件 jsp.out 只有一个正整数，为最少的加工时间。【输入样例】2 31 1 2 3 3 21 2 1 2 2 13 2 2 5 2 4【输出样例】10

简答题双栈排序【问题描述】Tom 最近在研究一个有趣的排序问题。如图所示，通过 2 个栈 S1 和 S2，Tom 希望借助以下 4 种操作实现将输入序列升序排序。操作 d如果栈 S2 不为空，将 S2 栈顶元素弹出至输出序列如果一个 1~n 的排列 P 可以通过一系列操作使得输出序列为 1，2，…，(n-1)，n，Tom就称 P 是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列：<a,c,c,b,a,d,d,b>当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom 希望知道其中字典序最小的操作序列是什么。【输入】输入文件 twostack.in 的第一行是一个整数 n。第二行有 n 个用空格隔开的正整数，构成一个 1~n 的排列。【输出】输出文件 twostack.out 共一行，如果输入的排列不是“可双栈排序排列”，输出数字 0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。【输入输出样例 1】【输入输出样例 2】【输入输出样例 3】【限制】30%的数据满足： n<=1050%的数据满足： n<=50100%的数据满足： n<=1000

简答题潜伏者【问题描述】R 国和 S 国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。历尽艰险后，潜伏于 S 国的 R 国间谍小 C 终于摸清了 S 国军用密码的编码规则：1． S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所得的内容均由大写字母‘A’-‘Z’构成（无空格等其他字符）。2． S 国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替换为其对应的“密字”。3．每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。“密字”可以和原字母相同。例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信息“ABA”被加密为“ACA”。现在，小 C 通过内线掌握了 S 国网络上发送的一条加密信息及其对应的原信息。小 C希望能通过这条信息，破译 S 国的军用密码。小 C 的破译过程是这样的：扫描原信息，对于原信息中的字母 x（代表任一大写字母），找到其在加密信息中的对应大写字母 y，并认为在密码里 y 是 x 的密字。如此进行下去直到停止于如下的某个状态： 1．所有信息扫描完毕，‘A’-‘Z’ 所有 26 个字母在原信息中均出现过并获得了相应的“密字”。2．所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。3．扫描中发现掌握的信息里有明显的自相矛盾或错误（违反 S 国密码的编码规则）。例如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。在小 C 忙得头昏脑涨之际，R 国司令部又发来电报，要求他翻译另外一条从 S 国刚刚截取到的加密信息。现在请你帮助小 C：通过内线掌握的信息，尝试破译密码。然后利用破译的密码，翻译电报中的加密信息。【输入】输入文件名为 spy.in，共 3 行，每行为一个长度在 1 到 100 之间的字符串。第 1 行为小 C 掌握的一条加密信息。第 2 行为第 1 行的加密信息所对应的原信息。第 3 行为 R 国司令部要求小 C 翻译的加密信息。输入数据保证所有字符串仅由大写字母‘A’-‘Z’构成，且第 1 行长度与第 2 行相等。【输出】输出文件 spy.out 共 1 行。若破译密码停止时出现 2，3 两种情况，请你输出“Failed”（不含引号，注意首字母大写，其它小写）。否则请输出利用密码翻译电报中加密信息后得到的原信息。【输入输出样例 1】【输入输出样例 1 说明】原信息中的字母‘A’和‘B’对应相同的密字，输出“Failed”。【输入输出样例 2】【输入输出样例 2 说明】字母‘Z’在原信息中没有出现，输出“Failed”。【输入输出样例 3】