降维技巧

区间转化为点

前缀和与差分

通过预处理将区间操作转化为对点的操作,降低难度

其中差分思想应用较广,只要有二元性,就可以考虑差分。

如类似于加减这样的互逆的操作可用差分维护;如果一个点只有两种状态,或一个数在改变前后的奇偶性相反,都可以考虑差分。

P2882 [USACO07MAR]Face The Right Way G

每头牛只有前后两个状态,相当于0和1,因此可以通过差分的方式来\(O(1)\)维护翻转

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

高维前缀和

没完全懂

压缩一维的大小

离散化

主要有两种类型

第一是问题不在意具体数值,只在意数值之间的大小关系

第二是题目中满足一些性质,可将一大段取值区间内的情况等价成一个点

离散化的方式也很多,有排序、二分、map、平衡树等

P1502 窗口的星星

P1052 [NOIP2005 提高组] 过河

对两维的询问,利用单调性降维

two-pointers

维护两个指针\(l,r\)每次确定区间的左端点,让\(r\)不断向右移动,直到满足条件停下,维护一下答案

这里的单调性定义很宽,可以是决策单调,影响单调等

P1311 [NOIP2011 提高组] 选择客栈

题目只要求合法的状态数,而如果当前状态合法,那么右端点右面的所有状态也合法,这意味着在同一种客栈中进行选择是有单调性的。因此可以two-pointers,若判断当前状态合法,左指针右移,不合法,右指针右移。

换研究对象

恒等式类

一个恒等式,如 \(A_i=B_i-C_i\),求 \(A_i\) 的最大值,可转化为枚举\(B_i\),求\(C_i\)的最小值

实际上,枚举\(B_i\)相当于把\(B_i\)定为常量,然后就可以通过计算比较易得的\(C_i\)的最小值来求\(A_i\)的最大值

如果我们发现了相关的恒等式,都可以参考上面的方法,来转换研究对象

在OI中,常见的恒等式不多,除了题目中给的以外,大概有:

前缀和 \(A[l , r]=su m[r]-sum[l-1]\)

差分 \(delta[i]=A[i]-A[i-1]\)

最短路中的不等式 \(Min+w[x]<=dis[v[x]]\)

P1714 切蛋糕

预处理好前缀和后,枚举\(i\),再查找 \([i-m,i)\) 前缀和数组的最小值 ,此时 \(sum[i]-min\)就是最大值

正难则反

直接求解问题困难的时候,可以尝试反过来想

如选一些数使他们的和最大,等价于删去一些数,使删去的数之和最小

P2034 选择数字

选出数字之和最大等价于删去数字之和最小,而由题意,任意连续\(k\)个数中至少有一个数被删去。定义\(f[i]\)为前i个数中删去的数的最小和,则\(f[i]=minf[i-k+1,i-1]+a[i]\)

P1419 选择段落

本题要求序列中长度为\(T-S\)的子序列的最大平均值。

显然

\(\overline{X_{max}}>=\overline{X}\)

\(\overline{X_{max}}-\overline{X}>=0\)

\((T-S)\overline{X_{max}}-(T-S)\overline{X}>=0\)

所以我们可以将原序列全部减去当前平均值,问题转化为判断是否存在一个长度在\([S,T]\)范围内的区间它的和为正,如果有说明还有更大的平均值。

因此可以二分答案

根据题目性质将问题简化

奇偶性反转

P2882 [USACO07MAR]Face The Right Way G

每头牛只有前后两个状态,相当于0和1,因此可以通过差分的方式来\(O(1)\)维护翻转

利用性质减少计算量

P1311 [NOIP2011 提高组] 选择客栈

题目只要求合法的状态数,而如果当前状态合法,那么右端点右面的所有状态也合法,可以直接用这种颜色的客栈数减去指针算出后面的合法状态数,减少了计算量。

多维最值降维

P2216 [HAOI2007]理想的正方形

在一个\(n \times n\) 的矩阵中,如果 \(a\) 既是行中的最值,又是列中的最值,那么 \(a\) 一定是整个矩阵中的最值。

我们可以先对每行进行长度为 \(n\) 的滑动窗口,得到每个\(n \times n\) 矩阵的行最值,这些最值构成一个行最值矩阵。再对行最值矩阵的每列进行长度为 \(n\) 的滑动窗口,这样就得到了每个\(n \times n\) 矩阵的最值,枚举计算答案即可

上一篇:贝叶斯公式经典例题


下一篇:《强化学习》中的第11章:基于函数逼近的离轨策略方法