Friends 题解_牛客博客

hash好题！而且nowcoder的数据比bzoj强多了qwq。在字符串中删除一个数的话，假设那个数为x，并且这个字符串的下标起止为 $1$ 到 $n$ ，那么要把 $1$ 到 $x-1$ 这段的hash值乘上 $base^{n-x+1}$ 。于是这题做完了，直接枚举这个删掉的点就好，注意枚举子串hash的方法。尽量函数式编程简化代码。

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define N 2000100
#define ll unsigned long long
#define base 233

ll h[N], p[N], ha;
char s[N], ans[N];
int n;
ll t1 = 0, t2 = 0, t = 0;

ll get_hash(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];}

bool check(int x) {
    if(x > n / 2) t1 = get_hash(1, n / 2), t2 = get_hash(n / 2 + 1, x - 1) * p[n - x] + get_hash(x + 1, n);
    else t1 = get_hash(n / 2 + 2, n), t2 = get_hash(1, x - 1) * p[n / 2 - x + 1] + get_hash(x + 1, n / 2 + 1);
    return t1 == t2;
}

int main() {
    p[0] = 1;
    for(int i = 1; i < 2000000; ++i) p[i] = p[i - 1] * base;
    scanf("%d%s", &n, s + 1);
    if(!(n & 1)) return puts("NOT POSSIBLE"), 0;
    for(int i = 1; i <= n; ++i) {
        h[i] = h[i - 1] * base + (ll)(s[i]);
    }
    int pos = 0;
    for(int i = 1; i <= n; ++i) {
        if(check(i)) {
            if(!t) t = t1;
            else if(t != t1) return puts("NOT UNIQUE"), 0;
            pos = i;
        }
    }
    if(!pos) return puts("NOT POSSIBLE"), 0;
    if(pos <= n / 2) for(int i = n / 2 + 2; i <= n; ++i) putchar(s[i]);
    else for(int i = 1; i <= n / 2; ++i) putchar(s[i]);
}