题解：AT_abc384_e [ABC384E] Takahashi is Slime 2

· · 题解

好题啊！

卡住了教练 10 分钟。

大概思路

我们注意到如果有一个小的一个大的，那么最优方案是先吃小的，在回头把大的吃掉。

所以我们可以使用小根堆。

因为我们数据范围非常惊人，可能使用除法会有精度问题，所以考虑乘法。

其余就是正常的广搜。

AC code

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define TRACE 1

#define tcout TRACE && cout

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define int long long

const int P = 998244353;

const int INF = 0x3f3f3f3f3f3f3f3f;

const int N = 1e6 + 10, M = 2e6 + 10;

const int dx[] = {0 , 0 , 1 , -1} , dy[] = {1 , -1 , 0 , 0} ;

int a[1000][1000] ;

bool vis[1000][1000] ; // 是否已经被吸收 

int n , m , X ;

int xs , ys ;

struct Node
{
    int x , y , s ;
    bool operator < (const Node& b) const
    {
        return s > b.s ;
    } ;
} ; //

int bfs ()
{
    priority_queue<Node > q ;
    for (int i = 0 ; i < 4 ; i ++)
    {
        int nx = xs + dx[i] ;
        int ny = ys + dy[i] ;
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0)
        {
            vis[nx][ny] = 1 ;
            q.push({nx , ny , a[nx][ny]}) ;
        }
    }
    vis[xs][ys] = 1 ;
    int cur = a[xs][ys] ;
    while (!q.empty())
    {
        auto[x , y , s] = q.top() ;
        //如果这个史莱姆能够吸收，那么访问四周元素
        if ((__int128)s * X <(__int128)cur)
        {
            q.pop() ;
            cur += s ;
            for (int i = 0 ; i < 4 ; i ++)
            {
                int nx = x + dx[i] ;
                int ny = y + dy[i] ;
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && vis[nx][ny] == 0)
                {
                    vis[nx][ny] = 1 ;
                    q.push({nx , ny , a[nx][ny]}) ;
                }
            }
        }
        else
        {
            break ;
        }
    }
    return cur ;
}

signed main()
{
    cin >> n >> m >> X ;
    cin >> xs >> ys ;
    for (int i = 1 ; i <= n ; i ++)
    {
        for (int j = 1 ; j <= m ; j ++)
        {
            cin >> a[i][j] ;

        }
    }
    cout << bfs() ;
    return 0;
}