P7715 「EZEC-10」Shape 题解

题目传送

并没有用标签的做法，属于乱搞做法，复杂度比较依赖数据。

Solution

\(O(n^5)\) 做法：

枚举 \(x_1,y_1,x_2,y_2\)，然后 \(O(n)\)判断是否合法。

\(O(n^4)\) 做法：

可以维护一个前缀和 \(O(1)\) 判断两个点之间是否都是 \(0\)。

\(O(n^3)\) 做法：

预处理一个 \(up_{i,j}\) 和 \(down_{i,j}\) 分别表示这个点向上和向下最多延伸的距离。取 \(\min\) 就可以得到该点的最大延伸距离 \(h_{i,j}\)。

考虑枚举每一条长度为 \(0\) 的横线 \([l,r]\)，假设这条横线在第 \(i\) 行，那么这条横线的贡献就是两个端点的最大延伸距离的较小值。即 \(\min(h_{i,l},h_{i,r})\)。

枚举行数加上枚举每条横线的两个端点，总复杂度 \(O(n^3)\)。

\(O(n^2) \sim O(n^3)\) 的做法

发现每次枚举到一条横线只是计算了它两端点的贡献，考虑把横线上两点之间的贡献一起算。

如果固定一个点 \(x\)，考虑它对横线上其他点 \(y\) 的贡献。那么当且仅当 \(h_{i,x} \le h_{i,y}\) 时，这两个点形成的 “H” 的贡献为 \(h_{i,x}\)。

不过这样做当 \(h_{i,x} = h_{i,y}\) 时 \(h_{i,x}\) 的贡献会被计算两次，把这部分单独拿出来特判掉即可。

如何快速的找到 \(\ge h_{i,x}\) 的值的数量？

我这里使用的是桶排，把每个 \(h_{i,x}\) 放进桶里，从后向前做前缀和，\(h_{i,x}\) 位置对应的前缀和 \(-1\) 就是 \(\ge h_{i,x}\) 的值的数量。

这里我先找到了这段横线中最大的 \(h_{i,x}\)，可以在预处理前缀和的时候减少枚举量。

这个做法在随机数据下跑的很快，感谢出题人没有把我卡成 \(O(n^3)\)。

\(O(n^2 \log n)\) 的做法

如果把上面的横线放进树状数组维护，复杂度是稳定的 \(\log\) 。

Code

代码写的是倒数第二个做法。

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"<= 1; --i) {
        for(int j = m; j >= 1; --j) {
            if(a[i][j]) {
                down[i][j] = i;
            } else {
                down[i][j] = down[i + 1][j];
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            up[i][j] = min(i - up[i][j] - 1, down[i][j] - i - 1);
        }
    }
    
    for(int i = 1; i <= n; ++i) {
        a[i][m+1] = 1;
        for(int j = 1, l = 1, r = 0; j <= m + 1; ++j) {
            if(a[i][j]) {
                if(l < r) {
                    int Sum = 0, Sum2 = 0;
                    memset(cnt, false, sizeof cnt);
                    int Max = -1;
                    for(int g = l; g <= r; ++g) cnt[up[i][g]] ++, Max = max(Max, up[i][g]);
                    for(int g = Max; g >= 0; --g) cnt[g] += cnt[g + 1];
                    for(int g = l; g <= r; ++g) Sum2 += up[i][g] * (cnt[up[i][g]] - cnt[up[i][g]+1] - 1), Sum += up[i][g] * cnt[up[i][g] + 1];
                    Ans += Sum + Sum2 / 2;
                }
                l = r = j + 1;
            } else {
                r = j;
            }
        }
    }
    printf("%lld", Ans);
    return 0;
}

P7715 「EZEC-10」Shape 题解

Solution

Code

相关

标签