B. Reverse String——论如何优美文雅的暴力（还是自己菜）

现在是原本想着上一波分来，没想到被一个暴力卡死了

这题过的人挺多的，所以就该考虑是不是自己思路偏了，可不可以换个角度考虑问题，还有就是写算法之前尽量证明一下自己的算法是正确的，要不然白白浪费时间，特别是cf这么短时间的比赛。掉分不可怕，可怕的是不知道自己为啥上不去分。

• 题意

就是从某一个位置开始连续向右走 0/x 步，然后反向连续向左走 0/y 步，问你给的 t 串是不是可以通过以上方法在 s 串中构造出来

• 思路

因为串的长度很短，所以肯定要考虑暴力，关键是怎样暴力。赛中以及赛后我一直想的是如何枚举 t 的前缀和 s 中的位置进行相互匹配，但是不仅麻烦，而且要考虑的情况非常多，算法都很假；然后看了 tourist 和一个红名大佬的，发现直接枚举向右的区间，然后反向再走，在这个过程中看是否出现字符串等于 t 串；哎，果然暴力不是真暴力，暴力也是可以又优雅的暴力的，其实还是自己菜！！！当时想的快跳楼了都。。。想着一直上不去分，心情就很难过，可是没办法，菜就菜呗，又不能当饭吃。

• 代码（tourist的）

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    string s, t;
    cin >> s >> t;
    int n = (int) s.size();
    int m = (int) t.size();
    bool found = false;
    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        bool ok = true;
        int ptr = 0;
        for (int k = i; k <= j; k++) {
          if (ptr == m || s[k] != t[ptr]) {
            ok = false;
            break;
          }
          ++ptr;
        }
        for (int k = j - 1; k >= 0; k--) {
          if (ptr == m) {
            break;
          }
          if (s[k] != t[ptr]) {
            ok = false;
            break;
          }
          ++ptr;
        }
        if (ok && ptr == m) {
          found = true;
          break;
        }
      }
      if (found) {
        break;
      }
    }
    cout << (found ? "YES" : "NO") << '\n';
  }
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50