AT_abc429_f

思路

感觉这题和这题是很像的，虽然那题我没有通过。

注意到如果只有三行，则不存在在中间绕路的情况。

所以考虑线段树，维护两列之间所有的位置答案。

对于每一个节点，不关心中间移动的具体过程，记

w_{i,j}

表示从最左边的第

i

行到最右边的第

j

行的最小步数，不可达记为无穷大。

合并显然有

3^3

的合并方法。

总复杂度

O(N\log N)

，带一个

27

倍左右的常数。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int w[8*N][3][3];
char a[3][N];
void pushup(int u)
{
    int x=u<<1,y=u<<1|1;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            w[u][i][j]=1e9;
            for(int k=0;k<3;k++)
                w[u][i][j]=min(w[u][i][j],
                    w[x][i][k]+w[y][k][j]+1);
        }
}
void build(int u,int l,int r)
{
    if(l==r)
    {
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)//初始化节点状态
            {
                bool flag=1;
                for(int k=min(i,j);k<=max(i,j);k++)
                    if(a[k][l]=='#')flag=0;
                if(flag)w[u][i][j]=abs(i-j);
                else w[u][i][j]=1e9;
            }
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void to(int u,int l,int r,int x,int t)
{
    if(l==r)
    {
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)//复制 build 里的代码
            {
                bool flag=1;
                for(int k=min(i,j);k<=max(i,j);k++)
                    if(a[k][l]=='#')flag=0;
                if(flag)w[u][i][j]=abs(i-j);
                else w[u][i][j]=1e9;
            }
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=x)to(u<<1,l,mid,x,t);
    else to(u<<1|1,mid+1,r,x,t);
    pushup(u);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,T;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[0][i];
    for(int i=1;i<=n;i++)cin>>a[1][i];
    for(int i=1;i<=n;i++)cin>>a[2][i];
    build(1,1,n);cin>>T;
    while(T--)
    {
        int x,y;
        cin>>x>>y;x--;
        if(a[x][y]=='#')a[x][y]='.';
        else a[x][y]='#';
        to(1,1,n,y,x);
        cout<<(w[1][0][2]==1e9?-1:w[1][0][2])<<'\n';
    }
    return 0;
}

文章操作

思路

代码

相关推荐

评论

AT_abc429_f