20241023 总结

· · 个人记录

预期：200+，实际：212

P1886 滑动窗口 /【模板】单调队列

P4147 玉蟾宫

假设所有的 R 都在最上层，那么我们相当于有一些向上突起的矩阵，而问题便转换成在这些矩阵中找到最大子矩阵，这个我们可以用单调栈解决。

那么如果存在一些 R 把中间分割了不好做，我们可以考虑枚举中间的一些层作为最底下的一层，然后预处理以当前这一层作为最底层时每一个位置所在矩阵的高度，然后问题再次转换成最大子矩阵

死因：最大子矩阵忘记怎么求了

P3522 [POI2011] TEM-Temperature

考虑一种和贪心的搞法，我们将所有的都设为一个温度，那么这个时候就是区间并。

思考什么时候当前区间不能和之前的接上，当当前这个的右端点比之前的未被排除的左端点的最大值还要小，那么这个将接不上

我们发现要维护的是未被排除的左端点的最大值，那么我们发现可以用单调队列维护

考虑枚举右端点，按上述规则进行删数，此时我们就可以统计答案，用当前这个和队头计算就行了。

考虑如何将这个压入队列，我们只要用当前左端点和队尾左端点比较就行了，如果大一些，很明显队尾的无法再成为最大值。

不过有个小点，这个被删掉，不代表这个无法作为一个答案左端点，因为可能有一个很高的区间，把之前的所有区间全部杀掉了，但是我们是可以从一个较低的区间爬上来的，因为之前我们预设的是所有的都为一个温度，但是其实是可以上爬的，所以我们将最后一个被删掉的作为当前要压入的，就可以记录有关它的答案了，注意只是让它作为答案一部分，区间还是当前这个的区间

P10264 [GESP202403 八级] 接竹竿

暴力优化100分爽！

考虑维护下一个出现位置，那么每次直接跳下一个位置将中间的删掉就行了，考虑用倍增优化这个过程

考虑如何计算保留下来的答案，思考得到，用倍增优化的过程，会出现一些中间空着地方导致跳的时候会断层，而这段空着的就是我们的答案，所以这段空着的暴力跳就行了。

暴力跳不会寄吗？我们来想一个极端的情况，当当前跳的牌是 x 那么中间最多出现 12 种数就必须进行跳跃了，在发现如果跳过一次了，那么就证明不存在下一个了，而在 l 到 r 中不可能出现两个不存在下一个的相同牌，所以暴力跳最多 13 次

#include <iostream>

using namespace std;

const int MaxN = 1.5e4 + 10, MaxK = 21;

int f[MaxN][MaxK], p[MaxN], c[26], a[MaxN], t, n, q;

int query(int l, int r, int res = 0) {
    for (; l <= r; l++) {
        for (; l <= r && f[l][0] > r; l++, res++) {
        }
        if (l > r) break;
        for (int i = MaxK - 1; i >= 0; i--) {
            if (f[l][i] <= r) {
                l = f[l][i];
                break;
            }
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    for (cin >> t; t; t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int j = 1; j <= n; j++) {
            for (int i = 0; i < MaxK; i++) {
                c[i] = n + 1;
                f[j][i] = n + 1;
            }
        }
        for (int i = n; i >= 1; i--) {
            p[i] = c[a[i]], c[a[i]] = i;
            f[i][0] = p[i];
        }
        for (int j = 1; j < MaxK; j++) {
            for (int i = n; i >= 1; i--) {
                if (f[i][j - 1] + 1 <= n)
                    f[i][j] = f[f[i][j - 1] + 1][j - 1];
            }
        }
        cin >> q;
        for (int i = 1, l, r; i <= q; i++) {
            cin >> l >> r;
            cout << query(l, r) << '\n'; 
        }
    }
    return 0;
}

总结

对于一些带技巧的题目以后反复做，不要出现今天这种思路想到了，处理答案的时候把技巧用错了