NOIP 2000 提高组算法题解

零、背景

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

一、进制转换

题意：给一个十进制数字，求转化为一个负数进制的数字。

思路：数学公式

N 进制可以转化为递归的形式。
例如 N 进制的 X(10) = abcd(X) 展开形式与递归形式如下。
展开形式 a*N^3 + b*N^2 + c*N^1 + d
递归形式：((a*N + b) * N + c) * N + d
可以抽象为 X(10) = A * N + d。

对于正数进制，第一位 d 就是 X%N。
而对于负数进制，X%N 为正数时满足公式，可以递归处理。
而 X%N 为负数时，需要转化为正数，即再减去负数 N 即可，此时 A 的个数加一。

X(10) = A * N + d
      = (A + 1) * N + (d - N)  

转化为代码如下：

while (n) {
  int rem = n % r;
  n /= r;
  if (rem < 0) {
    rem -= r;
    n++;
  }
  ans.push_back(num[rem]);
}

复杂度：log(n)

二、乘积最大

题意：给一个数字字符串，插入 K 个乘号，使得乘积最大。

思路：动态规划+高精度

状态：dp(n,k) 前 n 个数字拆分为 k 个数字的最大乘积。
状态转移方程：枚举最后一个数字的位数。
复杂度：O(k*n^2)

  dp(n,k)
= max(dp(i, k-1) * Val(i+1, n))

三、单词接龙

题意：给 n 个单词，进行单词接龙，每个单词最多用两次，问接龙可以得到的最长长度是多少。
接龙规则：前面单词的后缀等于后面单词的前缀，但单词不能存在包含关系。
单词数量：20 个

思路：DFS 搜索

显然，如果两个单词有多种接龙方式时，选择公共前后缀最短的方式可以得到更长的答案。
故可以预处理任意两个单词之间是否可以接龙，记录最短的公共前后缀长度。
然后暴力从龙头递归搜索，并记录单词的使用次数，最后更新答案。
复杂度：O(n!*n!)

int visited[25];
int Dfs(const int u, const int len) {
  int ans = len;
  for (auto [v, pos] : g[u]) {
    if (visited[v] >= 2) continue;
    visited[v]++;
    ans = max(ans, Dfs(v, len + words[v].length() - pos));
    visited[v]--;
  }
  return ans;
}

扩展：如果 n 比较小时，可以使用状态压缩 mask 来避免重复搜索。
状态定义：dp[mask][n]
状态解释：已经选择 mask 个数字，剩余数字使用第 n 个单词当做龙头可以新增的长度。

四、方格取数

题意：给一个矩阵，只能从左上角往下与往右走到右下角。
现在可以走两次，问怎么走才能使得路径的数字和最大。
要求：同一个位置数字只能加一次。

思路：动态规划

状态定义：dp(x0,y0,x1,y1)

这道题的难点在于如何定义两个点的关系，从而避免重复计算答案。
这里对两个点做了相对位置的限制。
限制1：第一个点不能在第二个点的右边。
限制2：第一个点不能在第二个点的下边。

状态含义：左下方点位于 (x0,y0)，右上方点位于 (x1,y1) 时的最优答案。

点的关系确定了，再确定移动规则，从而可以避免重复统计答案。
规则1：同点，第一个点只能向左走，第二个点只能向上走，此时不能增加答案。
规则2：同行，只能第二个点移动。
规则3：同列，只能第一个点移动。
规则4：其他，两个点都可以移动。

int Dfs(int r0, int c0, int r1, int c1) {
  int& ans = dp[r0][c0][r1][c1];
  if (ans != -1) {
    return ans;
  }
  ans = 0;
  if (r0 == 0 || c0 == 0 || r1 == 0 || c1 == 0) {
    return ans;
  } else if (r0 == r1 && c0 == c1) {
    ans = max(Dfs(r0, c0 - 1, r1, c1), Dfs(r0, c0, r1 - 1, c1));
  } else if (r0 == r1) {
    ans = max(Dfs(r0, c0, r1, c1 - 1), Dfs(r0, c0, r1 - 1, c1)) + g[r1][c1];
  } else if (c0 == c1) {
    ans = max(Dfs(r0 - 1, c0, r1, c1), Dfs(r0, c0 - 1, r1, c1)) + g[r0][c0];
  } else {
    int ans0 = max(Dfs(r0 - 1, c0, r1, c1), Dfs(r0, c0 - 1, r1, c1)) + g[r0][c0];
    int ans1 = max(Dfs(r0, c0, r1, c1 - 1), Dfs(r0, c0, r1 - 1, c1)) + g[r1][c1];
    ans = max(ans0, ans1);
  }
  return ans;
}

五、最后

这次比赛的四道题都不难，但是有不少注意事项。
第一题，负数进制转换如果没做过，就需要推导公式，而且存在一些理解难度。
第二题，考察大整数乘法。
第三题，题目有问题，只能暴力搜索。
第四题，可以想到状态，难在定义两个点的关系以及规则，否则就很容易发生重复计算问题。

《完》

-EOF-

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