腾飞营 day1(1) 基础算法

讲师：王浩清。

P6600

考虑枚举 T 中心的位置。

对于中心点，找出最长的横向长度和纵向长度，即维护每个位置向左/向右/向下有多少连续的 1。

重要的一步转换：对于所有 \((h,w)\)，提前建出一个 \(h\times w\) 的矩阵，若 \((h,w)=1\) 代表是一组合法的，否则不合法。

对于上界的限制，可以转换为求子矩阵和，前缀和即可。

时间复杂度 \(O(nm)\)。

有两个长度为 \(n\) 的 \(a\) 和 \(b\)，一次操作可以 \(a_{i-1}\leftarrow a_{i-1}+a_i\)，\(a_i\leftarrow -a_i\)，\(a_{i+1}\leftarrow a_{i+1}+a_i\)。问是否可以令 \(a=b\)。

一种比较经典的 trick，令 \(S\) 代表前缀和，可以发现一次操作本质上为交换 \(S_{i-1}\) 和 \(S_i\) 的值。差分、前缀异或也可以利用这个 trick。

快速判断两个序列是否相同：排序一下看对应位置是否相等。

NOIP2021 方差 第一步就是交换方差

要对这种式子保持敏感。

高维前缀和

用 \(k\) 元组 \((id_1,id_2,\cdots,id_k)\) 表示下标。\(0\le id_i\le m_i\)，求解 \(\forall i,id_i\le q_i\) 的权值和。

考虑一维到二维本质上是容斥，也可以对 \(k\) 维容斥，但复杂度下界为 \(\prod m_i \times 2^k\)。

考虑 dp，令 \(f_{i,(j_1,j_2,\cdots,j_k)}\) 代表在 \(j\) 状态下，前 \(i\) 位全部不大于 \(j_i\)，后 \(k-i\) 位全部等于 \(j_i\) 的权值和。

转移没听懂，\(f_{i,(j_1,j_2,\cdots,j_k)}=f_{i,(j_1,j_2,\cdots,j_i-1,\cdots,j_k)}+w_{j_1,j_2,\cdots,j_k}\)。

\(f_{i,(j_1,j_2,\cdots,0,\cdots,j_k)}=f_{i-1,(j_1,j_2,\cdots,0,\cdots,j_k)}\)。

时间复杂度 \(k\times \prod m_i\)。

总之类似一个 floyd 之类的东西。

最常见的是 \(m_i=1\)，子集求和。

CF1208F

二进制确定最大的 trick：从高位向低位枚举，一一确定。

定义广义上的二进制集合的属于关系为：

• 若 \(A\subset B\)，则 \(\forall i,A_i\le B_i\)。

考虑已经确定好了前 \(i\) 位，答案为 \(x\)，则要判断 \(x\cup{\text{第 i+1 位为 1 的二进制集合}}\subset d_i|(d_j&d_k)\) 是否成立。

即给出一个二进制，看是否存在 \(i<j<k\) 满足关系。

对于 或 运算，可以看作 \(d_i\) 占了目标二进制中的某些 1，所以枚举这些 1；\(d_j&d_k\) 占了 \(x^I\) 中的 1。

维护 \(S1_{j_1,\cdots,j_k}\) 代表满足 \((j_1,\cdots,j_k)\subset x\) 中下标最小的 x，\(S2_{\cdots}\) 代表满足 …… 中下标最大的 x，\(S3_{\cdots}\) …… 下标次大的 x。

判断 \(S1\) 和 \(S3\) 的大小关系即可。

时间复杂度 \(O(V\log V)\)，具体复杂度分析可以借鉴子集求和，笔者博客园里有。

半在线高维前缀和

显然听不懂。

国王游戏

博客园里有。

皇后游戏

贪心。

发现序列递增，要最小化最后一个数。

然后 sb 推式子。

发现一个没有可传递性的东西。

然后听不懂。

基础算法太难了。

去看数学了。