标签：code 前缀 记录 sum 板子 tag diff 24.07

24.7 降维技巧

约定

diff=1 水题 黄以下 一眼切

diff=2 easy 下位绿及黄 能切

diff=3 medium 特殊的黄;绿;较简单的蓝 可能需要题解提供一步

diff=4 hard 蓝色+ 需要题解

diff=5 不可做题 紫色+ 做不了

前缀和/差分

P1115 最大子段和

diff:1

前缀和板子。

code

P3406 海底高铁

diff:1

注意读题。前缀和板子。

看好数据范围

code

P2671 [NOIP2015 普及组] 求和

diff:2.5 tag:前缀和 性质

难点在于读题。

\((x,y,z)\) 表示的 都 是编号。如果读对了题会发现 \(y\) 没用。

由 \(2y=x+z\) 可以发现 \(x,z\) 奇偶性相同。将奇偶不同的编号分开排序。

按照颜色第一关键字，大小第二关键字排序并前缀和即可。

"写的是题解的三倍，还多一支 \(\log\)，附赠一堆细节"

code

P1314 [NOIP2011 提高组] 聪明的质监员

tag：二分 前缀和

你说得对，但是当答案可能超过 int 时最小值初始化应为 LONG_LONG_MAX 而不是 INT_MAX。

二分 \(W\) 对于每个不同的 \(W\) 处理一次 \(w_i\ge W\) 的前缀和，复杂度就是对的了。

注意二分返回 true/false 的条件，当 \(s>ans\) 时 返回 false。

code

P1083 [NOIP2012 提高组] 借教室

我会线段树。

题意即为 \((+,\min)\) 线段树。

注意线段树的 add 函数改没改

code

P2367 语文成绩

差分板子。

code

P2882 [USACO07MAR] Face The Right Way G

diff:3 tag:贪心 细节

为什么从前往后看到方向朝后的就转回去是对的？

我们注意到把一个点转两次等于啥也没干 可以模拟得出贪心正确性。

优化简单于贪心。xor 差分维护当前是否转向即可。

注意代码细节，差分的下一个数是 j+i 没有 +1！

code

高维前缀和/差分

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} \]

code

P3397 地毯

diff:1

板子。

code

P2280 [HNOI2003] 激光炸弹

diff:1.5

坐标有0 坐标有0 坐标有0 坐标有0。记得对所有的数组偏移 \(1\)，不然 91 pts。

code

P1719 最大加权矩形

diff:1

板子。建议你谷课程题单减少板子题数量。

code

P3017 [USACO11MAR]Brownie Slicing G

diff:3.5 tag:贪心 性质 二分 前缀和

USACO 首先考虑贪心

二分答案，对于每一次 check，我们可以贪心。

具体的，先满足列的条件。如果该列在满足 \(\ge x\) 情况下无法 \(\ge b\) 块，那么加一行，注意每一块的范围是以 (上次分割行，上次分割列) 和 (枚举点行，枚举点列) 形成的长方形而不是一行连着取。是否满足条件即是否 \(\ge a\)。

前缀和即可。

因为少写 else 多交两发。

code

[ARC100E] Or Plus Max

diff:4 tag:sosdp 高维前缀和

牛逼题。参考链接1 参考链接2

考虑对每个 \(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 中加入一个 ! 取反即可。

code

树上差分

P3128 [USACO15DEC] Max Flow P

diff:2

我会树剖。

code

P3258 [JLOI2014] 松鼠的新家

diff:2

我也会树剖。

code

P2680 [NOIP2015 提高组] 运输计划

todo

P1600 [NOIP2016 提高组] 天天爱跑步

todo

离散化

P1097 [NOIP2007 提高组] 统计数字

diff:1

板子。

code

P1955 [NOI2015] 程序自动分析

diff:2.5 tag:并查集 离散化

diff=2.5 而不是 2 的原因是写挂了若干发。

我们只需要判断是否在不相等时能否满足，原因是显然的——等式具有传递性，所以我们事实上只需要维护相等这一个并查集即可。

离散化写了要用。并查集要写 f[i]=i。

fun fact:洛谷 #2 #10 放反了

code

标签：code,前缀,记录,sum,板子,tag,diff,24.07
From： https://www.cnblogs.com/ChthollyNS/p/18302235