NOIP 2006 普及组算法题解

零、背景

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

本场题型概览如下。

第一题：排序去重
第二题：动态规划（01背包）
第三题：贪心求下一个递增排列
第四题：二进制转 k 进制（__int128 / 大整数两种写法）

一、明明的随机数

题意：明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数。
对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。
然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。
请你协助明明完成”去重”与”排序”的工作。

数据范围：N ≤ 100，生成的随机整数均在 1 到 1000 之间（包含 1 和 1000）。

思路：模拟（排序 + 去重）

先对 N 个数排序，使相同的数相邻；再用 unique 把相邻重复元素移到末尾并返回新结尾，erase 删掉即可。
排序后重复数字只保留一个，天然完成去重。
输出先去重后的个数 M，再按序输出 M 个数。

复杂度：O(N log N)。

scanf("%d", &n);
nums.resize(n);
for (int i = 0; i < n; i++) {
  scanf("%d", &nums[i]);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
printf("%d\n", (int)nums.size());
for (int i = 0; i < (int)nums.size(); i++) {
  printf("%d%c", nums[i], i == (int)nums.size() - 1 ? '\n' : ' ');
}

二、开心的金明

题意：金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。
更让他高兴的是，妈妈昨天对他说：”你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。

今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。
于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1-5 表示，第 5 等最重要。

他还从因特网上查到了每件物品的价格（都是整数元）。
他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

数据范围：
总钱数 n < 3×10^4，
物品个数 m < 25；
每件物品价格 v ≤ 10^4，重要度 p 为 1 到 5；
答案小于 10^8。

思路：动态规划（01背包）

把每件物品看成”重量为价格 v、价值为价格×重要度 v×p”的物品，总钱数 n 就是背包容量。
问题转化为经典的 01 背包：选一些物品，在总价不超过 n 的前提下使总价值最大。

定义 dp[i] 表示花费不超过 i 元时能获得的最大价值总和。
对每件物品，从大到小枚举容量，转移方程为 dp[i] = max(dp[i], dp[i - v] + v * p)。
从大到小枚举保证每件物品最多被选一次。
最终答案为 dp[n]。

复杂度：O(n * m)。

scanf("%d%d", &n, &m);
vector<pair<int, int>> nums(m);
for (int i = 0; i < m; i++) {
  scanf("%d%d", &nums[i].first, &nums[i].second);
  nums[i].second *= nums[i].first;  // 价值 = 价格 × 重要度
}
vector<int> dp(n + 1, 0);
for (int i = 0; i < m; i++) {
  for (int j = n; j >= nums[i].first; j--) {
    dp[j] = max(dp[j], dp[j - nums[i].first] + nums[i].second);
  }
}
printf("%d\n", dp[n]);

三、Jam 的计数法

题意：Jam 是个喜欢标新立异的科学怪人，他不使用阿拉伯数字计数，而是使用小写英文字母计数。
在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。
我们把这样的”数字”称为 Jam 数字：每个字母互不相同，而且从左到右是严格递增的。

每次，Jam 还指定使用字母的范围，例如从 2 到 10，表示只能使用 b,c,d,e,f,g,h,i,j 这些字母；
如果再规定位数为 5，那么紧接在 Jam 数字 bdfij 之后的数字应该是 bdghi。

你的任务是：对于给定的一个 Jam 数字，按顺序输出紧接在后面的 5 个 Jam 数字，如果后面没有那么多，有几个就输出几个。

数据范围：
1 ≤ s < t ≤ 26，
2 ≤ w ≤ t - s。

思路：贪心求下一个递增排列

1）普通全排列的下一个

先来看普通的全排列。

全排列是所有 N 个元素全部用上、顺序任意，共 N! 种。
按字典序求下一个的经典算法：

1. 从右往左找第一个“升序对”位置 i，满足 a[i] < a[i+1]；
2. 在 i 右侧找大于 a[i] 的最小元素，与 a[i] 交换；
3. 把 i 右侧整体反转成升序。

例如 1 3 2：
从右往左看，1 < 3 是升序对；
右侧大于 1 的最小元素是 2，交换得 2 3 1；
右侧 3 1 反转成 1 3；
最终得到 2 1 3。

这就是 std::next_permutation 的实现。

2）N 个不同字母选 M 个的下一个排列

再来看 N 个不同字母，选择 M 个字母，求下个排列。

从 N 个不同字母中选出 M 个的排列，共有 A(N, M) = N! / (N - M)! 种。

求字典序下一个的经典算法：

1. 从右往左扫描，维护候选集合：初始是“整个排列没选中的字母”，每扫过一个位置就把该位置的字母并入；
   到位置 i 时，集合 = 没选中的后备字母 ∪ 已扫描过的字母，即去掉已确定前缀 a[0..i-1] 后剩下的所有字母；
2. 在位置 i，若集合中存在比 a[i] 大的字母，取最小者替换 a[i]，其后位置依次填入集合剩余字母中最小的若干个（升序），即为下一个排列；
3. 若所有位置都不满足，说明已经是最后一个排列。

例如从 1..4 中选 3 个：

  1 2 3
→ 1 2 4
→ 1 3 2
→ 1 3 4
→ 1 4 2
→ 1 4 3
→ 2 1 3
→ ...

当 N = M 时，这一步就退化为第 1 步的全排列。

3）本题：选 w 个且严格递增

最后来看这道题，选择的 M 个字母需要严格递增，求下个排列。

本题与第 2 步不同：从 [s, t]（共 N=t-s+1 个字母）中选 M=w 个时，要求从左到右严格递增。
也就是说，每个组合只保留升序这一种表示，总数从 A(N, M) 变成 C(N, M)。

Jam 数字是长度为 w 的严格递增字母串，求字典序中下一个的算法如下。

1. 从右往左找第一个“还能增大”的位置 w：
   设当前位置字母序号为 c，严格递增约束下，候选字母只能是比 c 大的字母，即 (c, T] 区间，共 leftChar = T - c 个；
   候选数量必须足够填满剩余位置：剩余位置数 leftPos = W - w ≤ 候选字母数 leftChar；
2. 取候选中最小的字母（即 c + 1）替换 str[w]，其后位置依次填入剩余候选中最小的那些，即 str[i] = str[i - 1] + 1，得到下一个 Jam 数字；
3. 若所有位置都不满足，说明已经是最后一个 Jam 数字。

重复这个过程 5 次即可。

例如样例：

  bdfij
→ bdghi
→ bdghj
→ bdgij
→ bdhij
→ befgh

复杂度：每次 O(W)。

int S, T, W;
char str[30];

bool Next(int w) {
  int leftPos = W - w;      // [w, W) 还需填的位置数
  int c = str[w] - 'a' + 1;  // 当前位置字母序号
  int leftChar = T - c;     // (c, T] 可用的字母数
  return leftPos <= leftChar;
}

bool Next() {  // 求下一个 Jam 数字
  for (int w = W - 1; w >= 0; w--) {
    if (Next(w)) {
      str[w]++;
      for (int i = w + 1; i < W; i++) {
        str[i] = str[i - 1] + 1;
      }
      return true;
    }
  }
  return false;
}

void Solver() {
  scanf("%d%d%d", &S, &T, &W);
  scanf("%s", str);
  int cnt = 5;
  while (cnt && Next()) {
    printf("%s\n", str);
    cnt--;
  }
}

四、数列

题意：给定一个正整数 k，把所有 k 的方幂及所有有限个互不相等的 k 的方幂之和构成一个递增的序列。
例如当 k = 3 时，这个序列是 1, 3, 4, 9, 10, 12, 13, …（即 3^0, 3^1, 3^0+3^1, 3^2, 3^0+3^2, 3^1+3^2, 3^0+3^1+3^2, …）。
请你求出这个序列的第 N 项的值，用 10 进制数表示。

数据范围：3 ≤ k ≤ 15，10 ≤ N ≤ 1000。

思路：二进制转 k 进制

规律：序列的每一项都对应一个”子集”——选择哪些 k 的方幂求和。
下面从 k = 2 开始，一步步推出：第 N 项就是把 N 写成二进制，按位累加 k 的对应次幂。

1）先看 k = 2：第 N 项就是 N

k = 2 时，方幂是 2^0, 2^1, 2^2, …，即 1, 2, 4, 8, …。
序列就是：1, 2, 3, 4, 5, 6, 7, …（所有正整数）。

为什么？每个方幂只有”选”与”不选”两种状态：第 i 个方幂选不选，恰好对应二进制第 i 位是 1 还是 0。
所以任意”互不相等的 2 的方幂之和” = 某个二进制数的展开值，反过来也成立，两者一一对应。
按和从小到大排列，就是按二进制数从小到大排列，因此第 N 项就是第 N 个二进制数，即 N 本身。

2）再看 k = 3：还是用 N 的二进制

k = 3 时，方幂是 3^0, 3^1, 3^2, …，即 1, 3, 9, 27, …。
每个方幂依然是”选”与”不选”两种状态，所以依然与二进制位一一对应；
唯一区别：选中的第 i 位，贡献从 2^i 变成 3^i。

因此第 N 项 = N 的二进制展开，按位乘 3^i 求和：
ans = Σ bit_i(N) * 3^i。

为什么序列递增？
对两个下标 A < B，设最高的不同二进制位为 i（A 的第 i 位为 0、B 的第 i 位为 1）。
A 的低 i 位全选时和最大，为 1 + 3 + ... + 3^(i-1) = (3^i - 1) / 2，仍小于 3^i；
而 B 的第 i 位就贡献 3^i，故 A 的和 < B 的和。

3）任意 k 都可以用 N 的二进制

一般化：任意正整数 k，方幂 k^0, k^1, k^2, … 互不相等，每个方幂依然只有”选”与”不选”两种状态，与二进制位一一对应。
所以第 N 项 = N 的二进制展开，按位乘 k^i 求和：
ans = Σ bit_i(N) * k^i。

递增性同理：对 A < B，设最高的不同二进制位为 i，则 A 的和 ≤ 1 + k + ... + k^(i-1) = (k^i - 1) / (k - 1) < k^i，
而 B 的和 ≥ k^i，故 A 的和 < B 的和。
因此按下标从小到大排列等价于按和的值从小到大排列，任意 k 都成立。

这道题有两个正确解法，都介绍如下。

解法一：__int128（推荐）

N ≤ 1000 < 2^10，所以二进制最多 10 位，只用得到 k^9。
k ≤ 15 时 k^9 = 15^9 ≈ 3.8×10^10，总和不超过 (15^10 - 1) / 14 ≈ 4.1×10^10，__int128 不会越界。

实现：base 从 1 开始表示 k^i，每次看 N 的最低位，为 1 就把 base 累加到答案，然后 base 乘 k、N 右移一位。

复杂度：O(log N)。

typedef __int128_t BigNum;

string ToString(BigNum num) {
  if (num == 0) return "0";
  string res;
  while (num > 0) {
    res += (char)('0' + (num % 10));
    num /= 10;
  }
  reverse(res.begin(), res.end());
  return res;
}

void Solver() {
  int K, N;
  scanf("%d%d", &K, &N);
  BigNum ans(0);
  BigNum base(1);
  while (N) {
    if (N & 1) {
      ans += base;
    }
    base = base * K;
    N >>= 1;
  }
  printf("%s\n", ToString(ans).c_str());
}

解法二：BigNum 大整数

数据范围如果更大一些，就只能使用大整数来做了。
核心逻辑与解法一完全一致，只是把 ans 与 base 换成大整数类型即可。

复杂度同样是 O(B log N)，其中 B 是大整数的位数。

void Solver() {
  int K, N;
  scanf("%d%d", &K, &N);
  BigNum ans(0);
  BigNum base(1);
  while (N) {
    if (N & 1) {
      ans += base;
    }
    base = base * K;
    N >>= 1;
  }
  printf("%s\n", ans.ToString().c_str());
}

大整数模板如下，只需要实现加法与乘法：

struct BigNum {
  vector<ll> data;  // 逆序存储
  BigNum(ll x = 0) {
    while (x) {
      data.push_back(x % 10);
      x /= 10;
    }
    if (data.empty()) data.push_back(0);
  }
  BigNum& Smp() {  // 去掉高位前导 0
    while (data.size() > 1 && data.back() == 0) data.pop_back();
    return *this;
  }
  BigNum operator*(const BigNum& other) const {
    BigNum res;
    res.data.resize(data.size() + other.data.size() + 1, 0);
    for (int i = 0; i < (int)data.size(); i++) {
      int carry = 0, pos = i;
      for (int j = 0; j < (int)other.data.size(); j++) {
        res.data[pos] += data[i] * other.data[j] + carry;
        carry = res.data[pos] / 10;
        res.data[pos] %= 10;
        pos++;
      }
      while (carry) {
        res.data[pos] += carry;
        carry = res.data[pos] / 10;
        res.data[pos] %= 10;
        pos++;
      }
    }
    return res.Smp();
  }
  BigNum& operator+=(const BigNum& other) {
    data.resize(max(data.size(), other.data.size()) + 1, 0);
    int carry = 0;
    for (size_t i = 0; i < data.size(); i++) {
      carry += data[i];
      if (i < other.data.size()) carry += other.data[i];
      data[i] = carry % 10;
      carry /= 10;
    }
    return Smp();
  }
  string ToString() const {
    string res;
    for (int i = (int)data.size() - 1; i >= 0; i--) {
      res.push_back(data[i] + '0');
    }
    return res;
  }
};

五、最后

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

第一题，签到题，排序加去重即可。
第二题，经典 01 背包，把”价格×重要度”直接当成价值是关键，一维数组倒序枚举容量。
第三题，贪心求下一个严格递增排列，从右往左找第一个能增大的位置，剩余位置依次递增填充即可。
第四题，识别出”二进制下标转 k 进制求和”是关键：第 N 项就是把 N 的二进制位展开，逐位乘 k 的对应次幂再求和；这道题的数据范围不大，可以使用 __int128 水过去。

《完》

-EOF-

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