2019年信息学奥赛CSP-S2提高级复赛C++真题day1

2019年CCF非专业级软件能力认证第二轮 提高级 2019 CCF CSP-S2 day1 时间：2019年11月16日08:3012:00 题目名称 格雷码 括号树 树上的数 题目类型 传统型 传统型 传统型 目录 code brackets tree 可执行文件名 code brackets tree 输入文件名 code.in brackets.in tree.in 输出文件名 code.out brackets.out tree.out 每个测试点时限 1.0秒 1.0秒 2.0秒 内存限制 256 MiB 256 MiB 256 MiB 子任务数目 20 20 20 测试点是否等分 是 是 是 提交源程序文件名 对于C++语言 code.cpp brackets.cpp tree.cpp 对于C 语言 code.c brackets.c tree.c 对于Pascal语言 code.pas brackets.pas tree.pas 编译选项 对于C++语言 -lm 对于C 语言 -lm 对于Pascal语言 注意事项与提醒（请选手务必仔细阅读） 1.文件名（程序名和输入输出文件名）必须使用英文小写。 2.C/C++中函数main()的返回值类型必须是 int，程序正常结束时的返回值必须 是0。 3.提交的程序代码文件的放置位置请参照各省的具体要求。 4.因违反以上三点而出现的错误或问题，申诉时一律不予受理。 5.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。 2019年CCF非专业级软件能力认证第二轮提高级 day1 6.程序可使用的栈内存空间限制与题目的内存限制一致。 7.全 国 统 一 评 测 时 采 用 的 机 器 配 置 为： Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz，内存32GB。上述时限以此配置为准。 8.只提供Linux格式附加样例文件。 9.评测在当前最新公布的 NOI Linux下进行，各语言的编译器版本以其为准。 10.最终评测时所用的编译命令中不含任何优化开关。 11. ∑ 是求和运算符， n∑ i=1 ai的值等于 a1+a2+


+an。 第2页 共 10页 2019年CCF非专业级软件能力认证第二轮提高级 day1格雷码（code） 格雷码（code） 【题目描述】 通常，人们习惯将所有 n位二进制串按照字典序排列，例如所有 2位二进制串按 字典序从小到大排列为： 00，01，10，11。 格雷码（Gray Code）是一种特殊的 n位二进制串排列法，它要求相邻的两个二进 制串间 . 恰 . 好有一位 . 不 . 同，特别地，第一个串与最后一个串也算作相邻。 所有2位二进制串按格雷码排列的一个例子为： 00，01，11，10。 n位格雷码不止一种，下面给出其中一种格雷码的生成算法： 1.1位格雷码由两个 1位二进制串组成，顺序为： 0，1。 2.n+ 1位格雷码的前 2 n 个二进制串，可以由依此算法生成的 n位格雷码（总共 2 n 个n位二进制串）按 . 顺