1 条题解

  • 0
    @ 2025-3-24 16:58:57
    #include <bits/stdc++.h>
    using namespace std;
    
    typedef unsigned long long ull; // 定义新的无符号长整型
    
    #define rep(i, l, r) for(int i = l; i <= r; ++i)
    #define per(i, r, l) for(int i = r; i >= l; --i)
    const int N = 2e6 + 10;
    int n, mid, ans_id, tot;
    string s;
    const int base = 133331, p = 1e9 + 7;
    ull G[N], f[N];
    unordered_map<ull, bool> vis;
    
    void init() {
        G[0] = 1;
        rep(i, 1, n) {
            G[i] = G[i - 1] * base;
            f[i] = f[i - 1] * base + s[i];
        }
    }
    
    ull calc(int l, int r) {
        return f[r] - f[l - 1] * G[r - l + 1];
    }
    
    ull del_calc(int l, int x, int r) {
        return calc(l, x - 1) * G[r - x] + calc(x + 1, r);
    }
    
    bool check(int x) {
        ull l = 0, r = 0;
    
        if (x == mid) {
            l = calc(1, x - 1);
            r = calc(x + 1, n);
        }
    
        if (x < mid) {
            l = del_calc(1, x, mid);
            r = calc(mid + 1, n);
        }
    
        if (x > mid) {
            l = calc(1, mid - 1);
            r = del_calc(mid, x, n);
        }
    
        if (l == r && !vis[l]) {
            vis[l] = true;
            return true;
        }
    
        return false;
    }
    
    int main() {
        cin >> n >> s;
        s = "0" + s;
    
        if (!(n & 1)) {
            puts("NOT POSSIBLE");
            exit(0);
        }
    
        mid = (n + 1) >> 1;
        init();
        rep(i, 1, n) {
            if (check(i)) {
                ans_id = i;
                tot++;
            }
        }
    
        if (tot > 1) {
            puts("NOT UNIQUE");
            exit(0);
        }
    
        if (!tot) {
            puts("NOT POSSIBLE");
            exit(0);
        }
    
        if (ans_id == mid)
            rep(i, 1, mid - 1) cout << s[i];
        else if (ans_id < mid)
            rep(i, mid + 1, n) cout << s[i];
        else
            rep(i, 1, mid - 1) cout << s[i];
    
        return 0;
    }
    
    
    • 1

    信息

    ID
    915
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者