leetcode 周赛 510 - 构造、动态规划

零、背景

这次比赛比较简单，构造浪费不少时间，没想到做完进入前 50 名了。

本场题型概览如下。
A 题：时间计时。
B 题：数学计算。
C 题：构造。
D 题：动态规划。

一、统计起止时间经过的秒数

题意：给两个时分秒时间，问相差多少秒。

思路：统一转化为秒数，求差即可。

二、处理所有元素的成本

题意：给一个数组以及固定资源数，用手上的资源依次消除所有数字。
消除规则：手上资源数需不小于数字，数字是多少，就消耗多少资源。
申请资源代价：首次申请成本为 0，之后每申请一次，申请成本加一。
问消除所有数字，最小的总成本是多少。

思路：数学计算

显然与数组没关系，只关心需要消耗的总资源数，从而计算出需要申请几次固定资源。
首次成本为 0，之后每次加一，就是一个自然数数列。
求和取模即可。

注意事项：求和可能超过 Int64 最大值，建议使用 int128 或者乘法取模。

小技巧：先取模再乘即可。

ll num = (sum + k - 1) / k;
ll A = num;
ll B = num + 1;
if (A % 2 == 0) {
  A = A / 2;
} else {
  B = B / 2;
}
A = A % mod;
B = B % mod;
return (A * B) % mod;

乘法取模模版如下。

ll MulMod(ll a, ll b, ll c) {
  ll res = 0LL;
  for (; b; b >>= 1, a = (a << 1) % c) {
    if (b & 1) res = (res + a) % c;
  }
  return res;
}

三、创建一个恰好有 K 条路径的网格图 I

题意：求构造一个有障碍物的网格，使得从左上角到右下角恰好有 k 个路径。
数据范围：k 不大于 4。

思路：分情况构造

考虑对称性，需要考虑行与列的翻转，这里先讨论列大于行的情况。

情况 1：k = 1
构造：L 型路径。

情况 2：k = 2
构造：L 和反 L，合并压缩刚好是一个口加一个 L。

情况 3：k = 3
构造：两个连续口加一个 L。

情况 4：k = 4
这个分两种情况。
第一种：三个连续口加一个 L。

第二种：两个斜口，加一个 L。

四、网格中保持一致的最大列数

题意：给一个网格，求删除最少的列数，使得剩余的网格，任意相邻的两个数字的差不大于指定值 Limit。

思路：动态规划

状态定义：dp[i] 保留第 i 列时，前 i 列的最优答案。
状态转移方程：

// j 与 i 两列所有行都满足要求  
dp[i] = max(dp[i], dp[j] + 1);  

复杂度：O(n^3)

五、最后

这次比赛题目整体都比较简单。
不过第三题可能会卡住很多人，尤其是 k 等于 4 时，分两种情况，很多人会造成遗漏。

《完》

-EOF-

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