http://codeforces.com/contest/1296/problem/C
题意: 给一段字符串表示移动, 然后求删除最短的一段, 并且不影响结果
题解:
意思是: 建立 pair 点和 map, 当遍历到第 i 个点有一个 pair 值, 把这个加到 map 里面, 如果向后接着遍历时出现与 i 点相同的 pair 值时, 那么这一段表示可以删除的一段
- #include <bits/stdc++.h>
- using namespace std;
- int main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- #endif
- int t;
- cin>> t;
- while (t--) {
- int n;
- string s;
- cin>> n>> s;
- int l = -1, r = n;
- map<pair<int, int>, int> vis;
- pair<int, int> cur = {0, 0};
- vis[cur] = 0;
- for (int i = 0; i < n; ++i) {
- if (s[i] == 'L') --cur.first;
- if (s[i] == 'R') ++cur.first;
- if (s[i] == 'U') ++cur.second;
- if (s[i] == 'D') --cur.second;
- if (vis.count(cur)) {
- if (i - vis[cur] + 1 < r - l + 1) {
- l = vis[cur];
- r = i;
- }
- }
- vis[cur] = i + 1;
- }
- if (l == -1) {
- cout << -1 << endl;
- } else {
- cout << l + 1 << " " << r + 1 << endl;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3408817.html