NOIP 2002 提高组算法题解

零、背景

今天继续分享 2002 年 NOIP 提高组题解。

一、均分纸牌

题意：N 个盒子摆成一排，盒子里有若干张牌。
每次可以选择一个盒子，选择若干张牌放到相邻的其中一个盒子里。
问最少操作多少次，可以使得所有盒子的牌数量相等。

思路：贪心

先计算出最终每个盒子的牌的数量，然后从第一个盒子开始贪心。
如果盒子的牌少于目标数量，则需要从下个盒子移动对应的牌过来。
如果盒子的牌多于目标数量，则需要移动若干牌到下个盒子里。
如果盒子的牌等于目标数量，则不需要操作。

int avg = sum / n;
int ans = 0;
for (int i = 0; i < n; i++) {
  if (nums[i] == avg) continue;
  ans++;
  nums[i + 1] += nums[i] - avg;
}
printf("%d\n", ans);

二、字串变换

题意：给若干字符串二元组，代表第一个子串可以替换为第二个子串。
问字符串 A 是否可以在 10 步之内替换成字符串 B。

思路：暴力 BFS 搜索

复杂度：O(能过)

int Bfs() {
  if (S == T) return 0;
  unordered_map<string, int> H;  // H[s] 组成 s 的最小步数
  queue<string> que;
  int ans = -1;
  auto Add = [&](const string& s, const int step) {
    if (H.count(s)) return;
    if (s == T) {
      ans = step;
      return;
    }
    if (step < 10) {
      H[s] = step;
      que.push(s);
    }
  };

  Add(S, 0);
  while (!que.empty()) {
    const auto s = que.front();
    que.pop();
    const int step = H[s];
    const int sn = s.size();
    for (const auto& [A, B] : input) {
      const int an = A.size();
      for (int i = 0; i + an - 1 < sn; i++) {
        if (strncmp(&s[i], A.data(), an) == 0) {
          Add(s.substr(0, i) + B + s.substr(i + an), step + 1);
          if (ans != -1) return ans;
        }
      }
    }
  }
  return ans;
}

三、自由落体

题意：高度为 H 的天花板上在数轴 0,1,2，…，n-1 分别有一个小球。
所有小球同时自由下落。
在 S 有一个宽为 L，高为 K 小车，以固定速度 V 朝 0 点前进。
问小车可以接住多少个小球。
自由落体公式：d = 0.5 * g * t^2，其中 g=10。

思路：枚举或数学公式。

枚举，就是枚举每一个小球，判断降落到高度为 K，以及降落到地面的时间区间，是否在宽为 L 的车内。

bool Check(int p) {
  double t0 = sqrt(2 * (H - K) / g);
  double t1 = sqrt(2 * H / g);
  double S0 = S - t0 * V;
  double S1 = S - t1 * V;
  if (S0 + L >= p - eps4 && S1 <= p + eps4) {
    return true;
  }
  return false;
}

数学公式，就是列方程。

方程1：小球 i 高度为 K 时，车尾的坐标大于等于 i。
方程2：小球 i 高度为 0 时，车头的坐标小于等于 i。

注意事项1：车尾向下取整，例如 4.9 只能覆盖 4，不能覆盖 5。
注意事项2：车头向上取整，例如 1.1 只能覆盖 2，不能覆盖 1。
注意事项3：求的范围是 [0,n-1]。

const double t0 = sqrt(2 * (H - K) / g);
const double t1 = sqrt(2 * H / g);
const double S0 = S - t0 * V;
const double S1 = S - t1 * V;

// p0 向下取整， p1 向上取整
int p0 = floor(S0 + L + eps4);
p0 = min(p0, n - 1);
int p1 = ceil(S1 - eps4);
p1 = max(p1, 0);

printf("%d\n", max(p0 - p1 + 1, 0));

四、矩形覆盖

题意：二维坐标上有 n 个点，使用 k 个没有重叠的矩形覆盖这些点，求所有矩形的最小面积和。

思路：搜索

搜索第 i 个点属于第 k 个矩形，然后求面积之和。
复杂度：k^n

剪枝：一个点加入第 j 个矩形后，这个矩形不能和其他矩形有重叠。
每个矩形维护一个上下左右的边界，从而可以 O(1) 判断。

五、最后

这次比赛出得不好。
第二题没有正确的解法，只能暴力搜索。
第四题也只能暴力加剪枝，也不确定是否可以通过。

《完》

-EOF-

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

本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。