Wuyanru's blog
0%

[QOJ10518] 腐蚀与膨胀

发表于 分类于 ，

作业题，知道咋做之前感觉很牛，知道之后感觉有点无语。

题目链接。

题意

初始有一个 的 矩阵，后续有 次操作。

  1. 给定一个 ，若某个点周围有与其切比雪夫距离不超过 的 ，则这个点变成 ，所有点同时更改；
  2. 给定一个 ，若某个点周围有与其切比雪夫距离不超过 的 ，则这个点变成 ，所有点同时更改。

需要回答所有操作之后这个矩阵长什么样子。

，。

题解

考虑如果有两个相邻的 操作，那么我们显然可以将这两个操作合并。

再考虑如果出现了 这样的操作，我们也可以将其替换成 。

正确性考虑初始为 的位置，其在操作之后一定还是 。

对于初始为 的位置，考虑初始的时候其周围不超过 的位置是否有 。

如果有，那么操作之后这个位置一定是 ；如果没有，那么操作之后这个位置一定是 。

那么如果出现了 ，其中 ，我们也可以将其替换成 。

执行所有能操作的操作之后，剩余的操作的 一定是先上升再下降。

那么此时操作序列序列存在两种情况。

  1. 操作中最大的 不超过 ，则此时操作序列长度不超过 ，暴力模拟即可。
  2. 操作中最大的 超过 ，那么其前面一定有不超过 个操作，前面暴力模拟一下即可。

时间复杂度 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int dx[8]={1,-1,0,0,-1,-1,1,1};
int dy[8]={0,0,1,-1,-1,1,-1,1};
bool ty[1000005];
ll sta[1000005];
int top;
bool vis[505][505];
int dis[505][505];
char s[505][505];
int n,q;
inline void bfs(int ty,int k)
{
    memset(dis,0x3f,sizeof(dis));queue<pi>que;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(s[i][j]-'0'==ty) que.push(pi(i,j)),dis[i][j]=0;
    while(!que.empty())
    {
        int x=que.front().first;
        int y=que.front().second;
        que.pop();
        if(dis[x][y]==k) continue;
        for(int i=0;i<8;i++)
        {
            int vx=x+dx[i],vy=y+dy[i];
            if(vx<1||vx>n||vy<1||vy>n) continue;
            if(dis[vx][vy]<=dis[x][y]+1) continue;
            dis[vx][vy]=dis[x][y]+1,que.push(pi(vx,vy));
            s[vx][vy]=ty+'0';
        }
    }
}
int main()
{
    int T=read();
    while(T--)
    {
        top=0,n=read(),q=read();
        for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
        for(int i=1;i<=q;i++)
        {
            int op=read();ll k=read();
            if(!top) sta[++top]=k,ty[top]=op;
            else
            {
                if(ty[top]==op) k+=sta[top--];
                while(top>=2&&sta[top-1]>=sta[top]&&sta[top]<=k)
                {
                    k=k+sta[top-1]-sta[top];
                    top-=2;
                }
                sta[++top]=k,ty[top]=op;
            }
        }
        for(int i=1;i<=top;i++)
        {
            bfs(ty[i],sta[i]);
            int ans=0;
            for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) ans+=s[j][k]-'0';
            if(ans==0||ans==n*n) break;
        }
        for(int i=1;i<=n;i++) printf("%s\n",s[i]+1);
    }
    return 0;
}