NOIP 2009 普及组 真题全解（超详细讲解版）

目录

1. 多项式输出（模拟 / 字符串处理）
2. 分数线划定（排序 / 结构体）
3. 细胞分裂（质因数分解 / 数学）
4. 道路游戏（线性 DP / 环形处理）

T1 多项式输出

题目链接

洛谷 P1067：https://www.luogu.com.cn/problem/P1067

题意

给出一个一元多项式的次数 n，以及从最高次到常数项的系数。要求按照标准数学格式输出多项式，规则如下：

• 不输出系数为 0 的项
• 第一项不输出加号
• 系数为 1 或 -1 时，不输出 1，只输出符号
• 一次项只写 x，不写 x^1
• 常数项直接输出数字

思路讲解

本题是经典模拟题，核心是按项处理、分类讨论。

1. 按从高次到常数项依次遍历每一项
2. 系数为 0 直接跳过
3. 符号处理：
   • 第一项不输出加号
   • 正数输出 +，负数输出 -
4. 系数处理：
   • 次数 > 0 且系数绝对值为 1，不输出 1
   • 常数项必须输出数字
5. 次数处理：
   • 次数 = 0：只输出数字
   • 次数 = 1：只输出 x
   • 次数 ≥ 2：输出 x^ 次数

只要把符号、系数、次数三部分拆开处理，代码就会非常清晰。

完整 AC 代码

#include <iostream> #include <cstdio> using namespace std; int a[110]; int n; int main() { cin >> n; for (int i = 0; i <= n; i++) cin >> a[i]; bool first = true; for (int i = 0; i <= n; i++) { int c = a[i]; int p = n - i; if (c == 0) continue; // 符号 if (c > 0 && !first) cout << "+"; if (c < 0) cout << "-"; int ab = abs(c); first = false; // 系数部分 if (p > 0 && ab != 1) cout << ab; if (p == 0) cout << ab; // x 与指数 if (p > 0) { cout << "x"; if (p > 1) cout << "^" << p; } } return 0; }

T2 分数线划定

题目链接

洛谷 P1068：https://www.luogu.com.cn/problem/P1068

题意

有 n 个选手，给出报名号与成绩。录取名额为 m×1.5（向下取整）。按成绩从高到低排序，同分按报名号从小到大排序。输出：分数线、实际录取人数，再输出所有录取者。

思路讲解

这是最基础的排序题，核心只有两点：

1. 结构体排序
2. 排序规则：成绩降序，学号升序

步骤：

1. 读入所有学生信息
2. 自定义排序规则
3. 算出分数线（第 need 名的成绩）
4. 统计所有 ≥ 分数线的学生
5. 输出结果

边界注意：

• 可能有多人同分压线，要全部录取
• 学号小的优先

完整 AC 代码

#include <iostream> #include <algorithm> using namespace std; struct Stu { int id, score; } s[5010]; bool cmp(Stu a, Stu b) { if (a.score != b.score) return a.score > b.score; return a.id < b.id; } int main() { int n, m; cin >> n >> m; int need = m * 1.5; for (int i = 1; i <= n; i++) cin >> s[i].id >> s[i].score; sort(s + 1, s + n + 1, cmp); int line = s[need].score; int cnt = 0; for (int i = 1; i <= n; i++) { if (s[i].score >= line) cnt++; else break; } cout << line << " " << cnt << endl; for (int i = 1; i <= cnt; i++) cout << s[i].id << " " << s[i].score << endl; return 0; }

T3 细胞分裂

题目链接

洛谷 P1069：https://www.luogu.com.cn/problem/P1069

题意

总试管数 M = m1^m2。有 n 种细胞，第 i 种每秒分裂为 Si 倍。问：最少多少秒后，细胞总数能被 M 整除。若永远不能，输出 -1。

思路讲解

本题考察质因数分解，是数学题而非模拟题。

核心结论：一个数能被 M 整除，当且仅当它包含 M 的所有质因子，且次数足够。

步骤：

1. 对 m1 质因数分解，再乘以 m2，得到 M 的质因子与所需次数
2. 对每个细胞 Si 质因数分解
3. 若 Si 缺少 M 的任意一个质因子 → 永远不行
4. 否则计算每个质因子需要多少秒，取最大值
5. 所有细胞中取最小时间即为答案

关键点：

• 必须用质因数分解，不能暴力枚举
• 次数向上取整：(need + has - 1) /has

完整 AC 代码

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int INF = 1e9; int pri[300], cnt[300], tot; int m1, m2, n; void divide(int x) { tot = 0; memset(pri, 0, sizeof(pri)); memset(cnt, 0, sizeof(cnt)); for (int i = 2; i * i <= x; i++) { if (x % i == 0) { pri[++tot] = i; while (x % i == 0) { cnt[tot]++; x /= i; } } } if (x > 1) { pri[++tot] = x; cnt[tot] = 1; } for (int i = 1; i <= tot; i++) cnt[i] *= m2; } int solve(int x) { int res = 0; for (int i = 1; i <= tot; i++) { int p = pri[i]; int need = cnt[i]; int has = 0; while (x % p == 0) { has++; x /= p; } if (has == 0) return INF; int t = (need + has - 1) / has; res = max(res, t); } return res; } int main() { cin >> n; cin >> m1 >> m2; if (m1 == 1) { cout << 0 << endl; return 0; } divide(m1); int ans = INF; for (int i = 1; i <= n; i++) { int s; cin >> s; ans = min(ans, solve(s)); } if (ans == INF) cout << -1 << endl; else cout << ans << endl; return 0; }

T4 道路游戏

题目链接

洛谷 P1070：https://www.luogu.com.cn/problem/P1070

题意

环形道路上有 n 个位置，m 个时间单位。每个位置每个时刻会出现金币。机器人可以走 1~k 步，也可以花钱换新机器人。求最大收益。

思路讲解

本题是线性 DP，状态非常清晰：

设dp [i] = 第 i 分钟结束时的最大收益

转移思路：枚举上一次换机器人的时间 j，从 j+1 走到 i，累加金币，减去购买机器人的花费。因为道路是环形，位置要取模处理。

关键点：

1. 机器人可以连续走，但不能超过 k 步
2. 每次换机器人都要花钱
3. 金币只能在对应时间、对应位置获取
4. 答案是 dp [1…m] 中的最大值

完整 AC 代码

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; const int INF = 0x3f3f3f3f; int n, m, K; int coin[N][N]; int cost[N]; int dp[N]; int main() { cin >> n >> m >> K; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> coin[i][j]; for (int i = 1; i <= n; i++) cin >> cost[i]; memset(dp, -INF, sizeof(dp)); dp[0] = 0; for (int i = 1; i <= m; i++) { for (int st = 1; st <= n; st++) { int sum = 0; for (int t = 0; t < K && i - t > 0; t++) { int pos = st - t; if (pos <= 0) pos += n; sum += coin[pos][i - t]; if (dp[i - t - 1] != -INF) dp[i] = max(dp[i], dp[i - t - 1] + sum - cost[st]); } } } int ans = 0; for (int i = 1; i <= m; i++) ans = max(ans, dp[i]); cout << ans << endl; return 0; }