2021“MINIEYE杯”中国大学生算法设计超级联赛(1) 杭电多校1 题解
sdxjzsq
2021-07-24 02:36:24
## 目录
| 题号 | 题目 | 知识点 | 完成度 |
| ---- | ------------------------------------------------------------ | ---------------- | ------------ |
| 1008 | HDU6957 [Maximal submatrix](https://acm.hdu.edu.cn/showproblem.php?pid=6957) | 悬线法/单调栈 | 单调栈已完成 |
| 1010 | HDU6959 [zoto](https://acm.hdu.edu.cn/showproblem.php?pid=6959) | 莫队+分块/树状数组 | 莫队+树状数组做法已完成 |
| 1009 | HDU6958 [KD-Graph](https://acm.hdu.edu.cn/showproblem.php?pid=6958) | Kruskal | - |
| 1006 | HDU6955 [Xor sum](https://acm.hdu.edu.cn/showproblem.php?pid=6955) | 01trie | - |
| 1007 | HDU6956 [Pass!](https://acm.hdu.edu.cn/showproblem.php?pid=6956) | - | - |
| 1011 | HDU6960 [Necklace of Beads](https://acm.hdu.edu.cn/showproblem.php?pid=6960) | - | - |
| 1004 | - | - | - |
| 1003 | - | - | - |
| 1002 | - | - | - |
## 1008 HDU6957 [Maximal submatrix](https://acm.hdu.edu.cn/showproblem.php?pid=6957)
#### 思路1：单调栈法
首先预处理出 自该位置向上 满足性质的数 的个数，记为 $h[i][j]$
对于每行 ( $h[i]$ ) 维护一个单调(递增)栈，所有元素进栈和出栈一次，每个元素出栈时更新最大的矩形面积。
为了能够更新最大的矩形面积，我们需要在栈内记录两个数据——元素的高度 $h[i][j]$ 和它到栈中上一个元素的宽度差。
元素出栈时，因为高度逐渐递减，故记 $width$ 为当前已经弹出的元素的宽度和
#### code1（单调栈法）
```cpp
#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（悬线法）
```cpp
```
## 1010 HDU6959 [zoto](https://acm.hdu.edu.cn/showproblem.php?pid=6959)
#### 题意
已知平面上有 $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（莫队+树状数组）
``` cpp
#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（莫队+分块）
``` cpp
```