24.7 降维技巧
约定
diff=1 水题 黄以下 一眼切
diff=2 easy 下位绿及黄 能切
diff=3 medium 特殊的黄;绿;较简单的蓝 可能需要题解提供一步
diff=4 hard 蓝色+ 需要题解
diff=5 不可做题 紫色+ 做不了
前缀和/差分
P1115 最大子段和
diff:1
前缀和板子。
P3406 海底高铁
diff:1
注意读题。前缀和板子。
看好数据范围
P2671 [NOIP2015 普及组] 求和
diff:2.5 tag:前缀和 性质
难点在于读题。
\((x,y,z)\) 表示的 都 是编号。如果读对了题会发现 \(y\) 没用。
由 \(2y=x+z\) 可以发现 \(x,z\) 奇偶性相同。将奇偶不同的编号分开排序。
按照颜色第一关键字,大小第二关键字排序并前缀和即可。
"写的是题解的三倍,还多一支 \(\log\),附赠一堆细节"
P1314 [NOIP2011 提高组] 聪明的质监员
tag:二分 前缀和
你说得对,但是当答案可能超过 int
时最小值初始化应为 LONG_LONG_MAX 而不是 INT_MAX。
二分 \(W\) 对于每个不同的 \(W\) 处理一次 \(w_i\ge W\) 的前缀和,复杂度就是对的了。
注意二分返回 true/false
的条件,当 \(s>ans\) 时 返回 false
。
P1083 [NOIP2012 提高组] 借教室
我会线段树。
题意即为 \((+,\min)\) 线段树。
注意线段树的 add 函数改没改
P2367 语文成绩
差分板子。
P2882 [USACO07MAR] Face The Right Way G
diff:3 tag:贪心 细节
为什么从前往后看到方向朝后的就转回去是对的?
我们注意到把一个点转两次等于啥也没干 可以模拟得出贪心正确性。
优化简单于贪心。xor 差分维护当前是否转向即可。
注意代码细节,差分的下一个数是 j+i 没有 +1!
高维前缀和/差分
P2004 领地选择
diff:1
板子题。但是写对板子。
\[sum_{i,j}=sum_{i,j-1}+sum_{i-1,j}-sum_{i-1,j-1}+a_{i,j}\\ sum_{x2,y2}-sum_{x1-1,y2}-sum_{x2,y1-1}+sum_{x1-1,y1-1} \]P3397 地毯
diff:1
板子。
P2280 [HNOI2003] 激光炸弹
diff:1.5
坐标有0 坐标有0 坐标有0 坐标有0。记得对所有的数组偏移 \(1\),不然 91 pts。
P1719 最大加权矩形
diff:1
板子。建议你谷课程题单减少板子题数量。
P3017 [USACO11MAR]Brownie Slicing G
diff:3.5 tag:贪心 性质 二分 前缀和
USACO 首先考虑贪心
二分答案,对于每一次 check,我们可以贪心。
具体的,先满足列的条件。如果该列在满足 \(\ge x\) 情况下无法 \(\ge b\) 块,那么加一行,注意每一块的范围是以 (上次分割行,上次分割列) 和 (枚举点行,枚举点列) 形成的长方形而不是一行连着取。是否满足条件即是否 \(\ge a\)。
前缀和即可。
因为少写 else 多交两发。
[ARC100E] Or Plus Max
diff:4 tag:sosdp 高维前缀和
考虑对每个 \(k\) 分开计算,即令 \(A_k=\max_{i\operatorname{or} j=k} a_i+a_j\),则 \(ans_k=\max_{i=1}^k A_i\)又注意到上式即 \(A_k=\max_{i,j\subseteq} a_i+a_j,ans_k=\max_{i=1}^k A_i\) 这是由于或运算的不减性。该转化是进行 sosdp 的前提。
事实上该问题可以枚举子集,\(O(3^n)\),事实上我们可以非容斥计算前缀和。
e.g. 三维前缀和
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
a[i][j][k] += a[i - 1][j][k];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
a[i][j][k] += a[i][j - 1][k];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
a[i][j][k] += a[i][j][k - 1];
sosdp 是一个每一维度长度都为 2 的高维 dp。
for(int i=0;i<=n-1;i++)
for(int j=0;j<=(1<<n)-1;j++)
if((1<<i)&j)
m[j]=m[j]+m[j-(1<<i)];
这段代码中 \(j\) 在 \(j-2^i\) 的上一层,从 0 开始,建议背过。
从 dp 角度理解:
定义 \(f_{i,r}\) 表示当前处理到二进制最后 \(i\) 位,状态为 \(r\) 的情况,当枚举 \(i+1\) 位时,若 \(r\) 即当前状态为 1,就从 \(f_{i,r},f_{i,r-2^i}\) 转移,分别表示有/无该位的情况并合并,否则从 \(f_{i,r}\) 转移即可。实现上,我们滚动掉第一维。
求超集仅需在 if 中加入一个 ! 取反即可。
树上差分
P3128 [USACO15DEC] Max Flow P
diff:2
我会树剖。
P3258 [JLOI2014] 松鼠的新家
diff:2
我也会树剖。
P2680 [NOIP2015 提高组] 运输计划
todo
P1600 [NOIP2016 提高组] 天天爱跑步
todo
离散化
P1097 [NOIP2007 提高组] 统计数字
diff:1
板子。
P1955 [NOI2015] 程序自动分析
diff:2.5 tag:并查集 离散化
diff=2.5 而不是 2 的原因是写挂了若干发。
我们只需要判断是否在不相等时能否满足,原因是显然的——等式具有传递性,所以我们事实上只需要维护相等这一个并查集即可。
离散化写了要用。并查集要写 f[i]=i
。
标签:code,前缀,记录,sum,板子,tag,diff,24.07 From: https://www.cnblogs.com/ChthollyNS/p/18302235fun fact:洛谷 #2 #10 放反了