题解归档 - cf1202C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1202C
• 本地来源：problems/cf1202C/idea.md
• 题目链接：https://codeforces.com/contest/1202/problem/C
• 原始标题：CF 1202C — You Are Given a WASD-string...

思路

CF 1202C — You Are Given a WASD-string...

题意

给定 WASD 移动串 (s)，在网格上从某起点执行全部指令不越界所需的最小矩形面积记为 (Grid(s))。可额外插入 至多一个 字符（W/A/S/D 各一枚，四选一或不插），求最小面积。

关键观察：两维独立

• W/S 只改变纵坐标，A/D 只改变横坐标
• 矩形面积 = 纵轴跨度 × 横轴跨度
• 插入一个字母只影响其中一个维度（插 W/S 影响纵轴，插 A/D 影响横轴）
• 故答案 = (\min{W_y \cdot H_x,\ W_x \cdot H_y})，其中 (W) 为原跨度，(H) 为插入后该维最小跨度

一维子问题

将 W 视为 (+1)、S 视为 (-1)（横轴同理 D=+1, A=-1），得到前缀和 (p_i)。

• 原跨度：(\max p - \min p + 1)
• 至多插入一步 (\pm1)：枚举插入位置，或等价地维护「加一个向上/向下步后」的最小极差

实现上对每条 1D 串做两次（原方向与翻转 (p\leftarrow -p)，对应插入 (+1) 与 (-1)），并特判极差为 2 且最大值位置在最小值之前时可缩 1（插入消掉一端）。

样例

• DSAWWAW：横轴串 DAA，纵轴串 SWWW；最优在纵轴插 D 对应位置，面积 (2\times4=8)
• D → (2\times1=2)；WA → (2\times2=4)

复杂度

每组 (O(|s|))，总长度 (2\cdot 10^5)。

代码

来源：problems/cf1202C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:28:58
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s,a[2];
ll p[200005],t,n,i,j,k,ans,cur,dq,cnt,zc,pd,inf=1e9;
ll baseW[2],bestW[2];
int main(){
    cin>>t;
    while(t--){
        cin>>s;
        a[0]="";
        a[1]="";
        for(i=0;i<(ll)s.size();i++){
            if(s[i]=='W' or s[i]=='S') a[0]+=s[i];
            else a[1]+=s[i];
        }
        baseW[0]=baseW[1]=inf;
        bestW[0]=bestW[1]=inf;
        for(k=0;k<2;k++){
            p[0]=0;
            n=(ll)a[k].size();
            for(i=0;i<n;i++){
                if(a[k][i]==(k==0?'W':'A')) p[i+1]=p[i]+1;
                else p[i+1]=p[i]-1;
            }
            for(j=0;j<2;j++){
                cur=0;
                dq=0;
                for(i=0;i<=n;i++){
                    if(p[i]<p[cur]) cur=i;
                    if(p[i]>=p[dq]) dq=i;
                }
                zc=p[dq]-p[cur]+1;
                pd=zc;
                if(zc>2 and dq<cur) pd--;
                baseW[k]=min(baseW[k],zc);
                bestW[k]=min(bestW[k],pd);
                for(i=0;i<=n;i++) p[i]=-p[i];
            }
        }
        ans=min(baseW[0]*bestW[1],baseW[1]*bestW[0]);
        cout<<ans<<"\n";
    }
    return 0;
}