当前位置: 代码迷 >> 综合 >> E. Expand the Path ----Educational Codeforces Round 123 (Rated for Div. 2)
  详细解决方案

E. Expand the Path ----Educational Codeforces Round 123 (Rated for Div. 2)

热度:11   发布时间:2023-11-22 03:41:04.0

观察样例我们不难发现,关键点在于未偏移的时候的最右下角的坐标(若其触边界),如右边界,则无法整体右移,其他同理,接着分析如何计算覆盖的点,举个例子:当初始操作为D时,

当还未遇到R之前,不适合进行偏移,那么就会有部分空白面积,

当遇到R之后,可以计算第一个R之后右移动了多少记为cx,下移动了多少记为cy,留白面积就是cx*cy 可以自己造个样例去看看 我可以给个(6,DDDRRD),画个图就可以理解了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=200005;
int t,n;
char s[N];
signed main(){scanf("%lld",&t);while(t--){scanf("%lld%s",&n,s);int k=1,ans=0,cx=0,cy=0;while(k<strlen(s)&&s[k]==s[k-1])k++;if(k==strlen(s)){printf("%lld\n",n);continue;}for(int i=k;i<strlen(s);i++){if(s[i]=='R')cy++;else cx++;}ans+=k*(n-1);ans+=cx*cy;printf("%lld\n",n*n-ans);}return 0;
}

  相关解决方案