冲刺NOIP2008模拟题十.doc

如有侵权，请联系网站删除，仅供学习与交流冲刺NOIP2008模拟题十【精品文档】第 5 页冲刺NOIP2008模拟题十江苏省常州高级中学 曹文题目字母转换素数路工作序列集合堆栈电脑源程序名trans.?prime.?print.?stack.?输入文件名trans.inprime.inprint.instack.in输出文件名trans.outprime.outprint.outstack.out测试点时限1s1s1s1s一、字母转换 【问题描述】 26个大写字母的一个置换可以用一个长 度为26的字符串表示，比如说：HRSLCZDKIYXUNOMTGVJEFAWBPQ这表示，把A替换成H，把B替换成R 把Z替换成Q。 把这个置换操作两次，我们可以得到一个新的置换。比如上面这个置换，第一次操作，我们把A变成了H，接着对H进行置换，就变成了K。所以，在新的置换中，A将被替换成K。 这个新的置换也可以用一个长度为26的字符串表示。 现在的问题就是，给了你一个用26个字母组成的字符串，判断它是否是某个置换操作两次之后的结果。 【输入格式】 一行包含26个不相同的大写字母的字符串。 【输出格式】 如果存在某个置换操作两次之后可以成为输入中的字符串所表示的置换，则输出Yes，否则输出N。 样例 【输入】 CVBTOKWRIMDNSYUAXCQZPFJHLE【输出】Yes 二、素数路 【问题描述】 内阁大臣非常沮丧，他收到了安全部长的消息：他们都需要改变办公室的四位房间号码。 安全部长：经常换换房间号码是出于安全方面的考虑，可以让敌人陷入迷惑。 内阁大臣：但是，我选择1033作为我的房间号是出于我个人的偏爱。我可是内阁大臣！ 安全部长：你不就是喜欢素数么？我们给你安排了8179这个号码，你只需要贴四个新数字覆盖住以前的四个老数字就可以了。 内阁大臣：不行，没有那么容易。当我把1033的1用8盖住的时候，8033可不是个素数！ 安全部长：我知道，你不能允许你的门上出现非素数。 内阁大臣：正确！所以我必须找到一个方法从1033修改到8179，使得过程中门上出现的永远是素数，而且每次只能够修改当前数字的一位。 这个时候，在旁边偷听的财政大臣忍不住来插嘴。 财政大臣：千万不要为了这么个事情增加不必要的开支！我知道换一个数字就是要花一镑！ 内阁大臣：那我需要一个计算机来规划一下。 财政大臣：我能够帮你！ 现在这个任务就交给你了。你要从一个四位的素数出发，每次修改其中的一位，并且要保证修改的结果还是一个素数，还不能出现前导零。你要找到一个修改次数最少的方案，得到我们所需要的素数。 关于1033怎么变到8179，这里是一个最短的方案： 1033 1733 3733 3739 3779 8779 8179 修改了6次，所以要花6镑。 【输入格式】 一行，两个四位的素数（没有前导零），表示初始数和目标数。 【输出格式】 一个数，表示最少的操作次数。如果不可能，输出“Impossible”。 【样例】 【输入】1033 8179 【输出】6 三、工作序列 【问题描述】 有n个工作排成一个队列，每个工作有一个优先级，优先级是一个l到9之间的整数。 处理这些工作的流程如下： 1把队头的工作取出。 2如果队列中有哪个工作的优先级比取出的这个工作要高，则把这个工作放到队尾去。 3否则，执行这个工作，不再放回队列。 按照一开始在队列中的位置，这些工作从左到右以0，l，2，n-l编号。告诉你每个工作的优先级，需要你求出一开始编号为m的工作是第几个被执行的。 【输入格式】 第一行两个数n和m，n是队列中工作的个数，保证lnl00，m是我所关心的那个工作的最初编号。保证0mn-l。 第二行n个l到9的整数，按顺序表示了n个工作的优先级。 【输出格式】 一个整数，表示我所关心的那个工作是第几个被执行的。【样例】【输入】4 21 2 3 4【输出】2 四、集合堆栈电脑 【问题描述】 wikipedia上提供的一段背景资料：“集合理论是数学理论的一个分支，它主要由德国数学家Georg cantor在19世纪末创立。集合理论已经逐渐成为现代数学的基本理论。正式的集合理论学说为数学证明的严格性提供了保障。 一些古怪的理论工作者开始构造一个超级计算机，用来实现集合之间的操作，而不再是数字之间的操作。他们希望你来帮他们模拟一下集合运算的过程。 计算机的操作对象是一个以集合为元素的栈，一开始这个栈是空的。在每一步操作之后，栈顶集合中所含元素的个数是需要你输出的东西。计算机的操作指令有PUSH，DUP，UNION，INTERSECT，ADD。 ·PUSH操作将一个空集合入栈 ·DUP操作将把一个和栈顶元素相同的集合入栈 ·UNION操作进行两次出栈操作，并且把出栈的两个集合的并集入栈 ·INTERSECT操作进行两次出栈操作，并且把出栈的两个集合的交集入栈 ·ADD操作进行两次出栈操作，并且把第一个出栈的集合作为一个元素，放入第二个出栈的集合中，然后把这个结果入栈 举一个例子，假设栈顶的元素是A=，而它下面的一个元素是B=。 显然，集合A有2个元素，集合B也是。 对于这个情况： ·UNION操作会产生集合，这个集合有3个元素，所以要输出3 ·INTERSECT操作会产生，所以要输出1 ·ADD操作会产生，所以要输出3 【输人格式】 第一行一个整数N，保证0N2000。 接着的N行，每行有一条指令。保证输入的指令是合法的，不会出现让你在一个空的栈中弹出元素的情况。 【输出格式】 对于输入中的每一条指令，输出执行指令之后栈顶集合里的元素个数。 【样例】 【输入】 9 PUSH DUP ADD PUSH ' ADD DUP ADD DUP UNION 【输出】 0 0 1 0 1 l 2 2 2