原题还是没找
串串 49pts
用的 $ manacher $，板子差点没打对，但好歹还是打对了。。。
赛时写的时候没有考虑到不用管偶回文，导致递归的时候有点问题。。。
其实根本用不到递归，将循环顺序改为倒序即可；
有三种情况：
- 回文半径 + 位置能够到达右端点；
显然，这种情况是合法的；
- 既到不了左端点，又到不了右端点；
显然，这种情况是不合法的；
- 能到左端点，到不了右端点；
倒序循环，看看当前的右端点是否合法即可；
其实挺简单，但还是没切，赛时切两道题就这么难吗。。。
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t;
char c[5000005];
char s[5000005];
int n;
int a;
int mid, r;
int p[5000005];
int vis[5000005];
int main() {
cin >> t;
while(t--) {
mid = 0;
r = 0;
scanf("%s", s + 1);
a = strlen(s + 1);
if (a == 1) {
cout << 1 << endl;
continue;
}
n = 1;
c[1] = '~';
for (int i = 1; i <= a; i++) {
c[++n] = s[i];
}
c[++n] = '#';
for (int i = 1; i <= n; i++) {
p[i] = 0;
vis[i] = 0;
}
for (int i = 2; i <= n - 1; i++) {
if (i <= r) p[i] = min(r - i + 1, p[2 * mid - i]);
while(c[i - p[i]] == c[i + p[i]]) p[i]++;
if (i + p[i] - 1 >= r) {
r = i + p[i] - 1;
mid = i;
}
if (i + p[i] - 1 >= n - 1) vis[i] = true;
}
for (int i = n - 1; i >= 2; i--) {
if (vis[i]) continue;
if (i - p[i] + 1 > 2) continue;
if (vis[i + p[i] - 1]) vis[i] = true;
}
for (int i = 2; i <= n - 1; i++) {
if (vis[i]) {
cout << i - 1 << ' ';
}
}
cout << endl;
}
return 0;
}
排排 100pts
结论题，所以没给大样例。。。
-
给出的就是顺序，需要0次操作；
-
1或n在自己的位置上，1次；
-
有在自己位置上的，且左边没有比它大的，右边没有比它小的，1次；
-
1在n上，n在1上，3次；
-
剩下情况2次；
对于3，我用了线段树维护，当然也可以用ST表等等；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int t;
int n;
int a[500005];
int num[500005];
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
struct sss{
int l, r, ma, mi;
}tr[3000005];
inline void push_up(int id) {
tr[id].ma = max(tr[ls(id)].ma, tr[rs(id)].ma);
tr[id].mi = min(tr[ls(id)].mi, tr[rs(id)].mi);
}
void bt(int id, int l, int r) {
tr[id].l = l;
tr[id].r = r;
if (l == r) {
tr[id].ma = a[l];
tr[id].mi = a[l];
return;
}
int mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
push_up(id);
}
int ask_ma(int id, int l, int r) {
if (tr[id].l >= l && tr[id].r <= r) {
return tr[id].ma;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (r <= mid) return ask_ma(ls(id), l, r);
else if (l > mid) return ask_ma(rs(id), l, r);
else return max(ask_ma(ls(id), l, mid), ask_ma(rs(id), mid + 1, r));
}
int ask_mi(int id, int l, int r) {
if (tr[id].l >= l && tr[id].r <= r) {
return tr[id].mi;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (r <= mid) return ask_mi(ls(id), l, r);
else if (l > mid) return ask_mi(rs(id), l, r);
else return min(ask_mi(ls(id), l, mid), ask_mi(rs(id), mid + 1, r));
}
int main() {
cin >> t;
while(t--) {
cin >> n;
num[0] = 0;
bool vis = true;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] != i) vis = false;
}
bt(1, 1, n);
if (vis) {
cout << 0 << endl;
continue;
}
if (a[1] == 1 || a[n] == n) {
cout << 1 << endl;
continue;
}
for (int i = 1; i <= n; i++) {
if (a[i] == i) num[++num[0]] = i;
}
bool vi = false;
for (int i = 1; i <= num[0]; i++) {
if (a[num[i]] > ask_ma(1, 1, num[i] - 1) && a[num[i]] < ask_mi(1, num[i] + 1, n)) {
cout << 1 << endl;
vi = true;
break;
}
}
if (!vi) {
if (a[1] == n && a[n] == 1) {
cout << 3 << endl;
} else {
cout << 2 << endl;
}
}
}
return 0;
}