hdu7108哈希

添加链接描述

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int t,n;
char ch[maxn];
ll s;
map<pair<int,int>,int> pos;
int main()
{
	ll x,y;
	scanf("%d",&t);
	while(t--){
		x=y=0;
		s=0;
		while(!pos.empty()) pos.clear();
		pos[{0,0}]=1;
		scanf("%d",&n);
		scanf("%s",ch+1);
		for(int i=1;i<=n;i++){
			if(ch[i]=='U') y++;
			if(ch[i]=='D') y--;
			if(ch[i]=='L') x++;
			if(ch[i]=='R') x--;
			if(pos.count({x,y})==0) pos[{x,y}]=1;
			else{
				s+=pos[{x,y}];
				pos[{x,y}]++;
			}
		}
		printf("%lld\n",s);
	}
	return 0;
}