2021年第44周总结

11.1

判断线段相交问题

解决计算几何中判断两个直线相交问题&＃xff0c;通过矢量叉乘判断向量的相对位置&＃xff0c;叉乘也可判断凸包等。

博客

LeetCode 335

CF 751

Problem D

此题属于BFS中边数较多的情况&＃xff0c;尝试采用删点的方法降低时间复杂度&＃xff0c;删除后某些点将不会被搜索到。

可以使用Set维护待搜索的点集合。

思路&难点&＃xff1a;Set优化的BFS。

LC No.265

Probelm D

编辑距离超级加强版。

一开始考虑$dp[i][j]$为布尔型是否匹配&＃xff0c;后来发现其具有后效性&＃xff0c;因此该方法不行&＃xff0c;DP在设计状态的时候首先考虑是否有无后效性。

新的DP方法&＃xff0c;通过前推少量状态而不是枚举状态减少常数。

定义$dp[i][j]$为匹配到$s1[i]$和$s2[j]$的不产生冲突可能的剩余差值&＃xff08;由通配符产生&＃xff09;。

通过枚举$dp[i][j]$的状态去推出后继的状态。

其分为两种情况&＃xff1a;

• 追加差值
• 匹配差值

分类讨论即可。

思路&＃xff1a;二维DP。
难点&＃xff1a;选择合适的DP状态解决后效性。

11.2

CF 751

Problem E

可以看做是模板题。给定两个数组&＃xff0c;$a$的相对位置不变&＃xff0c;$b$以任意顺序插入到$a$中&＃xff0c;求最小逆序对。

首先需要证明两个结论&＃xff1a;

1. $b$一定以从小到大的相对顺序进行插入&＃xff0c;证明显然。
2. bib_ibi​的插入的最优性互相独立互不影响。

第二点的证明&＃xff0c;假设bib_ibi​在aja_jaj​的前面插入对逆序对的贡献是最少的&＃xff0c;那么我们知道&＃xff0c;aj>bia_j>b_iaj​>bi​若bib_ibi​插在aja_jaj​后面&＃xff0c;则会多产生一个逆序对&＃xff0c;并且小于bib_ibi​的$b$也不会产生更大的贡献。

首先的一个思路从寻找b1b_1b1​的最优插入位置p1p_1p1​&＃xff0c;这需要$O(n)$的时间&＃xff0c;在p1p_1p1​之后查找p2p_2p2​的位置&＃xff0c;这需要$O(n)$时间&＃xff0c;总共需要$O(nm)$的时间。如果我们使用分治&＃xff0c;每次查找bmidb_{mid}bmid​的最优位置&＃xff0c;每一层需要$O(n)$的时间&＃xff0c;总共需要$O(n\log m)$。

最后树状数组统计逆序对的个数&＃xff0c;然后统计即可&＃xff0c;时间复杂度$O((n\&＃43;m)\log (n\&＃43;m))$。

思路&＃xff1a;贪心证明&＃43;分治。
难点&＃xff1a;分成子问题优先考虑分治。

CF 752

Problem E

结论题 &＃43; 贡献转移。

考虑简化这个过程&＃xff0c;能够得到一些有用的结论&＃xff0c;即若ai&＃43;1ai&＃43;1​<ai​&＃xff0c;那么最终ai&＃61;⌊a⌈aiai&＃43;1⌉⌋a_i&＃61;\lfloor \frac{a}{\lceil \frac{a_i}{a_i &＃43; 1} \rceil} \rfloorai​&＃61;⌊⌈ai​&＃43;1ai​​⌉a​⌋&＃xff0c;并且需要⌈aiai&＃43;1⌉−1\lceil \frac{a_i}{a_i &＃43; 1} \rceil - 1⌈ai​&＃43;1ai​​⌉−1次拆解。

那么我们可以枚举以$x$结尾&＃xff0c;前驱为ai&＃43;1a_i &＃43; 1ai​&＃43;1的⌈aiai&＃43;1⌉−1\lceil \frac{a_i}{a_i &＃43; 1} \rceil - 1⌈ai​&＃43;1ai​​⌉−1贡献。设$dp[i][x]$表示为子数组$a[i:j]$最终以$x$结尾的子数组的数量&＃xff0c;那么前面有$i$个开头的子数组会得到这个贡献。即为i∗dp[i][x]∗(⌈aix⌉−1)i * dp[i][x] * (\lceil \frac{a_i}{x} \rceil - 1)i∗dp[i][x]∗(⌈xai​​⌉−1)。

思路&＃xff1a;推结论&＃43;贡献转移。
难点&＃xff1a;推出结论&＃43; DP状态设计 &＃43; 贡献转移技巧。

11.3

LC 407

优先队列的优化的BFS搜索题。

我们假设一个小人在$(r,c)$向四周倒水&＃xff0c;优先队列中有三元组$(r,c,hei)$&＃xff0c;表示小人在$(r,c)$向四周倒水的最大高度为$hei$。

首先我们可以确定一开始小人应该站在边界处&＃xff0c;故将所有的边界加入到队列中。

每次队列取出$hei$最小的&＃xff0c;向四周倒水&＃xff0c;如果$(dr,dc)$的高度低于$hei$&＃xff0c;那么肯定是可以倒水的高度为$hei$的&＃xff0c;因为$(dr,dc)$的短板一定是$(r,c)$。然后$(dr,dc)$的$hei$就可以确定&＃xff0c;即$\max (hei,height[dr][dc])$&＃xff0c;将其加入优先队列中。

思路&难点&＃xff1a;优先队列维护的BFS。

11.5

21 CCPC for Female

Problem C

一开始ych告诉我将分公司的数量为$1$和大于$1$进行分类&＃xff0c;为$1$的就不要赋予状态。

正解为传递闭包优化DAG上的DP。

考虑带中间节点的路径$i\to j$&＃xff0c;那么若有边$(i,j)$存在&＃xff0c;那么以这条边转移的DP一定是不优的&＃xff0c;所以可以删掉这个边。

为了维护节点$ij$之间是否有带中间节点的路径&＃xff0c;需要求一次DAG的传递闭包。

这样操作之后&＃xff0c;可以证明带有$n$个节点的DAG图最多有$n-1$个边。即$1\to n$的一条链。

这样时间复杂度就从O(n2)O(n^2)O(n2)的完全图优化为$O(n)$的链图。

思路&＃xff1a;DAG上的DP。
难点&＃xff1a;用传递闭包优化DAG的DP。

Problem B

倍增&＃xff0c;一个很显然的思路&＃xff0c;在字符串$s$上查询&＃xff0c;从$s[0]$到s[k1]s[k_1]s[k1​]正好凑齐一组字母表&＃xff0c;从s[k1&＃43;1]s[k_1 &＃43; 1]s[k1​&＃43;1]到s[k2]s[k_2]s[k2​]正好凑齐一组字母表&＃xff0c;结果正好能最多凑齐$p$个字母表&＃xff0c;那么关于$s$的答案即为$p\&＃43;1$。

考虑$dp[i][k]$为从起点$i$跳2k2^k2k次的中点。首先通过一次二分计算出$dp[i][0]$&＃xff0c;然后进行倍增求出所有的$dp[i][k]$即可。

单次查询时的时间复杂度为$O(\log n)$。

思路&难点&＃xff1a;二分&＃43;倍增DP。

11.6

21 CCPC for Female

Problem F

POJ 2185的增强版本 广义KMP&二维KMP的模板题&＃xff0c;只不过需要一次Hash来优化字符串的判断相等。

思路&难点&＃xff1a;二维KMP&＃43;Hash优化。

11.8

ABC 226

Problem F

一道分拆数估计&＃43;DFS枚举分拆&＃43;第一类斯特林数&＃43;划分模型的一道综合计数题。

首先根据P50<1e6P_{50} <1e6P50​<1e6&＃xff0c;确定DFS枚举分拆可行。

然后DFS枚举分拆&＃xff0c;在可能的答案中对分拆组转换为划分组&＃xff0c;最后根据公式$S(n,1)\&＃61;(n-1)!$对其进行计数。

思路&＃xff1a;组合数学。
难点&＃xff1a;计算公式的确定。