2021“MINIEYE杯”中国大学生算法设计超级联赛(4) 杭电多校4 题解
sdxjzsq
2021-08-08 19:42:25
## 目录
| 题号 | 题目 | 知识点 | 完成度 |
| ---- | ------------------------------------------------------------ | ------ | ------ |
| 1008 | HDU6992 [Lawn of the Dead](https://acm.hdu.edu.cn/showproblem.php?pid=6992) | 队列 | √ |
| 1004 | HDU6988 [Display Substring](https://acm.hdu.edu.cn/showproblem.php?pid=6988) | - | 代码已通过，题意思路待补 |
| 1007 | HDU6991 [Increasing Subsequence](https://acm.hdu.edu.cn/showproblem.php?pid=6991) | - | - |
| 1005 | HDU6989 [Didn't I Say to Make My Abilities Average in the Next Life?!](https://acm.hdu.edu.cn/showproblem.php?pid=6989) | - | - |
| 1011 | HDU6995 [Travel on Tree](https://acm.hdu.edu.cn/showproblem.php?pid=6995) | - | - |
| 1003 | HDU6987 [Cycle Binary](https://acm.hdu.edu.cn/showproblem.php?pid=6987) | - | - |
| 1010 | HDU6994 [Pony Running](https://acm.hdu.edu.cn/showproblem.php?pid=6994) | x | x |
| 1006 | HDU6990 [Directed Minimum Spanning Tree](https://acm.hdu.edu.cn/showproblem.php?pid=6990) | x | x |
## 1008 HDU6992 [Lawn of the Dead](https://acm.hdu.edu.cn/showproblem.php?pid=6992)
### 题意
已知一个 $n\times m$ 的网格，一只僵尸初始在 $(1,1)$ 的位置上，只能向右或向下走，网格中 $k$ 颗地雷，不能移动到地雷上，求这只僵尸能够到达多少个格子。
### 思路
根据题意，可以发现地雷将每行格子分成了若干个区间，上一行的区间可以通过区间合并或拆开转化到下一行的区间，可以发现，区间的个数约为 $O(k+n)$ 个，复杂度刚好为 $O(t\times (n+k))$ ，可以通过。
具体来说，我们使用两个队列轮流来维护当前行的区间，另一个队列则为上一行的区间，每次将上一行的队列清空并通过合并、被地雷切开得到当前列的区间，并维护答案，直到最后一列。
### code
```code
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 1e5 + 7;
int n, t, m, k;
int main()
{
for (scanf("%d", &t); t--;)
{
pair<int, int> p[maxn];
queue<pair<int, int>> Q[2];
long long ans = 0;
for (int i = 0; i < maxn; ++i) p[i].first = p[i].second = 0;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k; ++i) scanf("%d%d", &p[i].first, &p[i].second);
sort(p + 1, p + k + 1);
int now = 1;
if (p[now].first == 1)
Q[1].emplace(1, p[now].second - 1);
else
Q[1].emplace(1, m);
while (p[now].first == 1 && now <= k) ++now;
for (int i = 2; i <= n; ++i)
{
if (!Q[(i - 1) & 1].size()) break;
int _l, _r = 0;
while (p[now].first == i && now <= k)
{
_l = _r + 1;
_r = p[now].second;
if (!Q[(i - 1) & 1].size())
_l = m + 1;
else if (Q[(i - 1) & 1].front().first > _l)
_l = Q[(i - 1) & 1].front().first;
while (Q[(i - 1) & 1].size() && Q[(i - 1) & 1].front().second <= _r)
{
ans += Q[(i - 1) & 1].front().second - Q[(i - 1) & 1].front().first + 1;
Q[(i - 1) & 1].pop();
}
if (_l < _r) Q[i & 1].emplace(_l, _r - 1);
++now;
}
if (Q[(i - 1) & 1].size())
{
_l = _r + 1;
while (Q[(i - 1) & 1].size() && Q[(i - 1) & 1].front().second < _l)
{
ans += Q[(i - 1) & 1].front().second - Q[(i - 1) & 1].front().first + 1;
Q[(i - 1) & 1].pop();
}
if (Q[(i - 1) & 1].front().first > _l) _l = Q[(i - 1) & 1].front().first;
if (Q[(i - 1) & 1].size() && _l <= m) Q[i & 1].emplace(_l, m);
while (Q[(i - 1) & 1].size())
{
ans += Q[(i - 1) & 1].front().second - Q[(i - 1) & 1].front().first + 1;
Q[(i - 1) & 1].pop();
}
}
}
while (Q[n & 1].size())
{
ans += Q[n & 1].front().second - Q[n & 1].front().first + 1;
Q[n & 1].pop();
}
printf("%lld\n", ans);
}
return 0;
}
```