NOIP 2001 普及组算法题解

零、背景

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

一、数的计算

题意：给出数列的第一个数字，按规则构造正整数数列，问可以构造多少个不同的数列。
构造规则：相邻两个数字，下个数字不能超过上个数字的一半。
数据范围：1000

思路：动态规划

状态定义：
dp[i] 以 i 为第一个数字的不同数列个数。

状态转移方程：

dp[0] = 1;
// j <= i/2
dp[i] = sum(dp[j]);  

复杂度：O(n^2)

优化：预处理状态前缀和。

预处理状态：
sum[i] 以小于等于 i 为第一个数字的不同数列个数。

dp[0] = 1;
sum[0] = 1;

dp[i] = sum[i/2];
sum[i] = sum[i-1] + dp[i];

复杂度：O(n)

二、最大公约数和最小公倍数问题

题意：输入两个正整数 X 和 Y，问存在多少个正整数二元组 (P,Q) 满足 X 是最大公约数，Y 是最小公倍数。

思路：枚举

由于 X 是 (P,Q) 的最大公约数，可以推导出 gcd(P,Q) = X。
进而推导出 gcd(P/X, Q/X) = 1。

令 PX * X = P，QX * X = Q，则可以推导出
最小公倍数的关系 Y = PX * QX * X。

现在已知 Y 与 X，需要求 PX 与 QX。
且需要满足 Y % X == 0 且 gcd(PX, QX) = 1。

枚举 PX，求 QX 即可。

ll ans = 0;
if (y % x == 0) {
  ll YX = y / x;
  for (ll PX = 1; PX <= YX; PX++) {
    if (YX % PX == 0) {
      ll PY = YX / PX;
      if (Gcd(PX, PY) != 1) continue;
      ans++;
    }
  }
}

三、求先序排列

题意：给出中序和后序序列，求先序序列。

思路：递归

先预处理每个值对应的位置，然后递归处理即可。

Dfs(0, n - 1, 0, n - 1, 0, n - 1);
void Dfs(int l1, int r1, int l2, int r2, int l3, int r3) {
  if (l1 > r1) return;
  S3[l3] = S2[r2];
  int mid = mp1[S2[r2]];
  int leftLen = mid - l1;
  Dfs(l1, mid - 1, l2, l2 + leftLen - 1, l3 + 1, l3 + leftLen);
  Dfs(mid + 1, r1, l2 + leftLen, r2 - 1, l3 + leftLen + 1, r3);
}

四、装箱问题

题意：给一个容量为 V 的箱子，以及 n 个有自己体积的物品，问箱子的剩余空间最小是多少。

思路：01 背包

// 01背包
int V, n;
vector<int> vs;
vector<int> DP;
void Solver() {  //
  scanf("%d%d", &V, &n);
  vs.resize(n);
  DP.resize(V + 1, 0);
  for (int i = 0; i < n; i++) {
    scanf("%d", &vs[i]);
  }
  for (int i = 0; i < n; i++) {
    for (int j = V; j >= vs[i]; j--) {
      DP[j] = max(DP[j], DP[j - vs[i]] + vs[i]);
    }
  }
    printf("%d\n", V - DP[V]);
}

五、最后

这次比赛的四道题都不难。
第一题，动态规划。
第二题，数学计算与枚举。
第三题，递归。
第四题，动态规划 01 背包。

《完》

-EOF-

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

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