leetcode 第 362 场算法比赛,排名33

零、背景

这次比赛后两题比较难，第三题网络流（当然可以暴力通过），第四题字符串的矩阵幂，难度都较大。

leetcode 仓库地址：https://github.com/tiankonguse/leetcode-solutions

比赛代码：contest/3/362
费用流模板：graph/flow/min-cost/dinic-min-cost.cpp
字符串hash模板：doc/string/hash.cpp
矩阵幂模板：doc/matrix.cpp

一、与车相交的点

题意：数轴上有 n 个车的行驶区间，问哪些数字有车经过。

思路：区间合并。

方法1：枚举。
实现：枚举每辆车经过的每个点。
复杂度: O(n*m)

方法2：扫描线。
实现：按左区间从小到大排序，维护一个游标。
游标左边的代表已经计数，右边的尚未计数。
遇到一个区间，游标可以直接跳到右区间，并计算新增的区间大小。
复杂度：O(n)

二、判断能否在给定时间到达单元格

题意：给一个平面坐标系，问从一个点到达另一个点是否可以恰好 k 步到达。
步骤：上下左右8个方向相邻坐标走一步。

思路：先判断 t 步内能不能到达，再判断能不能来回走凑够 k 步。

假设两个点横坐标距离为 X，纵坐标距离为 Y，则最小步数为 max(X,Y)。

根据到达目标的奇偶性，分两种情况分析
1）剩余偶数步，左右来回走，即可凑够 k 步。
2）剩余奇数步，可以来回走，剩余 3 步是走三角形回到终点即可。
3）剩余1步，最短路到达目标的上一步，先不去目标，走一个三角形到达目标即可。

上面分析一番，发现只要能到达目标，就可以凑够 K 步。

实际上还有一个反例：剩余1步时需要上一步先不来，如果没有上一步呢？
也就是起点与重点相等，且k=1时，就没有答案了。

三、将石头分散到网格图的最少移动次数

题意：给一个3*3的网格，网格数字总和是 9，目标是最小操作，使得所有网格数字是 1。
操作：如果一个网格数字大于0，则可以减去一个数字，并选择将一个相邻的网格数字加一。

思路：一开始可能想使用动态规划或者状态压缩，发现没法处理。

然后发现，网格移动，其实就是搜索题或者图论题。

搜索的复杂度不太好算，可能会超时。

图论的话，就是典型的最小费用最大流问题。

构图：
1）网格9个数字，编号 1~9。
2）超级源点 与 数字大于1的网格有一个边，费用为0，流为数值减1（自己需要留一个数字）。
3）数字大于1的网格到数字为0的网格有一个边，费用为曼哈顿距离，流为 1（一个位置值只加1）。
4）数字为0的网格到超级汇点有一个边，费用为0，流为1。

算法：没有负环，跑 dinic 费用流即可。

代码与模板见第一小节。
费用流模板：graph/flow/min-cost/dinic-min-cost.cpp

PS：比赛时我一看需要写费用流，再刷榜单过了好多人，就猜测暴力 DFS搜索不会超时，于是我比赛先使用搜索通过的。

四、字符串转换

题意：给两个长度都为 n 的字符串 s 和 t，每次操作可以将 s 向右循环移动1~n-1次。
问操作 k 次恰好可以使得 s 与 t 相等的方案数。
数据范围：n=5*10^5,k=10^15

思路：字符串hash+矩阵幂题型。

先分析原题。

1）字符串任意循环右移，总共有 n 种字符串，即以原始字符串 s 某个下标为起始位置的字符串。

2）每次操作，循环右移有 n-1个选择，可以得到其他 n-1个字符串。
复杂度：O(n)

3）假设当前 n 个字符串分别有若干个方案，则一次操作有，下一轮 n 个字符串的方案数也都可以计算出来，具体计算方式可以写为矩阵的形式。
每个字符串的计算公式：其他所有字符串方案之和，也等价与所有字符串之和减去自己的方案数。
复杂度：O(n^2)

4）操作 k 次后，每个字符串的方案数就计算出来了。
复杂度：O(k * n^2)

5）n 个字符串中，与原始字符串相等的方案数求和，就是答案。
复杂度：O(n^2)

问题1：步骤3中，矩阵太大，计算一次复杂度太高。
优化：分析发现，可以发现规律，除了第一个字符串，之后所有字符串的计算公式都相同，值也都相同，即矩阵行都相等。
所以矩阵的大小没必要是n*2，定义一个2*2的矩阵即可，第二行就可以代表剩余的行。
优化后复杂度：O(1)

问题2：k 太大，计算 k 次会超时。
优化：相同的矩阵乘k次，可以使用矩阵幂优化。
优化后复杂度：O(log(k))

问题3：n个字符串比较大小，复杂度太高。
优化：可以通过计算字符串的hash值，快速比较是否相等。
优化后复杂度：O(n)

总共复杂度：O(n + log(k))

字符串hash模板：doc/string/hash.cpp
矩阵幂模板：doc/matrix.cpp

五、最后

这次比赛比较难，第三题是费用流可以暴力水过去，第四题是矩阵幂就没办法水过去了，是实实在在的考察硬实力的时候了。

这些题你都是怎么做的呢？

《完》

-EOF-

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