2021.07.09【NOIP提高B组】模拟 总结

第一题：找规律题，首先把在同一个大三角形的点转化。然后答案为经过第三个三角形或者不经过。发现跟二的次幂有关系。

第二题：我的做法：设 f i f_i fi​表示前 i i i个字符构成的最短文本长度。有转移 f i = f j + k + i − j k ( k ∣ ( i − j ) ) f_i=f_j+k+\frac{i-j}{k}(k|(i-j)) fi​=fj​+k+ki−j​(k∣(i−j))。优化一下，用哈希判重。时间复杂度可以做到 O ( n 2 log ⁡ n ) O(n^2\log n) O(n2logn)。还可以设 f i , j f_{i,j} fi,j​表示以 i i i为结尾的串 i − j + 1 i-j+1 i−j+1到 i i i的最短压缩答案。转移可以用 g g g维护，时间 O ( n 2 ) O(n^2) O(n2)。

第三题：迭代加深启发式搜索。注意几点优化：估值函数，考虑优化左上方的联通块，每次不递归上面。时间复杂度玄学。

第四题：考虑用线段树维护三个值 l , r , s u m l,r,sum l,r,sum，分别表示区间从左/右开始的最长空连续段和区间的最长空连续段。

pushup

时分类讨论一下，查询时先看左子树再看中间最后看右子树。注意：懒标记用完后要清空。