企业官网建设流程全解析

简介：这份资源是第18届绍兴市少儿信息学竞赛复赛真题，面向小学阶段的信息学竞赛选手与编程初学者。试卷共包含“好朋友”“统计人口”“卫星”“粉刷匠”四道题目，分别涉及数组与循环处理、区间求和查询、环状序列构造以及行列染色模拟等典型场景，覆盖变量与数据类型、控制结构、基础数据结构、算法设计等核心知识点，能较全面地检验参赛者的编程基本功与问题建模能力。资源为单个docx文档，体积仅32KB，文件内保留了完整题面、输入输出格式、样例解释、数据范围约束及考场目录结构说明，便于考生离线阅读、打印练习或模拟训练。目前已有811人下载学习，适合用于备赛刷题、赛前模拟、校内信息学社团练习，也可作为教师命题与教学参考。

1. 一份少儿信息学竞赛复赛试题，为什么值得反复刷

《第18届绍兴市少儿信息学竞赛复赛试题》这份docx格式的卷子，我拿到手先扫了一遍四道题，第一反应是“这真的是小学组吗？”好朋友、统计人口、卫星、粉刷匠，四个题目名字很萌，但卫星那题的约瑟夫环逆向构造、粉刷匠那题的行列时间戳优化，放到NOIP普及组也能当训练题。它最适合两类人：一是带信息学竞赛的教练，拿来做阶段测验；二是刚入门、想从真题里找编程手感的小学生和初中生。这套题没有偏题怪题，每一道都在考“把题意转化成代码”的基本功，刷完能摸清自己的薄弱点。

2. 把四道题拆开看：考点、数据范围与算法选型

拿到一套真题，先不要急着敲键盘。我习惯先把每道题的约束条件和预期复杂度写在草稿纸上，避免后面被数据范围坑到。这套卷子的四个题，数据范围从100到1000000不等，正好覆盖了线性扫描、前缀和、约瑟夫环构造、时间戳优化这四类最核心的基础思维。

2.1 好朋友：线性扫描就是最优解

先读题。小A住幸福村，n套房排成直线，房号1到n，相邻距离10米。小A房号x。小B想买离小A最近的一套，给出每套价格Pi（0表示不卖）和资金m。问最近距离。

这个题的考点其实不是算法，而是“能不能把生活场景翻译成循环里的条件”。数据范围n≤100，意味着你用什么算法都能过，线性扫描就够了。真正容易翻车的是三个条件：房号i不能等于x；Pi必须大于0；Pi必须小于等于m。三个条件必须同时满足。

为什么线性扫描是最优解？因为距离只取决于房号差的绝对值，而数组是无序的，不存在单调性可以利用。有人会想从x向两边扩展，用双指针找第一个满足价格的房号，但那样代码更绕，而且还要处理越界。n只有100，直接for i=1..n维护最小值最稳。这类“数据范围小到不需要优化”的题目，考的就是细心。

这里有个小陷阱：输出的是距离，单位是10米。也就是输出|i-x|*10。很多人算出房号差就交，忘记乘10，样例恰好把差值2乘10=20，一眼能看出来，但换一组数据就可能翻车。另外，题目说“按房号顺序给定每套房的价格”，所以输入顺序就是房号顺序，不需要再排序，直接按下标读入即可。

2.2 统计人口：前缀和把查询压到 O(1)

这道题的数据范围一下子从100跳到50000。n户人家，每户人口ai，m次查询，每次给出[x,y]表示这些户不在家，问能核查到多少人。朴素做法：每次查询累加除了[x,y]之外的所有ai，复杂度O(n*m)，m,n最大50000，直接超时。

标准做法是前缀和。先预处理pre[i]=pre[i-1]+ai，那么任意区间[x,y]的人口总和就是pre[y]-pre[x-1]。总人口total已知，答案就是total - (pre[y]-pre[x-1])。这样每次查询O(1)。

这里有一个很重要的竞赛习惯：看到区间求和，第一反应就是前缀和。不要因为“数据范围可能不大”就偷懒。另外题目提示“输入输出数据比较多，建议用scanf、printf”，这不是随便写的——用cin/cout在默认不关同步的情况下，50000组输入输出可能卡掉不少时间，虽然不算致命，但竞赛里时间就是分数。

还要注意答案范围：题目保证所有答案不超2^31-1，也就是说int够用。但前缀和数组建议用long long，因为total和pre在累加时，中间过程可能触及边界，用long long更安心。printf时用%lld。这算是一种“赔率思维”：多写一点，避免溢出。

2.3 卫星：环状约瑟夫变体的逆向构造

这是全卷最“烧脑”的一题。背景是n颗卫星排成环，按规则接收：先收1号，然后间隔1颗收2号，再间隔2颗收3号，依此类推，每次间隔数等于上一次收到的卫星编号。要求给出一个环状排列，使得按这个规则能按1到n的顺序收到信号。

很多选手第一次读题就卡在“间隔”的定义上。关键点：接收过的卫星不参与计数，但未接收的卫星在环上可以重复被数。比如n=5时，最后要间隔4颗，但只剩一颗未接收，于是4颗都是它。这是约瑟夫环的变体，但比普通约瑟夫环多了一个“递增步长”。

怎么构造排列？一个很自然的逆向思路是：先固定1号卫星在位置0，然后按编号2到n，依次决定每个编号放在环的哪个空位上。放2号时，从1号位置出发，跳过1个空位置，放到下一个空位置；放3号时，从2号位置出发，跳过2个空位置，放到下一个空位置；放i号时，从i-1号位置出发，跳过i-1个空位置。这里“空位置”就是还没放卫星的位置。用一个bool数组标记已占用，每次模拟跳圈，复杂度O(n^2)，n≤10000完全扛得住。

我用n=5验证了一遍：固定pos[1]=0；放2时跳过位置1，放到位置2；放3时从位置2数两个空位置（3和4），放到位置1；放4时从位置1数三个空位置，因为已占用的跳过，最后放到位置4；放5时只剩位置3，无论怎么数都是它。得到的排列是1 3 2 5 4，和样例一模一样。这个逆向构造是正解的核心。

2.4 粉刷匠：行列时间戳与排序计数

最后一题看着像模拟，实际是个计数优化题。n行m列墙，k次操作，每次把某整行或某整列刷成红色或蓝色，后刷的覆盖先刷的。问最后蓝色格子数。n,m,k都可达1000000，二维数组开不了，直接模拟每次涂色也不行。

突破口在于：每个格子的颜色只取决于最后一次影响它的操作。我们可以记录每行最后一次被刷的时间rt[i]和颜色rc[i]，每列最后一次被刷的时间ct[j]和颜色cc[j]。对于格子(i,j)，如果rt[i] > ct[j]，说明行操作比列操作晚，颜色由行决定，否则由列决定。

于是答案可以拆成两部分：所有行最终是蓝色且行时间大于对应列时间的格子，加上所有列最终是蓝色且列时间不小于行时间的格子。要高效统计，把行时间和列时间分别排序，然后用二分查找数个数。对每个蓝色行i，它覆盖的蓝色格子数等于所有满足ct[j] < rt[i]的列数；对每个蓝色列j，它覆盖的蓝色格子数等于所有满足rt[i] <= ct[j]的行数。两部分互斥，直接相加。复杂度O((n+m)log(n+m))，完美应对1e6的数据。

这个技巧在竞赛里非常常用：把二维问题拆成两个一维问题，用时间戳解决覆盖顺序。类似的题目还有“矩形涂色最后颜色”等等，掌握之后可以直接迁移。

3. 动手复现：C++ 参考实现与文件读写规范

先明确比赛要求。原题在题目一览中给出了每个题对应的输入文件名和输出文件名，比如好朋友是friend.in和friend.out，而不是从屏幕读入。这意味着必须使用文件重定向。很多新手第一次参加机试，不知道要加freopen，结果程序一运行就报“找不到文件”。下面从目录结构开始讲。

3.1 比赛目录结构：源文件放哪里先搞清楚

原题要求选手为每题建立与英文题目名相同的目录，把源程序放到对应目录下，最后把整个文件夹以考号命名放在D盘根目录。假设考号是sx001，四题的英文名分别是friend、people、star、paint，那么最终提交的目录结构应该是：

sx001/ ├── friend/ │ └── friend.cpp ├── people/ │ └── people.cpp ├── star/ │ └── star.cpp └── paint/ └── paint.cpp

注意：只交源程序，不交编译后的exe。评测时系统会重新编译，所以代码里的main函数必须返回0，文件名不能带空格，不要用IDE默认生成的“未命名1.cpp”。另外，freopen里的文件名是相对路径，评测时源文件就在对应题目目录下，所以直接写"friend.in"就行，不要加盘符路径。

3.2 好朋友与统计人口的代码

好朋友的参考实现如下：

#include <cstdio> #include <cstdlib> using namespace std; int main() { freopen("friend.in", "r", stdin); freopen("friend.out", "w", stdout); int n, x, m; scanf("%d%d%d", &n, &x, &m); int bestDist = -1; for (int i = 1; i <= n; i++) { int p; scanf("%d", &p); if (i == x) continue; // 不能买小A自己的房子 if (p == 0 || p > m) continue; // 不可卖或超出资金 int dist = abs(i - x) * 10; // 相邻房子距离10米 if (bestDist == -1 || dist < bestDist) { bestDist = dist; } } printf("%d\n", bestDist); // 题目保证有解；无解时这里输出-1 return 0; }

逻辑说明：依次读入每套房价格，排除条件后计算距离。用bestDist保存最小值，初始-1表示尚未找到可买房子。n最大100，扫描一遍足够。

参数说明：x是房号，注意abs(i-x)10中的10别丢；m是资金，判断条件是p>m而不是p>=m，因为等于刚好买得起。如果题目保证有解，可以忽略无解情况；为了对拍方便，保留-1输出。

统计人口的参考实现：

#include <cstdio> using namespace std; const int MAXN = 50005; long long pre[MAXN]; int main() { freopen("people.in", "r", stdin); freopen("people.out", "w", stdout); int n, m; scanf("%d%d", &n, &m); long long total = 0; for (int i = 1; i <= n; i++) { int a; scanf("%d", &a); total += a; pre[i] = pre[i - 1] + a; } while (m--) { int x, y; scanf("%d%d", &x, &y); long long absent = pre[y] - pre[x - 1]; printf("%lld\n", total - absent); } return 0; }

逻辑说明：pre[i]存前i户人口总和。查询时用pre[y]-pre[x-1]得到不在家人口，总人口减去就是可核查人口。数据范围n,m=50000，O(n+m)稳过。

参数说明：pre数组用long long，因为虽然答案不超2^31-1，但中间差值可能接近上限。printf用%lld对应long long。把pre定义成全局数组，避免栈空间不足。

3.3 卫星与粉刷匠的代码

卫星的逆向构造参考实现：

#include <cstdio> #include <vector> using namespace std; int main() { freopen("star.in", "r", stdin); freopen("star.out", "w", stdout); int n; scanf("%d", &n); vector<int> pos(n + 1, 0); // pos[i]表示编号i的卫星放在哪个位置 vector<bool> used(n, false); // used[p]标记位置p是否已放卫星 used[0] = true; pos[1] = 0; // 先把1号放在位置0 for (int i = 2; i <= n; i++) { int skip = i - 1; // 这次要间隔的卫星数 int cur = pos[i - 1]; // 从上一次接收的卫星出发 int cnt = 0; while (true) { cur = (cur + 1) % n; if (!used[cur]) { cnt++; if (cnt == skip) { // 已经跳过了skip个空位置，下一个空位置放i cur = (cur + 1) % n; while (used[cur]) cur = (cur + 1) % n; break; } } } pos[i] = cur; used[cur] = true; } // 按位置输出卫星编号 vector<int> ans(n, 0); for (int i = 1; i <= n; i++) ans[pos[i]] = i; for (int i = 0; i < n; i++) { if (i) printf(" "); printf("%d", ans[i]); } printf("\n"); return 0; }

逻辑说明：位置0固定给1号。每放编号i时，从上一次接收位置pos[i-1]出发，沿环数过skip个空位置，把i放在下一个空位置。“空位置”就是还没放卫星的位置，已占用位置跳过。当只剩一个空位置时，绕圈后仍会回到它，正好实现“重复计数”。n≤10000，O(n^2)可以过。

参数说明：pos数组下标是卫星编号，值是环上的位置索引；used数组下标是位置索引。输出时反过来用ans数组把位置映射回编号。如果n=1，for循环不执行，ans[0]=1，输出1。

粉刷匠的时间戳统计参考实现：

#include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { freopen("paint.in", "r", stdin); freopen("paint.out", "w", stdout); int n, m, k; scanf("%d%d%d", &n, &m, &k); vector<int> rt(n + 1, 0), ct(m + 1, 0); vector<int> rc(n + 1, 0), cc(m + 1, 0); for (int t = 1; t <= k; t++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); if (x == 0) { // 刷第y行 rt[y] = t; rc[y] = z; } else { // 刷第y列 ct[y] = t; cc[y] = z; } } vector<int> rowTime(rt.begin() + 1, rt.end()); vector<int> colTime(ct.begin() + 1, ct.end()); sort(rowTime.begin(), rowTime.end()); sort(colTime.begin(), colTime.end()); long long ans = 0; // 行比列晚，颜色由行决定 for (int i = 1; i <= n; i++) { if (rc[i] == 1) { int cnt = lower_bound(colTime.begin(), colTime.end(), rt[i]) - colTime.begin(); ans += cnt; } } // 列比行晚（或行从未操作），颜色由列决定 for (int j = 1; j <= m; j++) { if (cc[j] == 1) { int cnt = upper_bound(rowTime.begin(), rowTime.end(), ct[j]) - rowTime.begin(); ans += cnt; } } printf("%lld\n", ans); return 0; }

逻辑说明：对每行每列记录最后刷的时间戳和颜色。行决策覆盖的列：列时间 < 行时间；列决策覆盖的行：行时间 <= 列时间。排序后二分统计数量。1e6的数据量下，排序和二分都很快。

参数说明：rc/cc中0表示红色，1表示蓝色，对应题目里的z值。rt[i]=0表示行从未被操作，此时rc[i]为0，不会进入蓝色统计。lower_bound返回第一个>=rt[i]的位置索引，所以小于rt[i]的数量就是索引值。upper_bound返回第一个>ct[j]的位置索引，所以<=ct[j]的数量就是索引值。

4. 避坑指南：竞赛提交中的五个常见问题

下面这些坑都是实际比赛中真实出现过的，每条按“现象→原因→解决”写，建议你对照自己的习惯检查。

4.1 文件名和目录名对不上，白交

现象：代码在本地跑得好好的，交上去成绩是0分。 原因：源文件命名成friend.cpp，但目录名字打成了freind；或者整个文件夹没有以考号命名。 解决：赛前先看清楚英文题目名，建目录时直接复制题目给的英文名，不要手敲。提交前检查一遍文件路径，确保是“D盘根目录/考号/题目英文名/题目英文名.cpp”。

4.2 忘了加文件重定向

现象：自己测试时用键盘输入，输出到屏幕，一切正常；评测时找不到输入文件，直接运行时错误。 原因：题目一览里明确写了输入文件名friend.in、输出文件名friend.out，但代码里没有freopen。 解决：在main函数开头加freopen("friend.in","r",stdin); freopen("friend.out","w",stdout);。注意文件名是相对路径，评测时源文件就在对应题目目录下，所以直接用文件名就行，不要加路径前缀。

4.3 scanf/printf 和 cin/cout 混用导致缓冲出错

现象：使用cin读入、printf输出，或者反过来，部分数据丢失或顺序错乱。 原因：scanf/printf和cin/cout使用不同的缓冲机制，混用后可能导致未同步。 解决：要么统一用scanf/printf，要么统一用cin/cout并加上ios::sync_with_stdio(false)。竞赛题一旦出现“输入输出数据比较多”的提示，建议直接用scanf/printf。

4.4 好朋友的边界：把 x 号房也算进去

现象：样例都过了，换一组数据就错。 原因：题目明确说不包括小A的房子，但有些人在循环里没有跳过i==x，导致把x号房当成可买。 解决：在判断条件中明确写if (i == x) continue;。还要注意Pi=0不可卖，Pi>m买不起，这两个条件也要同时满足。我见过有人只写了价格大于0，忘了资金限制，输出结果比答案大。

4.5 粉刷匠的时间戳比较方向写反

现象：蓝色格子数比预期多或少。 原因：行决策的条件是“行时间 > 列时间”，但有人写成“>=”或者“列时间>行时间”，导致覆盖关系反了。 解决：用样例1手算一遍：第一次刷第1行蓝色，第二次刷第2列蓝色，最终蓝色格子是(1,1)、(1,2)、(2,2)。用程序输出中间rt/ct数组，对照检查。记住：后刷的覆盖先刷的，所以晚的时间戳决定颜色。

5. 把真题变成自己的题库：验证与改编技巧

5.1 用随机数据生成器做对拍

拿到题不要只靠样例题。我习惯写一个生成器，生成随机小数据，然后用暴力程序跟优化程序对拍。比如“好朋友”可以用随机n,x,m和Pi数组，暴力枚举所有房子算答案；“粉刷匠”可以用一个二维数组模拟所有操作，算出一个暴力答案。生成器大致长这样：

// gen.cpp #include <cstdio> #include <cstdlib> #include <ctime> int main() { srand(time(0)); int n = rand() % 10 + 2; int x = rand() % n + 1; int m = rand() % 100 + 1; printf("%d %d %d\n", n, x, m); for (int i = 0; i < n; i++) printf("%d ", rand() % 101); }

然后在命令行里跑gen | brute和gen | solve，再用diff比较输出。注意暴力程序也要用相同方式处理输入输出。这个习惯能帮你省下大量调试时间，尤其是卫星这种构造题，对拍能及时发现排列生成错误。

5.2 把四道题改造成新练习题

这套题可以魔改成很多变体：

• 好朋友：把n从100改成100000，变成线性扫描扩展题；改成“求第k近的可买房子”，就需要排序后取第k个。
• 统计人口：把静态前缀和改成带单点修改，就变成树状数组题；把“不在家”改成“在家”，答案变成区间和，做题时注意转换。
• 卫星：把间隔序列改成斐波那契数列，变成另一个构造题；要求输出字典序最小的排列，就需要贪心验证。
• 粉刷匠：把刷墙改成覆盖区间，求最后有多少个格子被蓝色覆盖，可以用线段树维护；把颜色数扩展到三种，统计每种颜色的格子数。

改动数据范围、增加修改操作、调整统计口径，都是一道新题。用这种“真题魔改”的方式训练，比盲目刷题库效率高得多。

从那以后，我每次带学生刷这套题，都强制他先把四道题的题意用一句话复述出来，再谈代码。因为信息学竞赛最怕的不是不会算法，而是没读懂题。希望帮到你。

本文还有配套的精品资源，点击获取