笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

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

posted on 2019-08-15 20:56:39 | under 题解 |

这道题简直是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