题解 P6739 【[BalticOI 2014 Day1] Three Friends】
Mars_Dingdang
2020-12-01 17:45:14
这一题用哈希就可以水掉了。需掌握求一个字符串区间哈希值的做法。
## 题目大意
**尊重原题**:有 $3$ 个好朋友喜欢一起玩游戏,$A$ 君写下了一个字符串 $S$,$B$ 君将其复制一遍得到 $T$,$C$ 君在其任意位置(**包括首尾**)插入一个字符得到一个字符串 $U$。现在你得到了 $U$,请找出 $S$。
**简化版**:有一个字符串 $S$,对其进行操作:
- 将 $S$ 复制为两份,存在字符串 $T$ 中;
- 在 $T$ 的某一位置上插入一个字符,得到字符串 $U$。
现在给定 $U$,求 $S$。
## 大体思路
#### 前置芝士:字符串哈希
如果对字符串哈希不甚了解,请自行参考 [这题](https://www.luogu.com.cn/problem/P3370)。
此处介绍的,即是最常见的一种哈希:进制哈希。进制哈希的核心便是给出一个固定进制 $base$,将一个串的每一个元素看做一个进制位上的数字,所以这个串就可以看做一个 $base$ 进制的数,那么这个数就是这个串的哈希值;则我们通过比对每个串的的哈希值,即可判断两个串是否相同。
首先选择两个质数。我选择 $22783$ 作为底数(这是我们班一个人的学号),并用 `unsigned long long` 自然溢出的特性作为模数。下方所有变量未经特殊说明均为无符号长整形。(详见代码)
接下来进行预处理:用一个数组 $pre_k$ 表示 $base^k$,并滚动处理字符串哈希值 $H_i=H_{i-1}\times base + S_i$,其中 $H_i$ 表示哈希值,$S_i$ 为字符串中的元素。
```cpp
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$。
```cpp
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$ 并跳出循环。反之亦然。
然后进行判断:
- 若答案数为零,则无解,输出 `NOT POSSIBLE`。
- 若答案数为一,或删去字符后的两串相等,则输出删去后不为空的字符串(即所求的 $S$)。
- 否则说明答案不唯一,输出 `NOT UNIQUE`。
## 完整代码
```cpp
#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++!