一道想了很久也毫无思路的题目,然后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!
*/