少儿信息学复赛四题解析：枚举、前缀和与freopen细节

简介：面向小学阶段信息学竞赛选手与指导教师的复赛真题文档，收录第18届绍兴市少儿信息学竞赛复赛完整试题，适合用于赛前模拟、课堂练习与算法专题训练。资源包共1个docx文件，约32KB，核心内容围绕“好朋友”“统计人口”“卫星”“粉刷匠”四道编程题展开，配有题目一览、输入输出格式、样例与样例解释、数据范围、150分钟考试设置以及比赛目录和提交注意事项，能够较完整地还原小学信息学复赛的题型结构与难度梯度。已有815人学习，读者可据此练习变量与控制结构、数组与链表、环状模拟、行列染色统计等知识点，并对照官方格式训练程序读写与文件命名规范；对教师而言，也便于拆解算法设计思路、组织讲评和查漏补缺。

1. 一份被 Word 吞掉空格的复赛真题，四道题刚好卡在「会语法」和「会做题」之间

第18届某市少儿信息学竞赛复赛试题，150 分钟，四道题，每题 10 个测试点各 10 分，题面文件名是 friend、people、star、paint。它不属于 NOIP 提高组那种难度，但对小学高年级到初中刚开始接触信息学、准备 NOIP 编程入门的孩子来说，这套卷子正好卡在「语法都会写」和「题能拿满分」之间的分水岭上：好朋友考枚举的顺序，统计人口考前缀和，卫星考约瑟夫环的逆推，粉刷匠考倒序思维加常数优化。四道题没有一道需要高级数据结构，但每一道都埋了能让人从 100 分掉到 30 分的细节。

我把它整份拆了一遍，包括那份从 docx 里复制出来时被 Word 吃掉空格的样例数据。下面按「文件怎么交、四道题怎么写、哪里会翻车」的顺序走一遍，代码可以直接抄，坑我提前标出来。

2. 目录结构与 freopen：四份 .in/.out 是怎么被评测机认出来的

2.1 题目一览与提交目录的硬性约定

先把题面第一页的信息固定下来，这张表决定了你后面所有文件名、目录名和时限预估：

题面里写得很死：选手要在本机为每题建立与英文题目名同名的目录，源程序放进对应目录，最后把整个选手目录放进 D 盘根目录。卷子给的例子是选手 sx001 分别用 C、Pascal、C++ 答了三道题，提交结构就是sx001/cashier/cashier.c、sx001/dune/dune.pas、sx001/manhattan/manhattan.cpp。这里有两个容易被忽略的点：目录名和源文件名必须完全一致，大小写都要对；「只递交源程序，测试时以源程序为准」意味着不要交编译出来的 exe，评测机是在自己的环境里现场编译你的源码。

在本机准备时，我一般直接用一条命令把骨架拉出来，省得手抖打错目录名：

# 在 D 盘根目录下建立与题面一致的提交结构 mkdir -p sx001/friend sx001/people sx001/star sx001/paint

这条命令执行完，sx001下就有四个空目录。逻辑很直白：-p保证父目录不存在时一并创建，重复执行不会报错，适合每次开赛前重置一次目录。参数上唯一要改的是把sx001换成你的选手号。建完之后不要在这些目录里放.in、.out、.exe，题面只收源程序，多余文件在某些评测机上会触发目录校验失败。

2.2 freopen 的正确姿势与条件编译

四道题的输入输出全部走文件，所以每份源码开头都要把 stdin 和 stdout 重定向到对应文件。C++ 里最短的写法是这样：

#include <cstdio> int main() { #ifdef LOCAL // 本地调试时打开，提交前保证不定义 LOCAL freopen("friend.in", "r", stdin); freopen("friend.out", "w", stdout); #endif int n, x, m; scanf("%d %d %d", &n, &x, &m); // ... 主逻辑 return 0; }

三个参数的含义要记牢：第一个是文件名，必须和题面一字不差；第二个是打开模式，"r"只读、"w"只写（会清空原文件）；第三个是流指针，stdin表示把标准输入接到文件，stdout表示把标准输出接到文件。用#ifdef LOCAL包起来的好处是：本地编译时加-DLOCAL就能读文件，交上去的时候不带这个宏，程序就退回标准输入输出，一套代码两用，不会出现「本地跑得好好的、交上去读不到数据」这种玄学问题。

用 C 语言答题的话写法几乎一样，只是把#include <cstdio>换成#include <stdio.h>，其余不变。真正会出事的是路径：题面没说文件放在哪，默认是「可执行文件所在目录」，所以freopen("friend.in", ...)里的文件名不能带任何目录前缀。如果你本地把数据放在D:\data\friend.in，那就得写绝对路径，但交上去之前必须改回来，这一改一忘就是零分。

2.3 1 秒和 2 秒的时限意味着什么

题面给的时限不是装饰。按常见的评测机性能估算，1 秒大约能跑 10⁸ 次简单循环，2 秒翻一倍。把四道题的暴力复杂度摆出来对比一下，就知道哪道题必须优化：

这张表基本就是四道题的分水岭：好朋友随便写，统计人口必须上前缀和，卫星最好上树状数组，粉刷匠必须换个方向想。粉刷匠给到 2 秒而不是 1 秒，恰恰是因为它的正解需要读 10⁶ 条操作再倒着扫一遍，常数比前三题大，出题人留了余量，但这点余量救不了 O(nk) 的暴力。

3. 好朋友与统计人口：一道考枚举顺序，一道考前缀和

3.1 好朋友：按距离由近到远枚举，第一个满足的就是答案

题意拆开就三句话：n 套房排成一条直线，相邻 10 米，A 住 x 号；B 要买一套不是 x 的、价格不为 0 且不超过 m 的房子；在距离最近的前提下，输出这个最近距离。注意题目要的输出是「距离」不是「房号」，距离 = |i − x| × 10。

很多人第一反应是把所有可买的房子收集起来，按价格排序再按距离排序，这就把简单题做复杂了。更稳的思路是反过来：距离只可能是 10、20、30……，从 d = 1 开始往上加，每次检查 x−d 和 x+d 这两个位置，谁先满足「价格不为 0 且 ≤ m」就停，答案就是 d × 10。因为距离是从小到大枚举的，第一个命中点天然就是最优解，不需要排序，也不需要比较。

#include <cstdio> int p[105]; int main() { freopen("friend.in", "r", stdin); freopen("friend.out", "w", stdout); int n, x, m; scanf("%d %d %d", &n, &x, &m); for (int i = 1; i <= n; i++) scanf("%d", &p[i]); int best = -1; for (int d = 1; d < n; d++) { // 距离由近到远 int ok = 0; if (x - d >= 1 && p[x - d] != 0 && p[x - d] <= m) ok = 1; if (x + d <= n && p[x + d] != 0 && p[x + d] <= m) ok = 1; if (ok) { best = d; break; } // 同一距离两侧都满足时答案相同 } printf("%d\n", best * 10); return 0; }

d的上界取n - 1就够，因为最远的情况是 x 在 1 号、目标在 n 号，距离差 n − 1。x - d >= 1和x + d <= n两个判断把越界挡在外面，这是本题最常见的翻车点——x = 1 时往左探会读到p[0]，那个位置没赋值，运气好是 0 被判成「不可卖」，运气不好是脏数据直接误判。p[i] != 0单独判一次，是因为价格 0 表示非卖品，和「价格 ≤ m」是两回事，不能合并。

这里必须提一句样例数据。题面里样例 1 写成6 2 600 0 80 56 89 0，样例 2 写成6 3 5051 0 0 62 72 46，看着像第一行三个数、第二行一串价格，但对不上输出。按输出反推才能还原：样例 1 实际是6 2 60加上0 0 80 56 89 0，样例 2 是6 3 50加上51 0 0 62 72 46。也就是说资金 60 被下一行首位的 0 粘成了 600，资金 50 被下一行首位的 51 粘成了 5051，这是 docx 转文本时行内空格丢失导致的。还原之后，样例 1 里 3 号房 80 元超预算、4 号房 56 元可买，距离 20，输出对上；样例 2 里 1 号 51 元超预算、6 号 46 元可买，距离 30，也对上。照着粘过来的数据调试，只会怀疑自己算法写错了。

3.2 统计人口：前缀和把 5×10⁴ 次询问压到 O(1)

统计人口的模型是：n 户人家线性排列，第 i 户有 a[i] 人，总共 m 次询问，每次给出区间 [x, y] 表示这些编号的人不在家，问能核查到多少人。翻译成数学语言就是「总人口减去区间 [x, y] 的人口和」。总人口扫一遍就能得到，区间和如果每次现加，最坏 5×10⁴ × 5×10⁴ = 2.5×10⁹ 次加法，1 秒绝对跑不完。

前缀和是这道题唯一合理的解法。定义pre[i] = a[1] + a[2] + ... + a[i]，那么区间 [x, y] 的和就是pre[y] - pre[x-1]，每次询问两次减法，O(1)。预处理 O(n)，总复杂度 O(n + m)。

#include <cstdio> const int N = 50005; int a[N]; long long pre[N]; // 用 long long <p> <a href="https://download.csdn.net/download/qq_41642321/21618001" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>