「BalticOI 2014 Day 1」三个朋友

Link: 「BalticOI 2014 Day 1」三个朋友

Description

给定一个字符串S，先将字符串S复制一次（变成双倍快乐），得到字符串T，然后在T中插入一个字符，得到字符串U。
给出字符串U，重新构造出字符串S。
所有字符串只包含大写英文字母。
输入格式
第一行一个整数N，表示字符串U的长度。()
第二行一个长度为N的字符串，表示字符串U。
输出格式
一行一个字符串，表示字符串S。
特别地：

  • 如果字符串无法按照上述方法构造出来，输出 NOT POSSIBLE；
  • 如果字符串S不唯一，输出 NOT UNIQUE。

样例
样例输入 1
7
ABXCABC
样例输出 1
ABC
样例输入 2
6
ABCDEF
样例输出 2
NOT POSSIBLE
样例输入 3
9
ABABABABA
样例输出 3
NOT UNIQUE

Problem solving

这道题的意思题面已经描述的很清楚了。清楚了题意之后，显然可以用哈希写。因为输入的字符串的长度是S的二倍加一，所以如果长度是偶数，直接输出NOT POSSIBLE即可。而且显然我们可以知道满足题意得S最多就两种。然后我们可以遍历整个字符串，遍历到第i位时便认为这一位即新加的，因为我们要求的字符串的长度是固定的的，所以只要我们确定了最后一步加上的是哪一位，我们求出删去这一位之后字符串的前一半的哈希值和后一半的哈希值作比较就可以得到要求的字符串。
因为可能满足条件的字符串有多个，所以我们需要特殊处理一下。详见代码及注释。
我们刚好有求区间的哈希值以及区间中删去任一位置之后的哈希值的板子，直接套板子即可。
（在网上找到的题解写的代码，我真的是看着头疼，自我感觉写的还是很清楚的

关于用到的板子：https://ac.nowcoder.com/discuss/178326?type=101&order=4&pos=12&page=1

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
typedef unsigned long long ull;
#define base 233
ull h[maxn], p[maxn];
ull get_hash(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
ull get_s(int l, int r, int x)
{
    return get_hash(l, x - 1) * p[r - x] + get_hash(x + 1, r);
}//板子
int main()
{
    int n, mid; string s;

    cin >> n >> s;
    if (!(n & 1)) {
        cout << "NOT POSSIBLE\n"; return 0;
    }
    p[0] = 1;
    for (int i = 1; i <= maxn; i++) p[i] = p[i - 1] * base;
    s = " " + s;//因为我们求get_s的时候会遇到x-1，所以下标如果从0开始会RE，因此我们给s的第一位变成空格
    h[1] = s[1];
    for (int i = 2; i <= n; i++)
        h[i] = h[i - 1] * base + s[i];
    mid = n / 2 + 1;
    ull a, b, ans = 0; b = get_hash(mid + 1, n);
    //这里我是分开处理了，前一半和后一半分开
    //因为如果你假设的是前一半中删去一个，那么后半部分字符串就是我们要求的，它的哈希值是固定的，这样只用算一次
    string Ans, ANS1, ANS2;
    for (int i = mid + 1; i <= n; i++) Ans += s[i];//把字符串后半部分存储起来
    for (int i = 1; i < mid; i++) {
        a = get_s(1, mid, i);
        // cout << i << " " << a << " " << b << endl;
        if (a == b) {
            ans++, ANS1 = Ans; break;//如果哈希值相等，说明Ans是答案之一
        }
    }
    Ans = "";
    for (int i = 1; i <= mid - 1; i++) Ans += s[i];
    b = get_hash(1, mid - 1);
    for (int i = mid; i <= n; i++) {
        a = get_s(mid, n, i);
        // cout << i << " " << a << " " << b << endl;
        if (a == b) {
            ans++, ANS2 = Ans; break;
        }
    }//这一部分是从后一半中删去一个字符，跟上面那种情况同样的做法
    if (ans == 0) cout << "NOT POSSIBLE\n";//如果ans还是0，说明没有出现满足条件的
    else if (ans == 1 || ANS1 == ANS2) cout << (ANS1 == "" ? ANS2 : ANS1) << endl;//如果只有1种情况，输出那一种。但是还有一种情况就是，分开的两种都有结果但是结果相同，所以我们也输出一个。
    else cout << "NOT UNIQUE\n";//否则就是有两个解
}
赏