NOI 1998 题解

零、背景

之前已经分享了 1998 年 NOIP 的《普及组题解》和《提高组题解》。
这里继续整理 1998 年 NOI 题解。

一、围巾裁剪

题意：给一个边长为 N 的正三角形，可以划分出 N*N 个小正三角形。
如图，把这些小正三角形画上坐标，则每个小三角形可以使用坐标唯一标识。
现在告诉你某些小三角形损坏了，问怎么裁剪，才能得到两个完好的不重叠的正三角形，使面积之和最大。

思路：枚举、旋转

很容易发现，对于任意两个不重叠的正三角形，肯定可以使用某条直线将其分割。
故可以枚举分割线，然后分别求出分割线两边的最大正三角形，面积求和即可。

由于正三角形面积与边长的平方成正比，可以先求边长，最后算答案时再转化为面积。

不妨先看横线的分割线。

很容易想到一个动态规划的做法。

如下图，红色正三角形可以使用两个黄色小正三角形、绿色正三角形、蓝色正三角形拼接而成。

另外，正三角形还存在倒着的情况。

与正三角形类似，两个小正三角形和绿色正三角形、蓝色正三角形拼接成倒着的情况。

其实可以发现，下标是偶数时对应正三角形，下标是奇数时对应倒着的情况。
这样，我们就可以求出以每个顶点为起点的最大正三角形的边长。

求出每个顶点的最大正三角形后，前缀聚合就可以求出每一行的最大正三角形，最后再聚合求出前缀的最大正三角形。

横线上面和下面的最大三角形都求出来了，枚举所有横线，求出最大面积即可。

除了横线，还有左方向的斜线和右方向的斜线。
可以发现，通过旋转三角形，可以将所有斜线都转化为横线。

把坐标从 0 开始计算时，逆时针旋转 90 度的公式如下：

x1 = n - 1 - y0 / 2;
y1 = 2 * x0 - y0;

旋转 2 次，计算三次答案即可。

二、免费的馅饼

题意：天上会掉馅饼，提前告诉你某个时间点在某个坐标会掉一个馅饼。
我们每秒最多移动 2 个单位，起始坐标任意，问最多可以吃掉多少个馅饼。

思路：二维偏序

显然，需要先按时间对馅饼进行排序。
然后很容易写出暴力的动态规划。

状态定义：dp[i] 吃到第 i 个馅饼时，共吃了多少个馅饼。

状态转移：dp[i] = max(dp[j]) + 1 && j 可以到达 i

什么时候上个馅饼的位置可以到达这个馅饼的位置呢？
距离除以时间不大于速度即可。
即 |xi - xj| <= 2 * (ti - tj)

复杂度：O(n^2)
得分：90分

要想继续优化，就需要对绝对值进行展开，从而得到两个公式。

   |pi - pj| <= (tj - ti) * 2

1) pi - pj <= (tj - ti) * 2
=> ti * 2 + pi <= tj * 2 + pj

2) pj - pi <= (tj - ti) * 2
=> 2 * ti - pi <= tj * 2 - pj

令 X=t*2+p，Y=t*2-p，则上述两个公式分别为：

1) Xi <= Xj
2) Yi <= Yj

这个问题就转化为了二维偏序问题。

对于二维偏序问题，解法就比较经典了。

第一步，排序，优先按 X 轴排序，然后按 Y 轴排序。
第二步，对 Y 坐标轴离散化。
第三步，扫描所有点，求 Y 前缀最大值。
由于已经离散化了，可以使用树状数组或者线段树来求前缀最大值。
第四步，更新当前 Y 的最大值。

复杂度：O(n log(n))

TreeArray tree;
ll SolverPartialOrder() {
  sort(points.begin(), points.end());
  tree.Init(m);  // [1,m]
  ll ans = 0;
  for (auto [x, y, v] : points) {
    ll offset = mp[y];
    ll newVal = tree.QueryMax(offset) + v;
    tree.SetVal(offset, newVal);
    ans = max(ans, newVal);
  }
  return ans;
}

三、最后

1998 年的 NOI 在洛谷上只有两道题，稍微有点难度。
尤其是二维偏序，属于很经典的高级问题。

《完》

-EOF-

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