题解：P13557 【MX-X15-T4】炸鱼鱼

· · 题解

P13557 【MX-X15-T4】炸鱼鱼 题解

题目传送门

思路

根据题意，我们发现，渔网的扩大实际如下图所示： 是一圈圈向外推的！
同时，我们发现：每过1秒，鱼游动的距离和网扩散的距离是相等的!
于是，通过大眼观察法，设放网位置为 (p,q)，当前鱼的初始坐标为 (x_i,y_i)，我们惊喜的发现了规律：

这时我们开始查询网放在每一个位置上的答案。维护初始网的位置时，我们惊喜的发现，我们可以使用差分数组维护每一位置上的答案。
于是我们惊喜地发现，只需要维护两个差分数组 qx[],qy[] 即可，其中 mx=\sum_{i=1}^{x_p}qx[x_p] 表示网放在 x=x_p 处可捕捉到的向L，R方向游动的鱼数量，my=\sum_{i=1}^{y_p}qy[y_p] 表示网放在 y=y_p 处可捕捉到的向U，D方向游动的鱼的数量，而答案 ans 自然等于 \max{mx}+\max{my} 了。

然而这时我们又遇到了一个问题：x,y 的范围极其大：−10^9≤x_i,y_i≤10^9，而这么大的数据我们显然无法用数组存下，怎么办呢？
考虑到网的放置位置对答案的影响只与其和鱼的初始位置关系有关，我们可以将鱼的 x,y 坐标分别进行离散化处理，这题就做完了。
注意多测要清空！！

更多细节详见代码吧。

代码

#include <bits/stdc++.h>
using namespace std;
int n, t;
struct Fish
{
    int x, y;
    char d;
} f[200010];
bool cmpx(Fish a, Fish b)
{
    return a.x < b.x;
}
bool cmpy(Fish a, Fish b)
{
    return a.y < b.y;
}
int qx[200010], qy[200010];
signed main()
{
    cin >> t;
    while (t--)
    {
        for (int i = 1; i <= n; i++)
            qx[i] = 0, qy[i] = 0;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> f[i].x >> f[i].y >> f[i].d;
        }
        sort(f + 1, f + n + 1, cmpx);
        long long tmp = -1e9 - 5;
        for (int i = 1; i <= n; i++)
        {
            if (f[i].x == tmp)
                f[i].x = f[i - 1].x;
            else
                tmp = f[i].x, f[i].x = i;
        }//对x坐标离散化
        sort(f + 1, f + n + 1, cmpy);
        tmp = -1e9 - 5;
        for (int i = 1; i <= n; i++)
        {
            if (f[i].y == tmp)
                f[i].y = f[i - 1].y;
            else
                tmp = f[i].y, f[i].y = i;
        }//对y坐标离散化
        for (int i = 1; i <= n; i++)
        {
            if (f[i].d == 'L')
                qx[1]++, qx[f[i].x + 1]--;
            else if (f[i].d == 'R')
                qx[f[i].x]++;
            else if (f[i].d == 'U')
                qy[f[i].y]++;
            else
                qy[1]++, qy[f[i].y + 1]--;
        }//处理差分数组
        int nx = 0, ny = 0, mx = 0, my = 0;
        for (int i = 1; i <= n; i++)
        {
            nx += qx[i];
            ny += qy[i];
            mx = max(mx, nx);
            my = max(my, ny);
        }//前缀和求出最大答案
        cout << mx + my << "\n";
    }
    return O;
}

其实这题好像不至于到绿题（小声）……
这篇题解到这里就结束了，如有错误欢迎指正！