NOIP 2007 普及组算法题解

零、背景

今天继续分享 2007 年 NOIP 普及组题解。

本场题型概览如下。

第一题：多关键字排序
第二题：贪心（排序 + 双指针）
第三题：动态规划（推荐）/ 贪心模拟
第四题：递推 + 大整数

一、奖学金

题意：某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。
期末，每个学生都有 3 门课的成绩：语文、数学、英语。
先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序。
如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

数据范围：5 ≤ n ≤ 300
每门课成绩都是 0 到 100 之间的整数
学号按输入顺序编号为 1 到 n

思路：模拟（多关键字排序）

每名学生用一个元组保存三要素：总分、语文成绩、学号。
按规则自定义比较器：总分不同按总分降序，总分相同按语文降序，总分和语文都相同按学号升序。
排序后输出前 5 名的学号和总分即可。

复杂度：O(n log n)。

int n;
vector<tuple<int, int, int>> nums;  // (总分, 语文, 学号)
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  nums.push_back({a + b + c, a, i});
}
sort(nums.begin(), nums.end(), [](const auto A, const auto B) {
  auto [a1, b1, c1] = A;
  auto [a2, b2, c2] = B;
  if (a1 != a2) {
    return a1 > a2;
  }
  if (b1 != b2) {
    return b1 > b2;
  }
  return c1 < c2;
});
for (int i = 0; i < 5; i++) {
  auto [a, b, c] = nums[i];
  printf("%d %d\n", c, a);
}

二、纪念品分组

题意：元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。
为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组。
但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。
为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

数据范围：1 ≤ n ≤ 3×10^4，80 ≤ w ≤ 200，5 ≤ P_i ≤ w；
50% 的数据满足 1 ≤ n ≤ 15

思路：贪心（排序 + 双指针）

先把所有纪念品按价格从小到大排序。
每组最多两件，为了让组数最少，应该尽量让”贵的”与”便宜的”配对：
维护左右指针 l、r，若最便宜的 nums[l] 与最贵的 nums[r] 之和不超过 w，就配成一组（l++、r–）。
否则最贵的 nums[r] 谁也配不上（比它便宜的都不行），只能单独一组（r–）。
每轮都增加一组，直到 l > r。

为什么贪心正确？
考虑当前最贵的物品 r，若它能与最便宜的物品 l 配对，那么任意最优解中 r 要么单独一组、要么与某个物品配对。
把配对对象换成 l 不会使组数变多：l 是最便宜的，替换后配对的那一组更轻，约束更容易满足，其余分组不受影响。
若 l 配不上 r，则 r 与任何物品都配不上（所有物品都比 l 贵或相等），只能单独一组，同样不劣于任何方案。
归纳下去，每一步贪心都保持最优。

复杂度：O(n log n)。

int W, n;
vector<int> nums;
scanf("%d %d", &W, &n);
nums.reserve(n);
for (int i = 0; i < n; i++) {
  int v;
  scanf("%d", &v);
  nums.push_back(v);
}
sort(nums.begin(), nums.end());
int ans = 0;
for (int l = 0, r = n - 1; l <= r;) {
  if (nums[l] + nums[r] <= W) {
    l++;
    r--;
  } else {
    r--;
  }
  ans++;
}
printf("%d\n", ans);

三、守望者的逃离

题意：恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。
守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。
为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。

守望者的跑步速度为 17 米/秒，以这样的速度是无法逃离荒岛的。
庆幸的是守望者拥有闪烁法术，可在 1 秒内移动 60 米，不过每次使用闪烁法术都会消耗魔法值 10 点。
守望者的魔法值恢复的速度为 4 点/秒，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值 M，他所在的初始位置与岛的出口之间的距离 S，岛沉没的时间 T。
你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。

注意：守望者跑步、闪烁或休息活动均以秒为单位，且每次活动的持续时间为整数秒。

数据范围：1 ≤ T ≤ 3×10^5，0 ≤ M ≤ 10^3，1 ≤ S ≤ 10^8；
30% 的数据满足 1 ≤ T ≤ 10、1 ≤ S ≤ 100；
50% 的数据满足 1 ≤ T ≤ 10^3、1 ≤ S ≤ 10^4。

思路：动态规划（推荐） / 贪心模拟

这道题有两个正确解法：标准的逐秒动态规划，以及按魔法存量分段批量处理的贪心模拟。
下面都介绍。

解法一：动态规划（推荐）

思路：动态规划（魔法与跑步解耦）

每秒钟有三种选择：跑步（+17 米）、闪烁（+60 米、消耗 10 点魔法）、休息（+4 点魔法）。
直接按魔法值开三维 DP 会太慢，这里有一个经典拆解：
把”闪烁 + 休息”整体看成魔法子系统，先求纯魔法策略每秒能走的最远距离，再与跑步混合。

状态定义 magic[i]：前 i 秒只做”闪烁或休息”（能闪就闪，魔法不够就休息），能走的最远距离。
状态定义 dp[i]：前 i 秒内（魔法与跑步任意混合）能走的最远距离。

magic 状态转移：
magic[i] = magic[i-1] + 60（若当前魔法 ≥ 10，闪烁并扣除 10 点魔法）；
magic[i] = magic[i-1]（休息，恢复 4 点魔法）。

dp 状态转移：
dp[i] = max(dp[i-1] + 17, magic[i])。

为什么正确？
闪烁每秒 60 米远快于跑步的 17 米，所以”能闪就闪”的纯魔法序列就是魔法子系统的最优策略：
任意魔法路径若某次闪烁推迟，只会让魔法更多、距离更少，不优于能闪就闪。

对任意最优混合策略，只需要看最后一秒：
若最后一秒是跑步，则前 i-1 秒的最优距离为 dp[i-1]，贡献 dp[i-1] + 17；
若最后一秒属于魔法序列，则纯魔法最优已覆盖到第 i 秒，贡献 magic[i]。
两者取最大即第 i 秒的最优，归纳成立。

扫描过程中一旦 dp[i] >= S 就输出 Yes 和 i；
扫完 T 秒仍未达到，输出 No 和 dp[T]（最远距离）。

复杂度：O(T)。

ll M, S, T;
scanf("%lld%lld%lld", &M, &S, &T);
vector<ll> magic(T + 1, 0), dp(T + 1, 0);
for (int i = 1; i <= T; i++) {
  if (M >= 10) {  // 能闪就闪
    magic[i] = magic[i - 1] + 60;
    M -= 10;
  } else {  // 魔法不够就休息
    magic[i] = magic[i - 1];
    M += 4;
  }
  dp[i] = max(dp[i - 1] + 17, magic[i]);  // 跑步与魔法取最优
  if (dp[i] >= S) {
    printf("Yes\n%d\n", i);
    return;
  }
}
printf("No\n%lld\n", dp[T]);

解法二：贪心模拟

思路：贪心模拟（按魔法存量分段处理）

第一步：魔法奇数转偶数

为什么 M 只需要偶数？
魔法值的变化恒为偶数（休息每秒 +4、闪烁每次 -10），奇数多出来的那个魔法值永远用不上。

所以奇数 M 与 M-1 的最优解完全相同，先令 M– 不影响答案。

if (M % 2 == 1) {
  M--;  // 奇数剩余一个永远用不上
}

第二步：确定比较基准。

闪烁 1 秒走 60 米，跑步 1 秒走 17 米，闪烁严格优于跑步。
所以魔法 ≥ 10 时能闪就闪，不需要犹豫。
如果在这期间可以到达终点，则存在答案。

if (M >= 10) {  // 空余的魔法先用完
  ll useTime = min(M / kMagicCost, T);
  ll useDistance = useTime * kMagicDistance;
  if (useDistance >= S) {
    ll ansT = (S + kMagicDistance - 1) / kMagicDistance;
    printf("Yes\n");
    printf("%lld\n", ansT);  // ansT 就可以到达 S
    return;
  }
  M -= useTime * kMagicCost;
  t += useTime;
  T -= useTime;
  s += useDistance;
  S -= useDistance;
}

第三步：按魔法余量分情况讨论

把 M ≥ 10 的部分一次性闪完后，剩余魔法可能是 0、2、4、6、8。

魔法不足时，要先休息 t 秒凑够 10 点（$t = ⌈(10 - M) / 4⌉$），再闪烁 1 秒，比较两种方案：
方案 A（魔法）：(t + 1) 秒走 60 米；
方案 B（走路）：(t + 1) 秒走 $17 × (t + 1)$ 米。

比较可知， M = 0 时单轮走路更优，其余 2、4、6、8 时单轮魔法走路优。

故，当 M 不等于 0 时，先走单轮，直到将 M 变成 0。

M = 2 时，一轮变为 0。
M = 4 时，第一轮变为 2，第二轮变为 0。
M = 6 时，第一轮变为 0。
M = 8 时，第一轮变为 2，第二轮变为 0。

总结，最多两轮，可以把 M 变为 0。

void OneMagic() {
  if (Finish()) return;
  if (M == 6 || M == 8) {             // 2s: 60m > 34m
    if (T == 1 || S <= kWalkSpeed) {  // 只能走 17m
      ll useTime = 1;
      ll useDistance = useTime * kWalkSpeed;
      t += useTime;
      T -= useTime;
      s += useDistance;
      S -= useDistance;
    } else {  // 消耗2秒魔法，走60米
      ll useTime = 2;
      ll useDistance = kMagicDistance;
      t += useTime;
      T -= useTime;
      s += useDistance;
      S -= useDistance;
      M = (M + 4) % 10;
    }
    return;
  }
  if (M == 4 || M == 2) {                 // 3s: 60m > 51m
    if (T <= 2 || S <= 2 * kWalkSpeed) {  // 只能走 34m
      ll useTime = 1;
      ll useDistance = useTime * kWalkSpeed;
      t += useTime;
      T -= useTime;
      s += useDistance;
      S -= useDistance;
    } else {  // 消耗3秒魔法，走60米
      ll useTime = 3;
      ll useDistance = kMagicDistance;
      t += useTime;
      T -= useTime;
      s += useDistance;
      S -= useDistance;
      M = (M + 8) % 10;
    }
    return;
  }
}
while (M > 0 && !Finish()) {
  OneMagic();
}

第三步：M = 0 时两轮合并，得到 7 秒周期。

M = 0 单轮不划算，但第二轮合起来会更优：

• 第一轮（M = 0 → 剩 2）：休息 3 秒恢复到 12 点，再闪烁 1 秒，4 秒走 60 米，剩 2 点；
  而 4 秒走路是 17×4 = 68 米，魔法没有走路更优；
• 第二轮（M = 2 → 剩 0）：休息 2 秒恢复到 10 点，再闪烁 1 秒，3 秒走 60 米，剩 0 点；
  而 3 秒走路是 17×3 = 51 米，魔法比走路更优；
• 两轮一起看：魔法 7 秒 120 米，走路 7 秒 $17×7 = 119$ 米，魔法每 7 秒比走路多 1 米。

所以剩余 0 点魔法且走路至少需要 7 秒时，选择不断选择两轮魔法会比走路更优。

if (!Finish()) {  // 7s: 120m > 119m
  ll useTime = min(T / 7, S / 120);
  ll useDistance = useTime * 120;
  t += useTime * 7;
  T -= useTime * 7;
  s += useDistance;
  S -= useDistance;
  // 此时如果 T >= 7 && 走路需要至少 7 秒，则可以继续使用两轮魔法
  ll walkTime = (S + kWalkSpeed - 1) / kWalkSpeed;
  if (T >= 7 && walkTime >= 7) {
    ll useTime = 1;
    ll useDistance = useTime * 120;
    t += useTime * 7;
    T -= useTime * 7;
    s += useDistance;
    S -= useDistance;
  }
}

第四步：收尾。

最后可能还剩余一些时间与距离，但是不足使用两轮魔法，所以只能走路了。

if (!Finish()) {  // 最后只有走路了
  ll useTime = min(T, (S + kWalkSpeed - 1) / kWalkSpeed);
  ll useDistance = useTime * kWalkSpeed;
  t += useTime;
  T -= useTime;
  s += useDistance;
  S -= useDistance;
}

最后，根据是否到达来判断答案。
最后，根据是否到达来判断答案。

const ll kMagicCost = 10;
const ll kMagicResume = 4;
const ll kMagicDistance = 60;
const ll kWalkSpeed = 17;
ll t = 0;  // 已经花费的时间，答案为 Yes 时输出
ll s = 0;  // 已经走的距离, 答案为 No 时输出
ll M, S, T;

bool Finish() {  // 时间不多了，或已经到达了
  if (T <= 0 || S <= 0) {
    return true;
  }
  return false;
}

if (S > 0) {
  printf("No\n");
  printf("%lld\n", s);
} else {
  printf("Yes\n");
  printf("%lld\n", t);
}

四、Hanoi 双塔问题

题意：给定 A、B、C 三根足够长的细柱，在 A 柱上放有 2n 个中间有孔的圆盘，共有 n 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的。
现要将这些圆盘移到 C 柱上，在移动过程中可放在 B 柱上暂存。
要求：每次只能移动一个圆盘；A、B、C 三根细柱上的圆盘都要保持上小下大的顺序。
设 A_n 为 2n 个圆盘完成上述任务所需的最少移动次数，对于输入的 n，输出 A_n。

数据范围：1 ≤ n ≤ 200；50% 的数据满足 1 ≤ n ≤ 25。

思路：递推 + 大整数

1）经典单塔

经典汉诺塔：n 个不同尺寸的盘，最少移动次数满足 $T(n) = 2*T(n-1) + 1$。
初始条件为 $T(1) = 1$。
解得 $T(n) = 2^n - 1$。

2）双塔

双塔中每对同尺寸的盘不做区分，所以可以把”一对盘”看成整体来分析：
先把上面 $2(n-1)$ 个盘移到 B 柱暂存（$A_{n-1}$ 步）；
再把最下面两个同尺寸盘依次放到 C 柱（2 步：两个盘尺寸相同、互不区分，可以一个接一个放上去）；
最后把 B 柱上 $2(n-1)$ 个盘移到 C 柱（$A_{n-1}$ 步）。
所以 $A_n = 2*A_{n-1} + 2$。

公式展开，发现数列是两倍的经典汉诺塔 2 2 4 6 10。
故可以推导出公式 A(n) = 2 * (2^n - 1)

3）大整数实现

n ≤ 200 时，$2^{201} - 2 ≈ 3.2×10^{60}$，远超 64 位整数范围，需要高精度。
ans 初始为 1，循环 n 次乘以 2（得到 2^n），减 1 后再乘以 2，就得到答案。

复杂度：O(n^2)。

void Solver() {
  int n;
  scanf("%d", &n);
  // A_n = 2^(n+1) - 2 = 2 * (2^n - 1)
  BigNum ans(1);
  BigNum one(1);
  BigNum two(2);
  for (int i = 0; i < n; i++) {
    ans = ans * two;  // ans = 2^n
  }
  ans = ans - one;    // ans = 2^n - 1
  ans = ans * two;    // ans = 2^(n+1) - 2
  printf("%s\n", ans.ToString().c_str());
}

五、最后

2007 年普及组的比赛整体难度适中。

第一题，签到题，多关键字排序，按总分、语文、学号依次比较即可。
第二题，经典贪心，排序后双指针，能配就配，最贵的与最便宜的配对，否则单独一组。
第三题，核心是长距离时”闪烁性价比远高于跑步”：要么逐秒 DP 把魔法与跑步解耦，要么按魔法存量分段批量贪心模拟。
第四题，双塔递推 $A_n = 2^(n+1) - 2$，n 到 200 时答案超过 64 位，必须用高精度。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code