link

一道想了很久也毫无思路的题目，然后Google搜到要用最小表示法，大多数都说的很含糊，最后在这篇博客 里面找到了答案。

原来无法理解的地方就是为什么当$s[i] > s[j]$的时候，直接跳到$i+k+1$。

吃完饭来写。

/*
ID: mwx36mw2
TASK: hidden
LANG: C++11
*/
// Author: Wenxing Mei
//   Date: 2018-12-01 09:59
#include <bits/stdc++.h>
#ifdef LOCAL
#include <unistd.h>
#endif
using namespace std;
#define rep(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define per(i, b, a) for (int i = (int)b - 1; i >= (int)a; --i)
#define repv(ele, cont) for (auto &ele : cont)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
// END OF TEMPLATE

int n;
char s[100010], c;

int main() {
#ifndef LOCAL
  freopen("hidden.in", "r", stdin);
  freopen("hidden.out", "w", stdout);
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
  cin >> n;
  rep(i, 0, n) {
    scanf("%c", &c);
    if (c < 'a' || c > 'z')
      --i;
    else
      s[i] = c;
  }

  int i = 0, j = 1;
  while (i < n && j < n) {
    int k = 0;
    for (; k < n; ++k) {
      if (s[(i + k) % n] != s[(j + k) % n]) { break; }
    }

    if (k == n) { break; }

    if (s[(i + k) % n] < s[(j + k) % n]) {
      if (j + k + 1 > i)
        j += k + 1;
      else
        j = i + 1;
    } else {
      if (i + k + 1 > j)
        i += k + 1;
      else
        i = j + 1;
    }
  }

  cout << min(i, j) << endl;

  return 0;
}

/*
USER: wenxing mei [mwx36mw2]
TASK: hidden
LANG: C++11

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.004 secs, 1340 KB]
   Test 2: TEST OK [0.004 secs, 1268 KB]
   Test 3: TEST OK [0.004 secs, 1276 KB]
   Test 4: TEST OK [0.004 secs, 1296 KB]
   Test 5: TEST OK [0.000 secs, 1300 KB]
   Test 6: TEST OK [0.004 secs, 1312 KB]
   Test 7: TEST OK [0.004 secs, 1404 KB]
   Test 8: TEST OK [0.014 secs, 1280 KB]
   Test 9: TEST OK [0.014 secs, 1296 KB]
   Test 10: TEST OK [0.014 secs, 1296 KB]
   Test 11: TEST OK [0.014 secs, 1292 KB]
   Test 12: TEST OK [0.004 secs, 1268 KB]
   Test 13: TEST OK [0.004 secs, 1280 KB]
   Test 14: TEST OK [0.011 secs, 1292 KB]

All tests OK.
Your program ('hidden') produced all correct answers!  This is your
submission #16 for this problem.  Congratulations!
*/