• 周五. 8月 19th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

降维技巧

admin

11月 28, 2021

区间转化为点

前缀和与差分

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

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

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

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 imes n) 的矩阵中,如果 (a) 既是行中的最值,又是列中的最值,那么 (a) 一定是整个矩阵中的最值。

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

发表回复

您的电子邮箱地址不会被公开。