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

2021-08-08 19:42:25


目录

题号 题目 知识点 完成度
1008 HDU6992 Lawn of the Dead 队列
1004 HDU6988 Display Substring - 代码已通过,题意思路待补
1007 HDU6991 Increasing Subsequence - -
1005 HDU6989 Didn't I Say to Make My Abilities Average in the Next Life?! - -
1011 HDU6995 Travel on Tree - -
1003 HDU6987 Cycle Binary - -
1010 HDU6994 Pony Running x x
1006 HDU6990 Directed Minimum Spanning Tree x x

1008 HDU6992 Lawn of the Dead

题意

已知一个 $n\times m$ 的网格,一只僵尸初始在 $(1,1)$ 的位置上,只能向右或向下走,网格中 $k$ 颗地雷,不能移动到地雷上,求这只僵尸能够到达多少个格子。

思路

根据题意,可以发现地雷将每行格子分成了若干个区间,上一行的区间可以通过区间合并或拆开转化到下一行的区间,可以发现,区间的个数约为 $O(k+n)$ 个,复杂度刚好为 $O(t\times (n+k))$ ,可以通过。
具体来说,我们使用两个队列轮流来维护当前行的区间,另一个队列则为上一行的区间,每次将上一行的队列清空并通过合并、被地雷切开得到当前列的区间,并维护答案,直到最后一列。

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;
}