题目链接：http://codeforces.com/contest/1296/problem/C
题意：给你一个字符串，是机器人的行走方式，现在要你删除一段连续字符，但机器人最后的终点不变，问你删掉的最短序列是哪一段。
最晚题目意思一直没看懂，以为只能删除前缀或者后缀。
思路：直接用map记录每个状态出现的位置，然后再选一段最短的就可以了。
#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<string> #include<algorithm> #include<queue> #include<map> typedef long long ll; using namespace std; char a[200005]; int main() { int t; scanf("%d",&t); while(t--) { map<int,map<int,int> >mp; int n; scanf("%d",&n); scanf("%s",a+1); int l,r; int x=0,y=0; int mi=n+2; for(int i=1; i<=n; i++) { if(a[i]==‘L‘) x--; else if(a[i]==‘R‘) x++; else if(a[i]==‘U‘) y++; else if(a[i]==‘D‘) y--; if(x==y&&x==0) { if(mi>i) { mi=i; l=0; r=i; } } if(mi>i-mp[x][y]&&mp[x][y]!=0) { mi=i-mp[x][y]; l=mp[x][y]; r=i; } mp[x][y]=i; } if(mi==n+2) printf("-1\n"); else printf("%d %d\n",l+1,r); } }
原文：https://www.cnblogs.com/zcb123456789/p/12264411.html