AT_abc384_e 题解

ikunTLE · 2024-12-14 21:53:53 · 题解

题面传送门

思路

不难想到以 (P,Q) 为起点 bfs，然后将每个点都枚举一遍能不能到达。然后这种做法在最差情况下可能每次会把每个点都枚举一遍，时间复杂度为 \mathcal{O}(H^2W^2)。

考虑贪心策略，每一次寻找该图形相邻点中强度最小的点进行吸收。因为如果该图形无法吸收这个点，那么它也不能吸收强度更大的点。

这种策略可以用优先队列实现，每次取最小的点判断是否可以被吸收。如果可以吸收，那么这个点周围的点放入队列中，并增加图形的强度；否则其他点也无法吸收，直接输出答案并结束程序。

这种做法的时间复杂度是 \mathcal{O}(HW\log HW)。

注意事项

• 设图形强度为 C，在计算 S_{i,j}<\frac{C}{X} 时为了控制精度，需要把不等式变为 S_{i,j}\times X<C，然而 S_{i,j}\times X 炸了 long long，需要在这一步开 __int128。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int __int128
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void unsigned_write(int x){if(x>9)unsigned_write(x/10);putchar(x%10+'0');return;}
const int N=505;
int s[N][N],dx[]={0,-1,1,0,0},dy[]={0,0,0,-1,1};
bool vis[N][N];
struct node{
    int x,y,num;
    friend bool operator>(const node cmp_x,const node cmp_y){
        return cmp_x.num>cmp_y.num;
    }
};priority_queue<node,vector<node>,greater<node>>pq;
signed main(){
    int n=read(),m=read(),x=read(),p=read(),q=read();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            s[i][j]=read();
    vis[p][q]=true;
    int power=s[p][q];
    for(int i=1;i<=4;++i){
        int xx=p+dx[i],yy=q+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){
            vis[xx][yy]=true;
            pq.push({xx,yy,s[xx][yy]});
        }
    }
    while(!pq.empty()){
        node u=pq.top();pq.pop();
        if(u.num*x>=power)
            return unsigned_write(power),0;
        power+=u.num;
        for(int i=1;i<=4;++i){
            int xx=u.x+dx[i],yy=u.y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){
                vis[xx][yy]=true;
                pq.push({xx,yy,s[xx][yy]});
            }
        }
    }
    unsigned_write(power);
    return 0;
}