2009年NOIP信息学奥赛提高组复赛C++真题

全国信息学奥林匹克联赛（ NOIP2009）复赛 提高组 第 1 页 共 7 页 全国信息学奥林匹克联赛（ NOIP2009）复赛 提高组 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 潜伏者 Hankson 的趣味题 最优贸易 靶形数独 英文题目名称 spy son trade sudoku 可执行文件名 spy son trade sudoku 输入文件名 spy.in son.in trade.in sudoku.in 输出文件名 spy.out son.out trade.out sudoku.out 每个测试点时限 1 秒 1 秒 1 秒 2 秒 测试点数目 10 10 10 20 每个测试点分值 10 10 10 5 附加样例文件 有 有 有 有 结果比较方式 全文比较 过滤行末空格 及文末回车 全文比较 过滤行末空格及 文末回车 全文比较 过滤行末空格 及文末回车 全文比较 过滤行末空格 及文末回车 题目类型 传统 传统 传统 传统 二．提交源程序文件名 对于pascal语言 spy.pas son.pas trade.pas sudoku.pas 对于C语言 spy.c son.c trade.c sudoku.c 对于C++语言 spy.cpp son.cpp trade.cpp sudoku.cpp 三．编译命令（不包含任何优化开关） 对于pascal语言 fpc spy.pas fpc son.pas fpc trade.pas fpc sudoku.pas 对于C语言 gcc -o spy spy.c -lm gcc -o son son.c -lm gcc -o trade trade.c -lm gcc -o sudoku sudoku.c -lm 对于C++语言 g++ -o spy spy.cpp -lm g++ -o son son.cpp -lm g++ -o trade trade.cpp -lm g++ -o sudoku sudoku.cpp -lm 四．运行内存限制 内存上限 128M 128M 128M 128M 注意事项： 1、文件名（程序名和输入输出文件名）必须使用小写。 2、C/C++中函数main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为： CPU 1.9GHz，内存1G，上述时限以此配置为准。各 省在自测时可根据具体配置调整时限。 全国信息学奥林匹克联赛（ NOIP2009）复赛 提高组 第 2 页 共 7 页 1．潜伏者 (spy.pas/c/cpp) 【问题描述】 R国和S国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。 历尽艰险后，潜伏于 S国的R国间谍小 C终于摸清了 S国军用密码的编码规则： 1． S国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所 得的内容均由大写字母‘ A’-‘Z’构成（无空格等其他字符） 。 2． S国对于每个字母规定了对应的“密字” 。加密的过程就是将原信息中的所有字母替 换为其对应的“密字” 。 3． 每个字母只对应一个