2021 CCPC 威海赛区D题 Period

2021 CCPC 威海赛区D题 Period

2021 CCPC 威海赛区D题 Period

题意

给定一个只含有小写字母的字符串 s = s 1 s 2 s 3 . . . s n s=s_1s_s_n s=s1​s2​s3​...sn​，并进行 q q q次询问。

每次询问选定一个下标 i i i，将 s i s_i si​变成 # # #，问这个变化后的字符串 s ′ = s 1 s 2 . . s i − 1 # s i + 1 . . . s n s'=s_1s_2..s_{i-1}#s_{i+1}...s_n s′=s1​s2​..si−1​#si+1​...sn​有几个周期。
每次询问独立，即修改操作不会影响原串 s s s。

思路

没学过前缀函数和字符串的周期的可以先看一下oi-wiki中的介绍。/

假设当前修改的位置为 i i i，且存在周期 d d d。
因为 s s s中只含有小写字母，所以修改后的字符 # # #一定不会出现在其他位置，故：

• s ′ s' s′中不会存在两个完整的周期， 2 d > n 2d > n 2d>n。
• # # #字符一定存在于第一个周期， i ≤ d ile d i≤d。
• 第二个周期中不存在 # # #字符， d > n − i + 1 d>n-i+1 d>n−i+1。
• s ′ s' s′的周期一定存在于 s s s的周期。

因为周期的数量等同于字符串的border的数量，且周期为 { d = n − π [ j ] } {d=n-pi[j]} {d=n−π[j]}，所以可以通过预处理将原串 s s s的周期求出，然后对于每次查询，二分出满足条件的周期 d d d（ d d d只需要大于某个值就均满足条件，满足单调性）。

AC的代码

#include <bits/stdc++.h>
using namespace std;// 求前缀函数的模板 
vector<int> prefix_function(string s) {int n = s.size();vector<int> pi(n);for (int i = 1; i < n; i++) {int j = pi[i - 1];while (j > 0 && s[i] != s[j]) j = pi[j - 1];if (s[i] == s[j]) j++;pi[i] = j;}return pi;
}string s;
int n, q; 
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ptions(ios::badbit | ios::failbit);cin >> s;vector<int> pi = prefix_function(s);n = s.size();vector<int> vec;	// 记录所有的borderint tmp = pi[n - 1];while(tmp != 0) {vec.push_back(n - tmp);tmp = pi[tmp - 1];}int k = (n + 1) / 2; // 字符串的中点 cin >> q;while(q--) {int x;cin >> x;if(x <= k) x = n + 1 - x;int t = lower_bound(vec.begin(), d(), x) - vec.begin();if(t == vec.size()) cout << 0 << "n";else cout << vec.size() - t << "n";}return 0;
}