摆了，但是没有完全摆
CF103495H
H. Reverse the String
给定长1e5的字符串，你可以翻转其中一段连续子段，问能产生的字典序最小的字符串是啥
据说可以用SA写，我是没啥思路，题解是hash，就这样补了
思路
考虑把字符串的字符排序，生成的新字符串必然是字典序最小的构造。
那么我们从原字符串和新字符串第一个不同的点作为翻转的起点即可。
然后枚举右端点，通过二分hash，求lcp来比较字符串大小即可。
hash的话，正反跑一遍拼起来就完了，不过式子有一点折磨捏
CODE
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
#include<unordered_map>
#include <iomanip>
#include<set>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
char s[200000 + 5];
char s2[200000 + 5];
ll seed = 20111203;
ll mod = 1e9 + 7;
ll T;
ll h[200000 + 5];
ll r[200000 + 5];
ll poww[200000 + 5];
ll l;
ll q(ll L, ll R, ll x) {
if (x < L)return h[x];
if (x > R)return ((h[L - 1] * poww[x - L + 1])%mod +(r[L] - r[R+1] * poww[R - L + 1]%mod+mod)%mod * poww[x - R]%mod + (h[x] - (ull)h[R] * poww[x - R]%mod +mod)%mod)%mod;
else return (h[L - 1] * poww[x - L + 1]%mod + (r[R-(x-L)] - r[R+ 1] * poww[(x - L)+1]%mod+mod)%mod)%mod;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
poww[0] = 1;
for (int i = 1; i <= 100000 + 5; i++) {
poww[i] = poww[i - 1] * seed%mod;
}
cin >> T;
while (T--)
{
cin >> s + 1;
l = strlen(s+1);
for (int i = 1, j = l; i <= l && j >= 1; i++,j--) {
h[i] =( h[i - 1] * seed%mod + s[i] - 'a')%mod;
r[j] = (r[j + 1] * seed%mod + s[j] - 'a')%mod;
s2[i] = s[i];
}
sort(s2 + 1, s2 + 1 + l);
ll r1 = 0;
for (int i = 1; i <= l; i++) {
if (s[i] == s2[i])r1 = i;
else break;
}
r1++;
if (r1 > l)cout << s + 1 << '\n';
else {
ll mx = r1;
for (int i = r1; i <= l; i++) {
ll L = 0, R = l;
while (L<R)
{
ll m = L + R >> 1;
if (q(r1, i, m) == q(r1, mx, m))L = m+1;
else R = m;
}
if (L > l)continue;
if (q(r1, i, L) < q(r1, mx, L))mx = i;
}
for (int i = 1; i < r1; i++)cout << s[i];
for (int i = mx; i >= r1; i--)cout << s[i];
for (int i = mx + 1; i <= l; i++)cout << s[i];
cout << '\n';
}
}
}
|
