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

Sun_wtup · 2023-08-09 21:19:23 · 题解

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

题目传送

题意

有一个机器人，给出一个只由 \texttt{WASD} 组成的字符串控制它行走。\texttt{W} 代表上，\texttt{S} 代表下，\texttt{A} 代表左，\texttt{D} 代表右。可以在给定的字符串中加入这四个字母中的一个（也可以不加），改变机器人行动轨迹，使其经过的所有矩形面积最小。

分析与思路

我们可以把字符串中的上下走和左右走的分开，分别统计最上面，最下面，最左面，最右面到达的位置（假设初始位置为 0，0）。然后把横着走的（即左右走）和竖着做的（即上下走的）单独拎出来看。我们要判断能不能减小走完后的长和宽,如果不能就输出原面积，如果能就取最小值输出。

实现

统计上下左右方向的最值很简单，接着最难得部分就是判断能不能缩小。我们定义 \texttt{W} 是 1，\texttt{S} 是 -1，\texttt{A} 是 -1，\texttt{D} 是 1。以样例的 \texttt{DSAWWAW} 举例，可以得到横着走的是 \texttt{DAA}，竖着走的是 \texttt{SWWW}，我们要想缩小矩形面积，长或宽，而长由最上面和最下面的值决定，宽由最左面和最右面的值决定。那么我们就需要缩小最大值，但最小值不动。或者扩大最小值，但最大值不动（因为 \texttt{A} 是 -1，\texttt{D} 是 1，所以最左面的值就是横着的最小值，最右面就是横着的最大值，同样对于竖着的，最上面就是最大值，最下面就是最小值）。

先处理横着的，想要变小最大值，就必须在它第一次出现之前插入一个能使最大值变小的字母，而且不能在最小值最后一次出现之前插入，因为这样会使最大值与最小值同时变大或变小，极差还是没有变（例如\texttt{ADAADDD}，这时两个最值出现的时间分别是 4 和 7，如果在第三个 \texttt{A} 前加一个 \texttt{D}，就会使后面的值都加 1，最小值是 -1，最大值是 2，两个最值同时变化同时变化同样的值，极差不变）。类似的，若果想变大最小值，就要在它第一次出现之前处理，且在最大值最后一次出现之后处理。还有一种特殊情况，就是一个最值第一次出现的时间与另一个最值最后一次出现的时间相差 1，这种情况也不能缩小极差，换句话说无法缩小面积。然后我们要就记录最大值和最小值第一次和最后一次出现的时间，判断一个最值第一次出现的时间-另一个最值最后一次出现的时间是否大于 1，然后再把这一个第最值一次出现的时间改为最后一次出现的时间，另一个同理，再比较一遍，只要满足一个，就能缩小极差了。

竖着的同理，最后在给这两种情况（减小横着的极差，减小竖着的极差）取最小值即可（不减小的答案为（最右面-最左面+1）\times（最上面-最下面+1））。

Code

#include <bits/stdc++.h>
//#include <windows.h>
//#include <psapi.h>
//#include <time.h>
using namespace std;
#define debug(x) std::cerr<<#x<<'='<<x<<std::endl
#define int long long
int sideway,vertical;//分别为横，竖
int up,down,lft,rigt;
int upfirstime,downfirstime,leftfirstime,rightfirstime;
int uplastime,downlastime,leftlastime,rightlastime;
string  reset(string a){//将字符串改为从 1 开始
    string t="+";
    for(int i=0;i<a.size();i++)t+=a[i];
    a="";
    a+=t;
    return a;
}
void clear(){//清空
    sideway=vertical=0;
    up=down=lft=rigt=0;
    upfirstime=downfirstime=leftfirstime=rightfirstime=0;
    uplastime=downlastime=leftlastime=rightlastime=0;
}
void handle(string a){//记录每个最值的两个时间
    for(int j=1;j<=a.size();j++){
        if(a[j]=='W')vertical++;
        else if(a[j]=='S')vertical--;
        else if(a[j]=='A')sideway--;
        else if(a[j]=='D')sideway++;
        if(vertical>up)up=vertical,upfirstime=j;
        if(vertical==up)uplastime=j;
        if(vertical<down)down=vertical,downfirstime=j;
        if(vertical==down)downlastime=j;
        if(sideway>rigt)rigt=sideway,rightfirstime=j;
        if(sideway==rigt)rightlastime=j;
        if(sideway<lft)lft=sideway,leftfirstime=j;
        if(sideway==lft)leftlastime=j;
    }
    // debug(vertical);
    // debug(sideway);
}
signed main()
{
//  freopen("Luogu_CF_1202_C.cpp.in","r",stdin);
//  freopen("Luogu_CF_1202_C.cpp.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    string a;
    for(int i=1;i<=n;i++){
        cin>>a;
        int ans=0;
        a=reset(a);
    //    cout<<a<<" ";
        clear();
        handle(a);
        ans=(up-down+1)*(rigt-lft+1);//不减小的面积
        if(leftfirstime-rightlastime>1 or rightfirstime-leftlastime>1)ans=min(ans,(up-down+1)*(rigt-lft));
        if(upfirstime-downlastime>1 or downfirstime-uplastime>1)ans=min(ans,(up-down)*(rigt-lft+1));
        cout<<ans<<"\n";//判断，取最小值
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

本蒟蒻水平有限，如有不周之处，希望能原谅。