2021“MINIEYE杯”中国大学生算法设计超级联赛(1) 杭电多校1 题解

2021-07-24 02:36:24


目录

题号 题目 知识点 完成度
1008 HDU6957 Maximal submatrix 悬线法/单调栈 单调栈已完成
1010 HDU6959 zoto 莫队+分块/树状数组 莫队+树状数组做法已完成
1009 HDU6958 KD-Graph Kruskal -
1006 HDU6955 Xor sum 01trie -
1007 HDU6956 Pass! - -
1011 HDU6960 Necklace of Beads - -
1004 - - -
1003 - - -
1002 - - -

1008 HDU6957 Maximal submatrix

思路1:单调栈法

首先预处理出 自该位置向上 满足性质的数 的个数,记为 $h[i][j]$
对于每行 ( $h[i]$ ) 维护一个单调(递增)栈,所有元素进栈和出栈一次,每个元素出栈时更新最大的矩形面积。
为了能够更新最大的矩形面积,我们需要在栈内记录两个数据——元素的高度 $h[i][j]$​ 和它到栈中上一个元素的宽度差。
元素出栈时,因为高度逐渐递减,故记 $width$ 为当前已经弹出的元素的宽度和

code1(单调栈法)

#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 2e3 + 7;
int t, n, m, v[maxn][maxn], h[maxn][maxn], ans, top, s[maxn], w[maxn];
void solve(int x)
{
    s[top = 0] = 0;
    h[x][m + 1] = 0;
    for (int i = 1; i <= m + 1; ++i)
    {
        int width = 0;
        while (h[x][i] < s[top])
        {
            width += w[top];
            ans = max(ans, s[top--] * width);
        }
        s[++top] = h[x][i];
        w[top] = width + 1;
    }
}
int main()
{
    for (scanf("%d", &t); t--;)
    {
        ans = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
            {
                scanf("%d", &v[i][j]);
                if (v[i][j] >= v[i - 1][j])
                    h[i][j] = h[i - 1][j] + 1;
                else
                    h[i][j] = 1;
            }
        for (int i = 1; i <= n; ++i) solve(i);
        printf("%d\n", ans);
    }
    return 0;
}

思路2(悬线法)

待补

code2(悬线法)

1010 HDU6959 zoto

题意

已知平面上有 $n$ 个点,分别为 $(i,fx[i])$,现在有 $m$ 个询问,每个询问为一个矩形,统计矩形内的点有多少个不同的 $y$ 值。

思路1(莫队+树状数组)

首先,看到数据量很容易想到莫队的根号算法,但是二维莫队并不好 $O(1)$ 同时维护 $x$ 值和 $y$ 值的变化,因此我们先不考虑 $y$ 值,只考虑 $x$ 值,发现 $x$ 值可以使用一个典型的莫队算法维护,剩下便是 $y$ 值如何维护了。
每个询问其实就是询问 $[y1,y2]$ 间有多少个不同的 $y$ 上有点,我们考虑开 $10^5$ 个桶来记录某个 $y$ 上有多少个点,然后当桶中的值由 $1$ 变 $0$ 或由 $0$ 变 $1$ 的时候用树状数组/线段树来维护某个 $y$ 是否有值,可以发现在点数较多的情况下对树状数组的修改其实较少,这样每次区间移动便可以做到近似 $O(1)$ 的修改。
至此,本题便完成了,最差复杂度 $O(n\sqrt n \log n)$。

code1(莫队+树状数组)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 7;
int t, n, m, f[maxn], num[maxn], bucket[maxn], ans[maxn], B, belong[maxn];
struct Node
{
    int id, l, r, ql, qr;
    bool operator<(const Node &rhs) const
    {
        if (belong[l] != belong[rhs.l]) return belong[l] < belong[rhs.l];
        return r < rhs.r;
    }
} q[maxn];
void build()
{
    B = n / sqrt(m);
    for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;
}
int query(int x)
{
    int ans = 0;
    for (; x > 0; x -= x & -x) ans += num[x];
    return ans;
}
void add(int x)
{
    ++bucket[x];
    if (bucket[x] == 1)
        for (; x < maxn; x += x & -x) ++num[x];
}
void del(int x)
{
    --bucket[x];
    if (!bucket[x])
        for (; x < maxn; x += x & -x) --num[x];
}
int main()
{
    for (scanf("%d", &t); t--;)
    {
        scanf("%d%d", &n, &m);
        memset(bucket, 0, sizeof(bucket));
        memset(num, 0, sizeof(num));
        build();
        for (int i = 1; i <= n; ++i) scanf("%d", &f[i]), ++f[i];
        for (int i = 0, x0, y0, x1, y1; i < m; ++i)
        {
            scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
            q[i] = {i, x0, x1, y0, y1};
        }
        sort(q, q + m);
        for (int i = 0, l = 1, r = 0; i < m; i++)
        {
            while (r < q[i].r) add(f[++r]);
            while (r > q[i].r) del(f[r--]);
            while (l < q[i].l) del(f[l++]);
            while (l > q[i].l) add(f[--l]);
            ans[q[i].id] = query(q[i].qr + 1) - query(q[i].ql);
        }
        for (int i = 0; i < m; ++i) printf("%d\n", ans[i]);
    }
    return 0;
}

思路2(莫队+分块)

code1(莫队+分块)