专栏文章

题解：AT_nikkei2019_2_final_h 逆にする関数

BBPG_ning
AT_nikkei2019_2_final_h题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minj8qoi
此快照首次捕获于
2025/12/02 03:18
3 个月前
此快照最后确认于
2025/12/02 03:18
3 个月前
查看原文
先讲讲 Manacher 怎么做。
钦定以下指的回文串是长度为奇数的 广义的回文串 ，我们将原字符串中每两个字符之间插入一个字符，求回文串就是 广义的回文串。
定义广义的回文串为翻转之后与原串相等的字符串。
考虑对于每个中心 ii 求出 fif_i，表示 [i−j,i+j][i-j,i+j] 是回文串当且仅当 j<fij<f_{i}。
一个很暴力的想法就是枚举 fif_{i} 暴力匹配 si−fis_{i-f_{i}} 和 si+fis_{i+f_{i}}。
考虑优化。从小到大枚举 ii，求 fif_{i}。维护 max⁡j=1i−1j+fj\max_{j=1}^{i-1} j+f_{j}，也就是他前面右端点最靠右的区间（若 右端点一样 选 jj 最大的）。
若 i≥j+fji\geq j+f_{j}，进行上述暴力。
若 i<j+fji<j+f_{j}，考虑让 ii 继承 f2j−if_{2j-i} 的信息，也就是在这个回文串里 ii 对应的位置的信息。
若 i+f2j−i>j+fji+f_{2j-i}>j+f_{j}，意味着超出了这个回文区间信息不能保真，所以我们取到最大 fi=j+fj−f2j−if_{i}=j+f_{j}-f_{2j-i}，然后再暴力。
复杂度证明：
设 r=j+fjr=j+f_{j}，每次执行一次上述“暴力”，r←r+1r\gets r+1，所以时间复杂度 O(n)O(n)。
代码：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=1.1e7+10;
int n,f[N*2];
string s="##";
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    // freopen("gsw.in","r",stdin);
    // freopen("gsw.out","w",stdout);
    char c;
    while(cin>>c) s+=c,s+='#';
    int r=0,j=0; s='!'+s+'?';
    n=s.size();
    for(int i=1;i<=n;i++){
        f[i]=(r>i?min(f[j*2-i],r-i):1);
        while(s[i-f[i]]==s[i+f[i]]) f[i]++;
        if(i+f[i]>r) r=i+f[i],j=i;
    }
    int Max=0;
    for(int i=1;i<=n;i++) Max=max(Max,f[i]-1);
    cout<<Max<<'\n';
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}
然后就是这道题，发现与回文串形式很类似，区间 [l,r][l,r] 贡献 ≠0\ne 0 当且仅当反转之后与原串构成双射，称之为 好串。一个 好串 的贡献为 mm−颜色数量m^{m-颜色数量}。
考虑用类似 Manacher 思想去做，求出 fif_{i}，表示 [i−j,i+j][i-j,i+j] 是 好串 当且仅当 j<fij<f_{i}，可以顺便维护 [i−fi+1,i+fi−1][i-f_{i}+1,i+f_{i}-1] 的颜色数量和 ∑mm−颜色数量\sum m^{m-颜色数量}。
与上面类似，维护右端点最靠右的 好串。
若 i≥j+fji\geq j+f_{j}，进行暴力。
若 i<j+fji<j+f_{j}，考虑继承信息。
若 i+f2j−i>j+fji+f_{2j-i}>j+f_{j}，考虑暴力回退 f2j−if_{2j-i} 使得没有超出。
复杂度证明：
对于一次回退的时间复杂度是 O(i+f2j−i−j−fj)O(i+f_{2j-i}-j-f_{j})。
根据定义有 2j−i+f2j−i≤j+fj2j-i+f_{2j-i}\leq j+f_{j}。
移项有 i+f2j−i−j−fj≤2i−2ji+f_{2j-i}-j-f_{j}\leq 2i-2j。
设 k=i−jk=i-j，做完这次操作之后会将 k←0k\gets 0，意味着我们已 O(k)O(k) 的时间复杂度将 k←0k\gets 0，然而 kk 的总增加量为 O(n)O(n)，所以总时间复杂度 O(n)O(n)。
讲的更好

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...