求题解

2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 程小盟编程模拟赛 CSP-J/S 2022 第二轮认证 入门组 时间：2022 年10 月5 日08:30 ∼ 12:00 题目名称 国际象棋 新年礼物 最强大脑 推销员 题目类型 传统型 传统型 传统型 传统型 目录 chess gifts escape salesman 可执行文件名 chess gifts escape salesman 输入文件名 chess.in gifts.in escape.in salesman.in 输出文件名 chess.out gifts.out escape.out salesman.out 每个测试点时限 1.0 秒 1.0 秒 1.0 秒 1.0 秒 内存限制 128 MiB 128 MiB 128 MiB 128 MiB 子任务数目 10 10 10 10 测试点是否等分 是 是 是 是 提交源程序文件名 对于 C++ 语言 chess.cpp gifts.cpp escape.cpp salesman.cpp 编译选项 对于 C++ 语言 ‐O2 ‐lm 注意事项： 1. 文件名（程序名和输入输出文件名）必须使用英文小写。 2. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必 须是0。 3. 提交的程序代码文件的放置位置请参考各省的具体要求。 4. 因违反以上三点而出现的错误或问题，申述时一律不予受理。 5. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。 6. 程序可使用的栈空间内存限制与题目的内存限制一致。 7. 全国统一评测时采用的机器配置为：Inter(R) Core(TM) i7-8700K CPU @3.70GHz， 内存 32GB。上述时限以此配置为准。 8. 只提供 Linux 格式附加样例文件。 9. 评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准。 1 / 10 2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 2 / 10 国际象棋（chess） 【题目背景】 国际象棋（Chess），又称西洋棋，是一种二人对弈的棋类游戏。棋盘为正方 形，由64个黑白（深色与浅色）相间的格子组成；棋子分黑白（深色与浅色） 两方共32枚，每方各16枚。虽然汉语称之为西洋棋或国际象棋，但是实际上它 起源于亚洲，后由阿拉伯人传入欧洲，成为国际通行棋种，也是一项智力竞技 运动，曾被列为奥林匹克运动会正式比赛项目。 【题目描述】 国际象棋棋盘（如下图所示），有8行8列，在棋盘上有黑白相间的方格，各种 不同的棋子有不同的行棋规则。 小赖皮不会下国际象棋，但他想到一种新的玩法。他自己画了一个n*n的国际象 棋棋盘，在涂颜色的时候，他先把左下角涂上黑色，然后按照国际棋盘的样子 黑白间隔地涂好颜色。然后他在棋盘的下方为每一列标上序号，并在最下面一 排放上棋子（如图中红色圆圈所示），无论黑色和白色的格子都放。 棋子放好后就该走棋了，因为小赖皮太赖皮了，没人跟他一起玩，所以他的这 种玩法正好适合他自己玩。 第1轮行棋：将所有1的倍数的列上放着的棋子都往前走一步； 第2轮行棋：将所有2的倍数的列上放着的棋子都往前走一步； 第3轮行棋：将所有3的倍数的列上放着的棋子都往前走一步； …… 2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 3 / 10 2 1 8 4 第n轮行棋：将所有n的倍数的列上放着的棋子都往前走一步。 n轮行棋结束之后，他会数一数这个时候一共有多少个棋子在白色的格子上（如 果棋子还在棋盘上的话），然后就去吃西瓜了。 【输入格式】 从文件 chess.in 中读入数据。输 入只有一行，包括1个正整数n。 【输出格式】 输出到文件 chess.out 中。 输出只有一行，为行棋结束之后在白色格子上的棋子个数。 【样例 1 输入】 【样例 1 输出】 【样例 1 解释】 第1轮行棋，第1、2列棋子向前走1步；第2轮行棋，第2列棋子向前走1歩。此 时，第1列的棋子停留在白色格子，第2列的棋子走出了棋盘，因此答案是1。 【样例 2 输入】 【样例 2 输出】 2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 4 / 10 【样例 3】 见选手目录下的 chess / chess 3.in 与 chess / chess 3.ans。 【数据范围】 对于 30%的数据，2<=n<=10； 对于 80%的数据，2<=n<=5,000; 对于 100%的数据，2<=n<=1,000,000,000。 2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 5 / 10 新年礼物（gifts） 【题目背景】 过新年了，陈老师想给同学们买一些礼物寄给大家。 【题目描述】 因为今年NOIP比赛大家成绩都很好，为了奖励大家，在新年的时候陈老师想要从 网上买一些礼物寄给大家。陈老师调研了大家喜欢的礼物，并且一一上网查到了 商品的价格，统计出了一张表。 陈老师有n名学生，每名学生想要的礼物都有一个价格pi和邮费si，也就是说，购 买这件礼物需要付pi+si元。陈老师只有b元的预算，他想给尽量多的同学购买礼 物。陈老师在整理购物车的时候发现，tb也给了他一个新年礼物，那就是一张优 惠券。这张优惠券能够让一个商品以半价购买，既使用了优惠券的商品需要付 pi/2+si元。 【输入格式】 从文件 gifts.in 中读入数据。 第1行有2个正整数，表示共有n名学生和b元钱。 第2到n+1行，每行有两个正整数，分别代表这名同学想要的礼物的价格pi和邮 费si，数据保证pi一定为偶数。 【输出格式】 输出到文件 gifts.out 中。 输出一行一个整数，表示要陈老师能够购买的最多礼物数。 2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 6 / 10 5 24 4 2 2 0 8 1 6 3 12 5 4 【样例 1 输入】 【样例 1 输出】 【样例 1 解释】 共有5名学生，有24元的预算。如果给第1~4名同学购买礼物，并且在购买第三 名同学的礼物时使用优惠券的话，总共会花(4+2)+(2+0)+(4+1)+(6+3) = 22 元，满足预算。容易发现陈老师无法给全部5名同学都买礼物，因此答案为4。 需要注意的是，在给1~4名同学买礼物时，这张优惠券如果在第1名同学或第4名 同学的礼物上使用，也可以满足预算条件。 【样例 2】 见选手目录下的gifts / gifts 2.in 与 gifts / gifts 2.ans。 【样例 3】 见选手目录下的 gifts / gifts 3.in 与 gifts / gifts 3.ans。 【数据范围】 对于20%的数据，1 ≤ n ≤ 10，1 ≤ b，pi，si ≤ 1000； 对于60%的数据，1 ≤ n ≤ 5000，1 ≤ b，pi，si ≤ 10 9； 对于100%的数据，1 ≤ n ≤ 200000，1 ≤ b，pi，si ≤ 10 9。 2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 7 / 10 【题目背景】 最强大脑（escape） 大聪明是一个学霸，参加过最强大脑，可以在1秒内轻松计算100个10位数的加 法运算。但小糊涂是个学渣，连最基本的加法进位都算不对。 【题目描述】 小糊涂是大聪明最好的朋友，经常一起出去玩。一天，小糊涂和大聪明来到游乐 场，在游乐场里有一个游戏，一人出题一人算。出题的人在一堆数当中挑选一些出 来，算题的人如果能够在1秒钟之内将这些数的和计算正确的话，两个人就都能 够得到奖品。该项目还规定，出题人选出的数越多，计算正确后获得的奖品就越 好。 本来这个游戏很简单，只要小糊涂去出题，大聪明计算，他们一定能得到最好的 奖品。老板看出了这一点，就让大聪明去出题，让小糊涂算。大聪明知道小糊涂在 计算时如果有进位运算的话，肯定会算错，于是他想到了一个办法，要在老板给 出的数当中选择尽量多的数，而这些数在计算和的时候一定不能有进位，这样的 话小糊涂就不会算错了。 【输入格式】 从文件 escape.in 中读入数据。 第一行有1个正整数，表示老板给出的数字个数n。 第2行到第n+1行，每行一个正整数，代表老板给出的每一个数字ai。 【输出格式】 输出到文件 escape.out 中。 输出一行一个整数，表示大聪明能够选出的最多的数字是多少个。 2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 8 / 10 5 522 6 84 7311 19 3 【样例 1 输入】 【样例 1 输出】 【样例 1 解释】 老板一共给出了5个数字，分别是533、6、84、7311和19。如果选择522、6和 7311的话，在求和运算时就不会出现进位。容易看出大于3个数字的组合都会产 生进位，因此答案是3。 【样例 2】 见选手目录下的 escape / escape 2.in 与 t escape / escape 2.ans。 【数据范围】 对于100%的数据，1 ≤ n ≤ 20， 1 ≤ ai ≤ 100,000,000。 2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 9 / 10 推销员（salesman） 2022 CCF 非专业级软件能力认证 CSP-J/S 2022 第二轮认证 10 / 10