NOIP 2002 普及组算法题解

零、背景

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

一、级数求和

题意：对于 S(n)=sum(1/n) 的级数求和，求最小的 n 使得 S(n)>k。

思路：枚举

从小到大枚举求和，直到找到答案即可。

double sum = 0;
int n = 0;
while (sum <= k) {
  n++;
  sum += 1.0 / n;
}
printf("%d\n", n);

二、选数

题意：给 n 个数，选 k 个数，问存在多少个方案满足 k 个数的和为质数。

思路：搜索

先预处理出素数表，然后深搜枚举所有 C(n,k) 中情况，判断是否是素数。

由于 n 不大于 20，故最坏情况为 C(20, 10)，不超过 1000^2。

int dfs(const int num, const ll sum, const int pos) {
  if(num + (n - pos) < k) return 0; // 剪枝
  if (num == k) {
    return isprime(sum);
  }
  int ans = 0;
  ans += dfs(num, sum, pos + 1); // 不选择
  ans += dfs(num + 1, sum + a[pos], pos + 1); // 选择
  return ans;
}

选择的数字和最大为 10^8，素数表存不下。
这时候只需要筛选出根号个素数即可。
小于根号的，查素数表，大于根号的，暴力判断是不是素数。

int isprime(int x) {  // 判断一个数是否是素数
  if (x < N) return is[x];
  for (int i = 0; i < prmCnt; i++) {  // 遍历所有素数
    if (x % prm[i] == 0) {
      return 0;
    }
  }
  return 1;
}

三、产生数

题意：给一个大整数，现在可以对某一位的数字替换为其他数字，问最终可以替换出多少个不同的数字。

思路：高精度乘法

根据替换规则建图，然后 dfs 预处理计算出每个数字可以替换为哪些数字，从而可以确定每一位可以替换为哪些数字。
数字总个数为各位数字个数的乘积。

int Bfs(int s) {
  vector<int> flag(10, 0);
  queue<int> q;
  q.push(s);
  flag[s] = 1;
  int ans = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : g[u]) {
      if (!flag[v]) {
        flag[v] = 1;
        ans++;
        q.push(v);
      }
    }
  }
  return ans;
}

由于乘积可能很大，所以需要使用高精度乘法或者 int128。
而使用 int128 时，需要自己实现一个 ToString 函数。

__int128 ans = 1;
string S = buf;
for (auto c : S) {
  __int128 cnt = nums[c - '0'];
  ans = ans * cnt;
}
printf("%s\n", toString(ans).c_str());

四、过河卒

题意：给一个网格，从左上角走到右下角，只能向右与向下走，问有多少种走法。
限制：有一个坐标有一个象棋的马，马一步能到达的地方不能走。

思路：动态规划

预处理：预处理哪些位置不能走。
状态定义：dp(x,y) 从左上角到达 (x,y)的路径数。

状态转移方程：

dp(x,y) = dp(x-1, y) + dp(x, y-1);

五、最后

这次比赛的四道题都不难。
第一题，枚举。
第二题，搜索与大素数判定。
第三题，搜索与高精度乘法。
第四题，网格动态规划。

《完》

-EOF-

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

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