全国信息学奥林匹克联赛(noip2009)复赛

《全国信息学奥林匹克联赛(noip2009)复赛》由会员分享，可在线阅读，更多相关《全国信息学奥林匹克联赛(noip2009)复赛（8页珍藏版）》请在金锄头文库上搜索。

1、全国信息学奥林匹克联赛（NOIP2009）复赛 提高组第 1 页 共 8 页全国信息学奥林匹克联赛（全国信息学奥林匹克联赛（NOIP2009）复赛）复赛提高组（请选手务必仔细阅读本页内容）一题目概况中文题目名称潜伏者Hankson 的趣味题最优贸易靶形数独英文题目名称spysontradesudoku可执行文件名spysontradesudoku输入文件名spy.inson.intrade.insudoku.in输出文件名spy.outson.outtrade.outsudoku.out每个测试点时限1 秒1 秒1 秒2 秒测试点数目10101020每个测试点分值1010105附加样例文件有有

2、有有结果比较方式全文比较 过滤行末空格 及文末回车全文比较 过滤行末空格 及文末回车全文比较 过滤行末空格 及文末回车全文比较 过滤行末空格 及文末回车题目类型传统传统传统传统二提交源程序文件名对于 pascal 语言spy.passon.pastrade.passudoku.pas对于 C 语言spy.cson.ctrade.csudoku.c对于 C+语言spy.cppson.cpptrade.cppsudoku.cpp三编译命令（不包含任何优化开关）对于 pascal 语言fpc spy.pasfpc son.pasfpc trade.pasfpc sudoku.pas对于 C 语言gc

3、c o spy spy.c -lmgcc o son son.c -lmgcc o trade trade.c -lmgcc o sudoku sudoku.c -lm对于 C+语言g+ -o spy spy.cpp -lmg+ -o son son.cpp -lmg+ -o trade trade.cpp -lmg+ -o sudoku sudoku.cpp -lm四运行内存限制内存上限128M128M128M128M五注意事项 1、 文件名（程序名和输入输出文件名）必须使用小写。 2、 C/C+中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、 全国统

4、一评测时采用的机器配置为：CPU 1.9GHz，内存 1G，上述时限以此配置为准。 各省在自测时可根据具体配置调整时限。全国信息学奥林匹克联赛（NOIP2009）复赛 提高组第 2 页 共 8 页1.潜伏者潜伏者(spy.pas/c/cpp)【问题描述】 R 国和 S 国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。 历经艰险后，潜伏于 S 国的 R 国间谍小 C 终于摸清了 S 国军用密码的编码规则： 1、 S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后 所的内容均由大写字母AZ构成（无空格等其他字母） 。 2、 S 国对于每个字母规定了对应的“密字” 。

5、加密的过程就是将原信息中的所有字母 替换为其对应的“密字” 。 3、 每个字母只对应一个唯一的“密字” ，不同的字母对应不同的“密字” 。 “密字”可 以和原字母相同。 例如，若规定A的密字为A ， B的密字为C （其他字母及密字略） ，则原 信息“ABA”被加密为“ACA” 。 现在，小 C 通过内线掌握了 S 国网络上发送的一条加密信息及其对应的原信息。小 C 希望能通过这条信息，破译 S 国的军用密码。小 C 的破译过程是这样的：扫描原信息，对 于原信息中的字母 x（代表任一大写字母） ，找到其在加密信息中的对应大写字母 y，并认 为在密码里 y 是 x 的密字。如此进行下去直到停止于如

6、下的某个状态： 1、 所有信息扫描完毕， AZ所有 26 个字母在原信息中均出现过并获得了相 应的“密字” 。 2、 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。 3、 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反 S 过密码的编码规则） 。 例如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字” 的规则。 在小 C 忙得头昏脑胀之际，R 国司令部又发来电报，要求他翻译另外一条从 S 国刚刚 截取到的加密信息。现在请你帮助小 C：通过内线掌握的信息，尝试破译密码。然后利用 破译的密码，翻译电报中的加密信息。【输入】 输入文件名为 spy.in，共

7、3 行，每行为一个长度在 1 到 100 之间的字符串。 第 1 行为小 C 掌握的一条加密信息。 第 2 行为第 1 行的加密信息所对应的原信息。 第 3 行为 R 国司令部要求小 C 翻译的加密信息。 输入数据保证所有字符串仅由大写字母AZ构成，且第 1 行长度与第 2 行相 等。【输出】 输出文件 spy.out 共 1 行。 若破译密码停止时出现 2，3 两种情况，请你输出“Failed” （不含引号，注意首字母 大写，其它小写） 。 否则请输出利用密码翻译电报中加密信息后得到的原信息。全国信息学奥林匹克联赛（NOIP2009）复赛 提高组第 3 页 共 8 页【输入输出样例 1】 s

8、py.inspy.outAA AB EOWIEFailed【输入输出样例 1 说明】 原信息中的字母A和B对应相同的密字，输出“Failed” 。【输入输出样例 2】 spy.inspy.outQWERTYUIOPLKJHGFDSAZXCVBN ABCDEFGHIJKLMNOPQRSTUVWXY DSLIEWOFailed【输入输出样例 2 说明】 字母Z在原信息中没有出现，输出“Failed” 。【输入输出样例 3】 spy.inspy.outMSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP YIZSDWAHLNOVFUCERKJXQMGT

9、BPPKOIYKANZWPLLVWMQJFGQYLL FLSONOIP2.Hankson 的趣味题的趣味题(son.pas/c/cpp)【问题描述】 Hanks 博士是 BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫 Hankson。 现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。 今天在课堂上，老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小公倍数。 现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求 公倍数”之类问题的“逆问题” ，这个问题是这样的：已知正整数 a0,a1,b0,b1，设某未知正 整数 x

10、满足： 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 整除。全国信息学奥林匹克联赛（NOIP2009）复赛 提高

11、组第 4 页 共 8 页【输出】 输出文件 son.out 共 n 行。每组输入数据的输出结果占一行，为一个整数。 对于每组数据：若不存在这样的 x，请输出 0； 若存在这样的 x，请输出满足条件的 x 的个数；【输出输出样例】 son.inson.out2 41 1 96 288 95 1 37 17766 2【说明】 第一组输入数据，x 可以是 9、18、36、72、144、288，共有 6 个。 第二组输入数据，x 可以是 48、1776，共有 2 个。【数据范围】 对于 50%的数据，保证有 1a0，b1，b0，b110000 且 n100。 对于 100%的数据，保证有 1a0，b1

12、，b0，b12,000,000,000 且 n2000。3.最优贸易最优贸易(trade.pas/c/cpp)【问题描述】 C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个 城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分 为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。 C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的 价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。 商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息 之后，

13、便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城 市的标号从 1-n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游 的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸 易方式赚取旅费：他会选择一个经过的城市迈入他最喜欢的商品水晶球，并在之后经 过的另一个城市卖出这个水晶球。用赚取的差价当作旅费。由于阿龙主要是来 C 国旅游， 他决定这个贸易只进行最多一次。当然，在赚不到差价的情况下它就无需进行贸易。 假设 C 国有 5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路 为单向通行。双向箭头表

14、示这条道路为双向通行。31245全国信息学奥林匹克联赛（NOIP2009）复赛 提高组第 5 页 共 8 页假设 1n 号城市的水晶球价格分别为 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 条道路的信息（每条道路所连接的两个城市的编 号以及该条道路的通

15、行情况） 。请你告诉阿龙，他最多能赚钱多少旅费。【输入】 输入文件名为 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。【输出输出样例】 trade.intrade.out5 5 4 3 6 5 1 1 2 1 1 4 1 2 3 2 3 5 1 4 5 25【数据范围】 输入数据保证 1 号城市可以到达 n 号城市。 对于 10%的数据，1n6。 对于 30%的数据，1n100。 对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。 对于 100%的数据，1