NOIP 2003 基础组算法题解

零、背景

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

一、乒乓球

题意：告诉你两个人乒乓球每个球的胜负情况。
问在 11 分制和 21 分制情况下的比分。
规则：对于 X 分制，至少打 X 个球，且需要满足分差大于或等于 2 一局才算结束。

思路：循环

这道题最难的是读懂题意。
对于 11 分制，每局结束的规则是先打 11 个球，然后看是否满足分差大于等于 2，不满足就一直打。

读懂了题意，按题意计算即可。

注意事项：由于比赛每打完，最后一局都没得分就是 0:0。

void Solver(int B) {
  int W = 0, L = 0;
  for (auto c : S) {
    if (c == 'W') {
      W++;
    } else if (c == 'L') {
      L++;
    }
    if (max(W, L) >= B && abs(W - L) >= 2) {
      printf("%d:%d\n", W, L);
      L = 0, W = 0;
    }
  }
  printf("%d:%d\n", W, L);
}

二、数字游戏

题意：n 个数字摆成一个圆圈，问将数字划分为 m 连续的部分。
每部分求和后模 10 得到 m 个非负数，最后这些非负数相乘。
求可以得到的最大值和最小值。
数据范围：n=50，m=9

思路：动态规划

数字个数很小，枚举边界起始位置，问题就转化为了 n 个数字一排分成 m 组，求最值。

状态定义：dp(n,m) 前 n 个数字分成 m 组的最值。
状态转移方程：

dpMax(n,m) = max(dpMax(n-i, m-1) * Mod(sum(n-i+1, n)));
dpMin(n,m) = min(dpMin(n-i, m-1) * Mod(sum(n-i+1, n)));

复杂度：O(n^3 * m)

pair<ll, ll> Dfs(const int l, const int r, const int m) {
  if (dp[l][r][m][0] != -1) return {dp[l][r][m][0], dp[l][r][m][1]};
  if (m == 1) {
    dp[l][r][m][0] = dp[l][r][m][1] = Sum(l, r);
    return {dp[l][r][m][0], dp[l][r][m][1]};
  }
  ll minAns = INFL, maxAns = -INFL;
  for (int i = r; i - l + 1 >= m; i--) {
    auto [minV, maxV] = Dfs(l, i - 1, m - 1);
    ll sum = Sum(i, r);
    minAns = min(minAns, minV * sum);
    maxAns = max(maxAns, maxV * sum);
  }
  dp[l][r][m][0] = minAns;
  dp[l][r][m][1] = maxAns;
  return {minAns, maxAns};
}

三、栈

题意：给 n 个数字在栈中，现在可以使用一个中转栈，最终把数字移动到第三个栈中。
问最终第三个栈有多少种不同的排列。

思路：动态规划

状态定义：dp(n) n 个不同数字最终的排列数。

状态转移方程：
第 1 个数字可以借助中转栈，位于排列的第 i 个位置。
此时，第二个到第 i 个数字都需要先到达第三个栈，剩余的数字是独立的子问题。

dp(n) = sum(dp(i-1) * dp(n-i))  

复杂度：O(n^2)

ll Dfs(int n) {
  ll& ret = dp[n];
  if (ret != -1) {
    return ret;
  }
  ret = 0;
  for (int i = 0; i < n; i++) {
    ret += Dfs(i) * Dfs(n - i - 1);
  }
  return ret;
}

四、麦森数

题意：求 2^p-1 的位数与最低 500 位数字。
p 范围 [1000,3100000]

思路：高精度乘法

如果直接使用高精度乘法，只能得 50 分。
使用快速幂与高精度乘法，只能得 60 分。

所以，我就思考为何 p 最小值是 1000 而不是 1。

首先可以发现，2^p 的个位肯定不是 0，故减一不影响位数。
而 2^p 的位数等价于 log10(2^p)，转化一下就是 p * log10(2)。
这个值就是十进制的位数。

p 太小时，会存在精度问题。
p 最小值限制为 1000，显然是大于 1000 时就没有精度问题。

故直接使用公式计算位数。
而高精度计算时，剪枝只保留最低 500 位即可。

BigNum& Smp() {
  while (data.size() > 1 && data.back() == 0) {
    data.pop_back();
  }
  while(data.size() > 500){
      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 < data.size(); i++) {
    ll carry = 0;
    int pos = i;
    for (int j = 0; j < 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();
}

五、最后

这次比赛有点坑，直接写高精度会超时。
必须本地手动验证下 1000 左右数学公式计算的位数是否正确，然后再直接使用数学公式。

《完》

-EOF-

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

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