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

思路

根据题意，我们发现，渔网的扩大实际如下图所示：

是一圈圈向外推的！
同时，我们发现：每过1秒，鱼游动的距离和网扩散的距离是相等的!
于是，通过大眼观察法，设放网位置为

(p,q)

，当前鱼的初始坐标为

(x_i,y_i)

，我们惊喜的发现了规律：

当鱼往L方向游动时，只要初始放网位置 $p \leq x_i$ ，该鱼即可被捕捉；
当鱼往R方向游动时，只要初始放网位置 $p \geq x_i$ ，该鱼即可被捕捉；
同理，当鱼往D方向游动时，只要初始放网位置 $q \leq y_i$ ，该鱼即可被捕捉；
当鱼往U方向游动时，只要初始放网位置 $q \geq 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

坐标分别进行离散化处理，这题就做完了。
注意多测要清空！！

更多细节详见代码吧。

代码

CPP

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

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

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

文章操作

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

思路

代码

相关推荐

评论

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

文章操作

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

思路

代码

相关推荐

评论

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