题解 CF1202C

不错的题，需要点思维和码力。

容易发现，左右和上下互不影响，可以分开处理，这里以左右举例。

定义向左走一格 \(-1\)，向右走一格 \(+1\)，求个前缀和找到最大值和最小值，和出现最值的最早时间与最晚时间。定义为 \(l,r,l2,r2\)。

只有当我们放了一个 A 或 D 使得所有最大值 \(-1\) 且最小值不变，或最小值 \(+1\) 且最大值不变时，面积才会减小。

假如我们要让最大值 \(-1\)，那么当且仅当 \(r<l2\) 且在坐标 \((r,l2)\) 中存在一个数不等于 \(r\) 对应的值时满足。原理很简单，不过多解释。

其他情况同理。

复杂度 \(O(n)\)。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll T,n,sum[N],sum2[N];
string s;
bool chk(int l,int r){
  for(int i=l+1;i<=r;++i)if(sum[i]!=sum[l])return true;
  return false;
}
bool chk2(int l,int r){
  for(int i=l+1;i<=r;++i)if(sum2[i]!=sum2[l])return true;
  return false;
}
int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>T;
  while(T--){
    cin>>s;n=s.size();s="."+s;
    ll ma=0,mi=0,ma2=0,mi2=0;
    for(int i=1;i<=n;++i){
      sum[i]=sum[i-1];
      if(s[i]=='A')--sum[i];
      if(s[i]=='D')++sum[i];
      ma=max(ma,sum[i]);mi=min(mi,sum[i]);
      sum2[i]=sum2[i-1];
      if(s[i]=='S')--sum2[i];
      if(s[i]=='W')++sum2[i];
      ma2=max(ma2,sum2[i]);mi2=min(mi2,sum2[i]);
    }
    int l=1e9,r=-1e9,l2=1e9,r2=-1e9;
    for(int i=0;i<=n;++i){
      if(sum[i]==mi)l=min(l,i),r=max(r,i);
      if(sum[i]==ma)l2=min(l2,i),r2=max(r2,i);
    }
    ll tot=(ma2-mi2+1)*(ma-mi+1),ans=tot;
    if((l>r2||r<l2)&&(chk(r2,l-1)||chk(r,l2-1)))ans=min(ans,tot-(ma2-mi2+1));
    l=l2=1e9;r=r2=-1e9;
    for(int i=0;i<=n;++i){
      if(sum2[i]==mi2)l=min(l,i),r=max(r,i);
      if(sum2[i]==ma2)l2=min(l2,i),r2=max(r2,i);
    }
    if((l>r2||l2>r)&&(chk2(r2,l-1)||chk2(r,l2-1)))ans=min(ans,tot-(ma-mi+1));
    cout<<ans<<endl;
  }
  return 0;
}