题解 P6739 【[BalticOI 2014 Day1] Three Friends】

· · 题解

这一题用哈希就可以水掉了。需掌握求一个字符串区间哈希值的做法。

题目大意

尊重原题：有 3 个好朋友喜欢一起玩游戏，A 君写下了一个字符串 S，B 君将其复制一遍得到 T，C 君在其任意位置（包括首尾）插入一个字符得到一个字符串 U。现在你得到了 U，请找出 S。

简化版：有一个字符串 S，对其进行操作：

现在给定 U，求 S。

大体思路

前置芝士：字符串哈希

如果对字符串哈希不甚了解，请自行参考 这题。

此处介绍的，即是最常见的一种哈希：进制哈希。进制哈希的核心便是给出一个固定进制 base，将一个串的每一个元素看做一个进制位上的数字，所以这个串就可以看做一个 base 进制的数，那么这个数就是这个串的哈希值；则我们通过比对每个串的的哈希值，即可判断两个串是否相同。

首先选择两个质数。我选择 22783 作为底数（这是我们班一个人的学号），并用 unsigned long long 自然溢出的特性作为模数。下方所有变量未经特殊说明均为无符号长整形。（详见代码）

接下来进行预处理：用一个数组 pre_k 表示 base^k，并滚动处理字符串哈希值 H_i=H_{i-1}\times base + S_i，其中 H_i 表示哈希值，S_i 为字符串中的元素。

    pre[0]=1;//边界条件：base 的 0 次方等于一。
    for(int i= 1;i<=n;i++) {
        pre[i]=pre[i-1]*22783;//记录 pre 数组
        h[i]=h[i-1]*22783+(s[i]-'A'+1);//滚动处理哈希值
    }

在得到字符串哈希值后，如何求区间的哈希值呢？其实类似前缀和的思想，hash[l,\ r]=H_r-H_{l-1}\times pre_{r-l+1}。显然单纯的相减是不可取的，因此需要将区间前一项乘以底数的区间长度次幂，以求得字符串的区间哈希值。

而题目是插入了一个字符，因此我们逆向处理时需枚举删去一个字符的哈希值。类似上方，删去第 x 个字符后的哈希值为 hash[1,x-1]\times pre_{r-x} + hash[x+1,r]。对于整个字符串而言，l=1,r=n。

inline unsigned long long check(int l, int r) { 
    return h[r] - h[l - 1] * pre[r - l + 1]; 
}//区间哈希值
inline unsigned long long sum(int l, int r, int k) { 
    return check(l, k - 1) * pre[r - k] + check(k + 1, r); 
}//删去第 k 个字符

本题详解

首先一个很显然的结论：由于 U 串是 S 串复制两次后插入一个字符所得，因此长度必然为奇数。所以特判：若 n 为偶数则直接输出 NOT POSSIBLE。

接下来，将得到的字符串分成两部分 1\sim mid,\ mid+1\sim n，并分别记录这两段的哈希值。然后对于 mid+1\sim n，枚举删去 1\sim mid 中的字符，若所得字符串与后半段相等则答案数 ans+1 并跳出循环。反之亦然。

然后进行判断：

完整代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 2000002
string a, b, c, d;
int n, mid, l1, l2, h[maxn], pre[maxn], ans;
char s[maxn];
inline unsigned long long check(int l, int r) { 
    return h[r] - h[l - 1] * pre[r - l + 1]; 
}//区间哈希值
inline unsigned long long sum(int l, int r, int k) { 
    return check(l, k - 1) * pre[r - k] + check(k + 1, r); 
}//删去字符
int main() {
    scanf("%d%s",&n,s+1);
    mid=(n+1)>>1;
    if (!(n&1)){
        printf("NOT POSSIBLE");
        return  0;
    }//特判
    pre[0]=1;
    for(int i= 1;i<=n;i++) {
        pre[i]=pre[i-1]*22783;
        h[i]=h[i-1]*22783+(s[i]-'A'+1);
    }//预处理
    l1=check(mid+1,n);
    for(int i=mid+1;i<=n;i++) a.push_back(s[i]);
    for(int i=1;i<=mid;i++) {
        l2=sum(1,mid,i);
        if (l1==l2){
            ans++;
            c=a;
            break;
        }
    }
    l2=check(1,mid-1);
    for(int i=1;i<mid;i++) b.push_back(s[i]);
    for(int i=mid;i<=n;i++) {
        l1=sum(mid,n,i);
        if(l1==l2) {
            ans++;
            d=b;
            break;
        }
    }//枚举
    if (!ans)
        printf("NOT POSSIBLE");
    else if (ans == 1 || c == d)
        cout << (c.size() ? c : d);
    else printf("NOT UNIQUE");//判断输出
    return 0;
}

后记

今天 CSP2020 出成绩，普及组正常 1=，提高组因为 T3 加了 ios::sync_with_stdio(0); 语句而抱灵，导致 1= 没了，悲痛。

希望 NOIp rp++！