题目链接
题目大意
给你一个字符串只有UDLR代表一个机器人可以上下左右 问你有多少个字串让机器人运动后可以回到原点
题目思路
机器人运动后回到原点那么 需要保证字串 s（i，j）关于LR和UD的前缀和 一定相等
即sum1[i]-sum1[j-1]=0
sum2[i]-sum2[j-1]=0
先考虑UD的情况对于每一种相等的 前缀和 将其存在桶里
这种桶存储方式昨天刚做一道今天比赛就用上了
然后对于UD的每一个桶计算 LR的前缀和相同的点的数量x
ans+=x*(x-1)/2;
代码注释很详细
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
const int maxn=4e5+10;
int sum1[maxn];
int sum2[maxn];
map<int ,vector<int > >m;
map<int ,int >m2;
int a[maxn],b[maxn];
void init()
{m.clear();
}
int main()
{cin>>t;while(t--){init();int n;cin>>n;int cnt=0;int cnt2=0;char c[maxn];scanf("%s",c+1);sum1[0]=1e5;sum2[0]=1e5;for(int i=1;i<=n;i++){sum1[i]=sum1[i-1];sum2[i]=sum2[i-1];if(c[i]=='U'){sum1[i]=sum1[i-1]+1;}else if(c[i]=='D'){sum1[i]=sum1[i-1]-1;}else if(c[i]=='L'){sum2[i]=sum2[i-1]-1;}else {sum2[i]=sum2[i-1]+1;}} for(int i=0;i<=n;i++){m[sum1[i]].push_back(i);if(m[sum1[i]].size()==1){a[++cnt]=sum1[i];}}sort(a+1,a+cnt+1);//cout<<cnt<<endl;ll ans=0;for(int i=1;i<=cnt;i++)//离散化一下第一个前缀和不同值数量{int now=a[i];cnt2=0;m2.clear();for(int j=0;j<m[a[i]].size();j++)//对于每一个值的数量{int val=m[now][j];//找到下标m2[sum2[val]]++;//对于该下标第二个前缀和的值的数量++if(m2[sum2[val]]==1)b[++cnt2]=sum2[val]; //离散化一下第二个前缀和不同值数量}for(int j=1;j<=cnt2;j++){ll tmp=ll(m2[b[j]])*ll(m2[b[j]]-1)/2;ans+=tmp;}}cout<<ans<<endl;}return 0;
}