题解：CF1202C You Are Given a WASD-string...

· · 题解

CF1202C You Are Given a WASD-string...

*2100

给你一个操作序列，求在任意位置插入一个 t\in WASD，使得包含路径的最小矩形的面积最小。

|s|\le 2\times 10^5

简单题，插入一个操作仅会将后面所有到达的位置向相应方向移动一格，于是记录前后缀相应坐标的最大最小值，然后求解时直接给后缀加上相应位移再计算面积即可。枚举所有的空隙以及操作符，时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
char s[maxn]; int dx[maxn],dy[maxn];
int posx[maxn],posy[maxn];
int pxmi[maxn],pymi[maxn];
int pxmx[maxn],pymx[maxn];
int sxmi[maxn],symi[maxn];
int sxmx[maxn],symx[maxn];
int dxl[]={1,-1,0,0},dyl[]={0,0,-1,1};
void solve(){
    cin>>s; int n=strlen(s);
    for(int i=1;i<=n;i++) dx[i]=s[i-1]=='W'?-1:(s[i-1]=='S'?1:0),dy[i]=s[i-1]=='A'?-1:(s[i-1]=='D'?1:0);
    for(int i=1;i<=n;i++){
        posx[i]=posx[i-1]+dx[i];
        posy[i]=posy[i-1]+dy[i];
        pxmi[i]=min(pxmi[i-1],posx[i]);
        pxmx[i]=max(pxmx[i-1],posx[i]);
        pymi[i]=min(pymi[i-1],posy[i]);
        pymx[i]=max(pymx[i-1],posy[i]);
    }
    sxmi[n]=sxmx[n]=posx[n];
    symi[n]=symx[n]=posy[n];
    for(int i=n-1;~i;i--){
        sxmi[i]=min(sxmi[i+1],posx[i]);
        sxmx[i]=max(sxmx[i+1],posx[i]);
        symi[i]=min(symi[i+1],posy[i]);
        symx[i]=max(symx[i+1],posy[i]);
    }
    long long ans=1ll*(pxmx[n]-pxmi[n]+1)*(pymx[n]-pymi[n]+1);
    for(int i=0;i<=n;i++){
        for(int j=0;j<4;j++){
            int tx=dxl[j],ty=dyl[j];
            int xl=min(sxmi[i]+tx,pxmi[i]),xr=max(sxmx[i]+tx,pxmx[i]);
            int yl=min(symi[i]+ty,pymi[i]),yr=max(symx[i]+ty,pymx[i]);
            ans=min(ans,1ll*(xr-xl+1)*(yr-yl+1));
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    int T; cin>>T; while(T--) solve();
    return 0;
}