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

· · 题解

这道题简直是debug到吐血……

其实思路是很明晰+清新的，大概就是你考虑首先显然是行列无关的，所以分开考虑；接着你发现我们的最优策略肯定是让某一步相当于每走，但是假设我的x_{min}和x_{max}均在我这次改动操作的后面，那么我们尝试缩小活动范围，即缩小x_{max}的时候也会缩小x_{min}，相当于没缩——所以我们应找到一个界点，所有的最大值都在左/右边，对应的所有最小值都在右/左边。

于是我们考虑直接前缀和瞎搞就可以了。但是我debug了很久的原因是，这个问题他不是很完美，详细一些就是我们考虑无论怎么移动，都不能越过我们预处理出来的x_{min}、x_{max}这个界（否则会出现越贪越大）。也就是说，假设一开始我有一个x_{max}，接着过了一会儿有一个x_{min}，为了“拔高”x_{min}我们必须要添加一个W，所以我们必须要保证任何时刻不会出现x_{max}在放上一个W之后越界的情况，也就是说x_{min}和x_{max}出现的位置之间必须要一个S才能用来抵消掉我们W。

以上全都是以W/S作为例子的，A/D的情况分类讨论一下就好。

呃，废话有点多，但是实际上写起来挺好写的吧也需要一些时间：

#define MAXN 200010
#define LL long long
#define Inf 192608170

using namespace std ; LL ans ; 
int fhm, fhn, fwm, fwn, pos[2][5], i ; 
int T, N, Sw[MAXN], Sh[MAXN] ; char S[MAXN] ;

int main(){
    cin >> T ; 
    while (T --){
        fhm = fwm = -Inf, fhn = fwn = Inf ;  
        scanf("%s", S + 1), N = strlen(S + 1) ;
        for (i = 1 ; i <= N ; ++ i){
            Sh[i] = Sh[i - 1], Sw[i] = Sw[i - 1] ;
            if (S[i] == 'W') Sh[i] = Sh[i - 1] + 1 ; 
            else if (S[i] == 'S') Sh[i] = Sh[i - 1] - 1 ;
            else if (S[i] == 'D') Sw[i] = Sw[i - 1] + 1 ;
            else if (S[i] == 'A') Sw[i] = Sw[i - 1] - 1 ;
        }//前缀和 : w x h 
        for (i = 0 ; i <= N ; ++ i) fwm = max(Sw[i], fwm), fwn = min(Sw[i], fwn) ;
        for (i = 0 ; i <= N ; ++ i) fhm = max(Sh[i], fhm), fhn = min(Sh[i], fhn) ; 
        for (i = N ; ~i ; -- i) if (Sh[i] == fhn) { pos[0][4] = i ; break ; } //last_min h
        for (i = N ; ~i ; -- i) if (Sw[i] == fwn) { pos[1][4] = i ; break ; } //last_min h
        for (i = 0 ; i <= N ; ++ i) if (Sh[i] == fhm) { pos[0][1] = i ; break ; }  //first_max h
        for (i = 0 ; i <= N ; ++ i) if (Sw[i] == fwm) { pos[1][1] = i ; break ; }  //first_max w

        for (i = N ; ~i ; -- i) if (Sh[i] == fhm) { pos[0][3] = i ; break ; } //last_max h
        for (i = N ; ~i ; -- i) if (Sw[i] == fwm) { pos[1][3] = i ; break ; } //last_max h
        for (i = 0 ; i <= N ; ++ i) if (Sh[i] == fhn) { pos[0][2] = i ; break ; }  //first_min h    
        for (i = 0 ; i <= N ; ++ i) if (Sw[i] == fwn) { pos[1][2] = i ; break ; }  //first_min w
        ans = 1ll * (fwn - fwm - 1) * (fhn - fhm - 1) ; //cout << ans << endl ;
        if (pos[0][3] < pos[0][2] && Sh[pos[0][3]] - Sh[pos[0][2]] > 1) 
            ans = min(ans, 1ll * (fhm - fhn) * (fwm - fwn + 1)) ;
        if (pos[1][3] < pos[1][2] && Sw[pos[1][3]] - Sw[pos[1][2]] > 1) 
            ans = min(ans, 1ll * (fhm - fhn + 1) * (fwm - fwn)) ;
        if (pos[0][4] < pos[0][1] && Sh[pos[0][4]] - Sh[pos[0][1]] < -1) 
            ans = min(ans, 1ll * (fhm - fhn) * (fwm - fwn + 1)) ;
        if (pos[1][4] < pos[1][1] && Sw[pos[1][4]] - Sw[pos[1][1]] < -1) 
            ans = min(ans, 1ll * (fhm - fhn + 1) * (fwm - fwn)) ;
        cout << ans << endl ; 
        pos[0][1] = pos[1][1] = pos[0][2] = pos[1][2] = Inf ;
        pos[0][3] = pos[1][3] = pos[0][4] = pos[1][4] = -Inf ;
    }
}

嘤嘤嘤鬼知道我做这题时经历了什么啊qaq