NOIP 2001 提高组算法题解

零、背景

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

一、一元三次方程求解

题意：给一个一元三次方程的系数，已知方程在 [-100,100] 数据范围内存在三个实数根，且任意两个根之间差的绝对值大于 1，求三个根，精确到小数点2位。

思路：枚举二分

由于题目要求精确到小数点2位，最简单的就是枚举 [-100.00, 100.00]，步长为 0.01。
对于每个枚举的点 p，判断 [p,p+1) 之间是否有答案。
如果 p 是答案，则直接枚举下一个。
如果 f(p) * f(p+1) < 0，则在其之间必然有答案。
否则肯定没有答案。

vector<double> ans;
for (double i = -100.00; i <= 100.00; i += 0.01) {
  double l = i, r = l + 1;
  double lv = f(l), rv = f(r);
  if (IsZero(lv)) {
    ans.push_back(l);
    continue;
  }
  if (lv * rv < 0) {
    // 二分法求根
    while (r - l > eps) {
      double mid = (l + r) / 2;
      if (f(l) * f(mid) < 0) {
        r = mid;
      } else {
        l = mid;
      }
    }
    ans.push_back(l);
    i = l;
  }
}

注意事项：如果直接枚举 [-100,100] 且步长为 1，则在整数答案上可能得到重复的答案。
解决方法：对于右端点，单独判断一次是不是答案，是了，直接跳到下一个步长。

vector<double> ans;
for (double i = -102; i < 102; i += 1) {
  double l = i, r = l + 1;
  double lv = f(l), rv = f(r);
  if (IsZero(lv)) {
    ans.push_back(l);
    continue;
  }
  // bad case: rv 是答案，二分会无限趋近于 rv，从而导致答案重复
  if (IsZero(rv)) {
    continue;
  }
  if (lv * rv < 0) {
    // 二分法求根
  }
}

二、数的划分

题意：对整数n 划分为 k 分，求划分数。
规则：相同数字之间没有区别，例如1,1,2与1,2,1为相同的划分。

思路：动态规划

分析：对于组合类的划分，需要定义当前可以选择的最值。

状态定义：dp[n][k][minVal] 将 n 划分 k 个数字，可以选择的最小数字为 minVal 的方案数。

状态转移方程，范围选择与不选择即可。

dp[n][k][minVal] = dp(n-minVal, k-1, minVal) + dp(n, k, minVal + 1);

复杂度：O(n^2 * k)

三、统计单词个数

题意：给一个字符串和若干单词，问如何将字符串拆分为 k 个字符串，使得每份中包含的单词个数加起来总数最大。
包含规则：单词可以部分重叠，当选用一个单词之后，其第一个字母不能再用。

思路：双重动态规划

第一重：拆分字符串
状态定义：dp(n,k) 前 n 个字符拆分为 k 个字符串的最大值。
状态转移方程：枚举拆分的最后一个字符串，求累计最大值。

dp(n,k) = max(dp(i, k-1) + Count(i+1, n));

第二重：求一个字符串包含的单词个数。
状态定义：Count(l,r) 字符串s[l,r]包含的单词个数。

状态转移方程：

Count(l,r) = Check(l,r) + Count(l+1, r);

Check(l,r) 含义，包含第一个字母时，是否包含某个单词。

四、Car 的旅行路线

题意：每个城市有四个机场，同一个城市内有高铁互通机场，不同城市的机场之间都有航线。
告诉你每个城市高铁的历程单价，以及飞机的历程单价，问从一个城市任意机场到另外一个城市任意机场的最低费用。

思路：单源最短路

每个机场当做一个点，就是4个起点以及4个终点的最短路问题。
多个起点与多个终点比较麻烦，可以通过增加超源点与超汇点，变更1个起点1个终点。

然后直接跑 Dijkstra 即可。

五、最后

这次比赛的四道题都不难。
第一题，枚举二分。
第二题，划分动态规划。
第三题，区间动态规划。
第四题，单源最短路。

《完》

-EOF-

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