2023 国庆集训 Day 4B 笔记

RyanLi · 2023-10-07 17:11:21 · 个人记录

更佳的阅读体验：2023 国庆集训 Day 4B 笔记，本文同步发表于 洛谷博客。

以下内容为个人总结，如有错误或您有不同见解，欢迎指出。

单调队列优化 DP

洛谷 P1886 - 单调队列

int a[N];
deque<int> q;  // 存每个数的下标

for (int i = 1; i <= n; ++i) {
    while (!q.empty() && q.front() <= i - k) q.pop_front();
    while (!q.empty() && a[q.back()] <= a[i])       q.pop_back();
    q.push_back(i);
    cout << a[q.front()] << '\n';
}

洛谷 P2216 - 理想的正方形

洛谷 P2219 - 修筑绿化带

• 求出每一块花园中，花坛应该放在哪里。如果花园的右下角为 (x, y)，那么花坛的右下角就应位于 (x - a + c + 1, y - b + d + 1) \sim (x - 1, y - 1) 这个矩形内。
• 求出这个矩形内最小的 sum。

求最大全 0 正方形

给定一个 0 / 1 矩阵，求出最大的全为 0 的子正方形，求不带 \log 的做法。

带 \log 的做法：枚举每个点作为左上角，二分正方形边长。

• 令 f[i][j] 表示矩形 (i, j) 位置往下延伸 0 的个数，得到转移方程 f[i][j] = \begin{cases} 0, a_{i, j} = 1 \\ f[i + 1][j] + 1, a_{i, j} = 0 \end{cases}。
• 枚举正方形的上边界 u，依次从 1 \sim n 枚举正方形的右边界。
• 维护一个左边界的指针，并用单调队列维护左右边界之中的 f 值，需要时刻保证 r - l + 1 \le \min ⁡f 。
• 复杂度为 O(n^2 )。

带修版本：洛谷 P4259 - 寻找车位

洛谷 P2254 - 瑰丽华尔兹

• 设 f[t][i][j] 为 t 时刻到达 (i, j) 的最长路程。
• 假如 t 时刻钢琴是往上方滑动，那么 f[t][i][j] = \max (f[t - 1][i + 1][j] + 1, f[t - 1][i][j])。往其他方向同理。
• 复杂度为 O(nmT)。
• 由于时间可以被分为 K 段，每段滑动方向相同，则可以修改状态，令 f[k][i][j] 为第 k 个时间段结束后到达 (i, j) 的最长路程。
• 复杂度 O(nmK)。

// 不考虑障碍 且只考虑向上的转移

for (int k = 1; k <= K; ++k) {
    int t_k;
    for (int j = 1; j <= m; ++j) {
        deque<int> q;
        int g[];
        for (int i = 1; i <= n; ++i) g[i] = f[k - 1][i][j] + i;
        for (int i = n; i; --i) {
            while (!q.empty() && q.front() > i + t_k) q.pop_front();
            while (!q.empty() && g[q.back()] <= g[i]) q.pop_back()
            q.push_back(i);
            f[k][i][j] = g[q.front()] - i;
        }
    }
}

洛谷 P4381 - Island

• 求若干个基环树的直径之和。
• 对于一个基环树，找到它的环，求出环上每个节点 i 环外延伸的最长距离 d_i。
• 将长为 m 的环破为长为 2m 的链。如果从节点 i 外面走到节点 j 外面，则距离为 j - i + d_i + d_j，同时要求 i < j < i + n。使用单调队列优化求解。
• 复杂度为 O(n)。

单调队列优化多重背包

一共有 c_i 个 i 号物品，有 w_i 的价值和 v_i 的体积。

洛谷 P5665 - 划分

• 贪心地使最后一段的和尽可能小。
• 不严谨证明：如果最后一段 [l, r] 的和没到达下界，那么可以不断地把 a_l 分给前一段。由于 s_i < s_{i+1}，分给前一段的贡献是 2a_l s_i，分给后一段的贡献是 2a_l s_{i+1}，则分给前一段更优，同时分给前一段也有利于后面的分段。
• 所以设 f[r] 为 \max⁡ {l-1: 最后一段分成 [l, r] 可行}，应有 sum_r - sum_{l-1} \ge sum_{l-1}-sum_{f[l-1]}，即 sum_r \ge 2sum_{l-1} - sum_{f[l-1]}，双指针即可。
• 复杂度为 O(n)。

计数 DP

洛谷 P5824 - 十二重计数法

洛谷 P3702 - 序列计数

• 用总方案数去掉不含质数的方案数。
• 分别用 DP 求解，设 f[i][j] 为 i 个数字，和 \mod p = j 的方案数，矩阵快速幂加速。
• 复杂度 O(p^3 \log⁡ n )。

洛谷 P3773 - 吉夫特

• 由 Lucas 定理可知 C_n^m 是奇数 ↔(n\&m)=m。
• 设 f[T] 表示结尾值为 S 的序列个数，转移时枚举子集 T，如果 pos[S] < pos[T] 则令 f[T] 加上 f[S]。
• 复杂度为 O(3^w)。

int a[N], pos[N];

cin >> n;
for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pos[a[i]] = i;
}

for (int s = VALUE_MAX; s; --s) {
    ++f[s];
    for (int t = (s - 1) & s; t; --t)
        if (pos[s] < pos[t]) f[t] += f[s];
    ans += f[s] - 1;
}

洛谷 P5664 - Emiya 家今天的饭

• 对「每种食材最多在一半菜中」进行容斥。用总的方案数减去某种食材过多的方案数，不会有两种食材同时过多。
• 总方案数易求。
• 枚举过多的食材种类 t，设 f[i][j][k] 表示前 i 种烹饪方法，一共做了 j 个菜，其中 k 个使用 t 的方案数。转移时枚举第 i + 1 种烹饪方法是否选用，选用时是否使用 t，最后要求 k > \frac{j}{2} 。
• 只需记录 2k - j 的值即可，最后要求此值 > 0。
• 复杂度为 O(n^2 m)。