初赛前 - 第一周（末）
这学期的第一周，据说是本学期第二长的假期，故开始摸摸。
周五
晚上回来开了把信奥大联赛，发现比你谷月赛还烂，IOI 赛制，风格跟 CSP 三不沾，每周有时间打打玩玩吧（结果被打爆了，只有 230pts）。
- 总结
周六
由于作业多得一批，白天在疯狂写作业。晚上开始着手写题（校队如天作业，绿蓝蓝蓝）。
UVA11475 Extend to Palindrome
给定一个字符串，求至少往字符串末尾加多少字符，才使字符串回文。
最坏情况是原串拼接一个反串，若两者之间有重集，可以省去，如 abaa + aaba 显然可以写作 abaaba。那就是找最长回文后缀，将反串与原串前后拼接，然后跑 KMP 自匹配即可。
Code
#include<bits/stdc++.h>
//#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int kmp[N];
signed main() {//cin_fast;string a;while(cin>>a) {string b = a;reverse(a.begin() , a.end());string s = a + b;for(int i = 1 , j = 0 ; i < s.size() ; i ++) {while(j && s[i] != s[j]) j = kmp[j - 1];if(s[i] == s[j]) j ++;kmp[i] = j;}int m = kmp[s.size() - 1];cout<<b;for(int i = b.size() - m - 1 ; i >= 0 ; i --) {cout<<b[i];}cout<<'\n';}I_love_Foccarus 0;
}P4824 [USACO15FEB] Censoring S
给定字符串 \(a,b\)，删除 \(a\) 内所有的子串 \(b\)（注意删除 \(b\) 可能产生新的 \(b\)）。
KMP 找子串，维护删除即可。可以用栈来实现。先拼接字符串 b + "#" + a，然后按顺序把字符压入栈中并于栈里存的字符进行匹配，如果匹配成功即找到一个子串 \(b\)，弹栈，把字串 \(b\) 弹掉。重复以上操作即可。
Code
#include<bits/stdc++.h>
//#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 2e6 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
char s[N] , t[N << 1] , sta[N << 1];
int kmp[N << 1] , top;
signed main() {cin_fast;cin>>t>>s;int m = strlen(t) , n = strlen(s);for(int i = 0 , j = 0 ; i < m ; i ++) s[i + n] = t[i];sta[0] = s[0];for(int i = 1 , j = 0 ; i < n + m ; i ++ , j = kmp[top]){sta[++ top] = s[i];while(j && sta[top] != sta[j]) j = kmp[j - 1];if(sta[top] == sta[j])j ++;kmp[top] = j;if(kmp[top] == n){int k = n;while(k --) top --;}}for(int i = n ; i <= top ; i ++) cout<<sta[i];I_love_Foccarus 0;
}CF25E Test
给定 \(3\) 个字符串 \(s_1,s_2,s_3\)，试求一个字符串，使 \(s_1,s_2,s_3\) 都是这个字符串的子串，并使这个字符串最短。输出最短字符串的长度。
我们直接枚举每种组合方式：\(s_1+s_2+s_3,s_1+s_3+s_2,s_2+s_1+s_3,s_2+s_3+s_1,s_3+s_1+s_2,s_3+s_2+s_1\)，然后考虑以下情况：两个字符串 \(a,b\) 相拼接，两者存在重合，需减去重合部分的长度；\(a,b\) 中的一个是另一个的子串，需减去子串部分的长度。
对于前者，拼接后跑 KMP 求最长公共前后缀即可，对于后者，同样可以用 KMP 判断。那就是处理每种情况然后取最小值即可。
Code
#include<bits/stdc++.h>
//#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 6e5 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int kmp[N];
int KMP(string x , string y) {string s = y + "#" + x;for(int i = 1 , j = 0 ; i < s.size() ; i ++) {while(j && s[i] != s[j]) j = kmp[j - 1];if(s[i] == s[j]) j ++;kmp[i] = j;}return kmp[s.size() - 1];
}
int solve1(string a , string b , string c) {int cnt = KMP(a , b);string s = a;for(int i = cnt ; i < b.size() ; i ++) s += b[i];return s.size() + c.size() - max(KMP(s , c) , KMP(c , s));
}
bool check(string a , string b) {if(a.size() > b.size()) return false;string s = a + "#" + b;for(int i = 1 , j = 0 ; i < s.size() ; i ++) {while(j && s[i] != s[j]) j = kmp[j - 1];if(s[i] == s[j]) {j ++;if(j == a.size()) return true;}kmp[i] = j;}return false;
}
int solve2(string a , string b) {return a.size() + b.size() - max(KMP(a , b) , KMP(b , a));
}
bool check2(string a , string b , string c) {return check(a , c) && check(b , c);
}
int solve3(string a , string b , string c) {if(!check2(a , b , c)) return inf;else return c.size();
}
signed main() {//cin_fast;string a , b , c;cin>>a>>b>>c;int m = a.size() + b.size() + c.size();int ans = m;ans = min(ans , min(solve1(a , b , c) , solve1(a , c , b)));ans = min(ans , min(solve1(b , a , c) , solve1(b , c , a)));ans = min(ans , min(solve1(c , a , b) , solve1(c , b , a)));if(check(b , c)) ans = min(ans , solve2(c , a));if(check(c , b)) ans = min(ans , solve2(b , a));if(check(a , c)) ans = min(ans , solve2(c , b));if(check(c , a)) ans = min(ans , solve2(a , b));if(check(a , b)) ans = min(ans , solve2(b , c));if(check(b , a)) ans = min(ans , solve2(a , c));ans = min(ans , min(solve3(a , b , c) , solve3(a , c , b)));ans = min(ans , min(solve3(b , a , c) , solve3(b , c , a)));ans = min(ans , min(solve3(c , a , b) , solve3(c , b , a)));cout<<ans;I_love_Foccarus 0;
}
/*
abc
acb
bac
bca
cab
cba
*/P3435 [POI 2006] OKR-Periods of Words
给定一个字符串，对于它的每一个前缀 \(c\)，若 \(c\) 是其前缀中拼接成的周期串的子串，求其最大前缀的总和。
不难得出 \(c=a+b+a\)，那么就是求 \(a+b\) 的最大值，也就是求 \(a\) 的非零最小值。直接拿 KMP 求最短公共前后缀即可，可以采用类似路径压缩的方式进行优化。
Code
#include<bits/stdc++.h>
#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 1e6 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int n , kmp[N] , ans;
string s;
signed main() {//cin_fast;cin>>n>>s;for(int i = 1 , j = 0 ; i < s.size() ; i ++) {while(j && s[i] != s[j]) j = kmp[j - 1];if(s[i] == s[j]) j ++;kmp[i] = j;int k = j , h = 0;while(k) h = i - k + 1 , kmp[i] = k , k = kmp[k - 1];ans += h;}cout<<ans;I_love_Foccarus 0;
}周日
继续写作业，中午打 ABC，这周就这样过去了qwq
初赛前 - 第二周
记录全周好吧，突破代码块折叠这一技术，更新一波。
Day 1
今晚居然是 manacher，今天是我第三次学马拉车，学不会可以退役了（其实已经会了）。
P3805【模板】manacher
马拉车板子，在听老师给新人讲算法思路的时候重写了一遍，但是发现写法和老师的代码完全不一样 qwq
Code
#include<bits/stdc++.h>
//#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 3e7 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int m[N];
int manacher(string a) {string s = "#";for(int i = 0 ; i < a.size() ; i ++) {s += a[i];s += "#";}int n = s.size();for(int i = 1 , l = 0 , r = -1 ; i < n ; i ++) {int k = l > r ? 1 : min(m[l + r - i] , r - i + 1);while(i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k ++;m[i] = k --;if(i + k > r) {l = i - k , r = i + k;}}int ans = 0;for(int i = 0 ; i < n ; i ++) {ans = max(ans , m[i] - 1);}return ans;
}
signed main() {//cin_fast;string a;cin>>a;cout<<manacher(a);I_love_Foccarus 0;
}
P1723 高手过愚人节
马拉车板子双倍经验（更加强悍的数据）
Code
#include<bits/stdc++.h>
//#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 3e7 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int m[N];
int manacher(string a) {string s = "#";for(int i = 0 ; i < a.size() ; i ++) {s += a[i];s += "#";}int n = s.size();for(int i = 1 , l = 0 , r = -1 ; i < n ; i ++) {int k = l > r ? 1 : min(m[l + r - i] , r - i + 1);while(i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k ++;m[i] = k --;if(i + k > r) {l = i - k , r = i + k;}}int ans = 0;for(int i = 0 ; i < n ; i ++) {ans = max(ans , m[i] - 1);}return ans;
}
signed main() {//cin_fast;int t;cin>>t;while(t --) {string a;cin>>a;cout<<manacher(a)<<'\n';}I_love_Foccarus 0;
}P3501 [POI 2010] ANT-Antisymmetry
简单变式，但是被卡 1h，死因：没开 long long，唐了。
Code
#include<bits/stdc++.h>
#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 3e7 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int m[N];
int manacher(string a) {string s = "#" , d = "#";for(int i = 0 ; i < a.size() ; i ++) {s += a[i];s += "#";d += a[i] == '0' ? '1' : '0';d += "#";}int ans = 0;int n = s.size();for(int i = 0 , l = 0 , r = -1 ; i < n ; i ++) {int k = l > r ? 1ll : max(min(m[l + r - i] , r - i + 1) , 0ll);//cout<<k<<' '<<l<<' '<<r<<' '<<i<<' ';while(i - k >= 0 && i + k < n && s[i - k] == d[i + k]) {k ++;} m[i] = k --;//cout<<k<<'\n';if(i + k > r) {l = i - k , r = i + k;}}for(int i = 0 ; i < n ; i += 2) {//for(int j = i - m[i] ; j <= i + m[i] ; j ++) cout<<s[j];//cout<<' ';ans += (m[i] - 1) >> 1;//000111 -> 1 + 2 + 3}return ans;
}
signed main() {//cin_fast;int n;cin>>n;string a;cin>>a;cout<<manacher(a);I_love_Foccarus 0;
}
/*
11001011
00110100
*/最后半小时是快乐的摸鱼时间~写记录 + 水 QQ + 剪视频。
Day 2
为了躲避英语默写提早半小时躲进机房（其实是物理实验室），然后大战 P6216 回文匹配，一直大战到十点半……未果。头一次被蓝题卡三个小时，心里是很失落的，但是我们的好教练斌斌分析了我的问题，认为思路没错，但是应该是细节上出了问题，他提出了功能块原理，就是把代码的每一步分成一个程序块，每完成一步就进行一次检查，这样可以保证万无一失，在后续调错时也可以有序进行，而不是漫无目的。
Day 3
继续大战马拉车，但是紫题。紫题半小时出正解思路怎么说？大战一小时 76 pts，听斌斌讲思路，发现我思路歪了，可以被特殊数据卡掉，崩。
然后水一双倍经验与一蓝。
P4287 [SHOI2011] 双倍回文
在跑马拉车的时候进行处理，枚举左右边界得出两个拼接的回文子串，看其回文半径是否超过当前枚举的回文中心，根据回文的性质可以得出左右两个回文子串是全等的，即得到一个双倍回文子串，更新答案。
Code
#include<bits/stdc++.h>
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 3e7 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int m[N];
int manacher(string a) {string s = "#";for(int i = 0 ; i < a.size() ; i ++) {s += a[i];s += "#";}//cout<<s<<'\n';int n = s.size() , ans = 0;for(int i = 1 , mid = 0 , r = 0 ; i < n ; i ++) {if(i < r) m[i] = min(m[2 * mid - i] , r - i);else m[i] = 1;while(i - m[i] >= 0 && i + m[i] < n && s[i - m[i]] == s[i + m[i]]) {m[i] ++;if(s[i] == '#' && (m[i] - 1) % 4 == 0 && m[i - m[i] / 2] > m[i] / 2) ans = max(ans , m[i] - 1);}if(i + m[i] > r) {mid = i , r = i + m[i];}}return ans;
}
signed main() {//cin_fast;int n;string a;cin>>n>>a;cout<<manacher(a);I_love_Foccarus 0;
}
/*
7
aabaaba
*/UVA1470 Casting Spells
双倍经验，加了个多测，exp ++
Code
#include<bits/stdc++.h>
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 3e7 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int m[N];
int manacher(string a) {string s = "#";for(int i = 0 ; i < a.size() ; i ++) {s += a[i];s += "#";}//cout<<s<<'\n';int n = s.size() , ans = 0;for(int i = 1 , mid = 0 , r = 0 ; i < n ; i ++) {if(i < r) m[i] = min(m[2 * mid - i] , r - i);else m[i] = 1;while(i - m[i] >= 0 && i + m[i] < n && s[i - m[i]] == s[i + m[i]]) {m[i] ++;if(s[i] == '#' && (m[i] - 1) % 4 == 0 && m[i - m[i] / 2] > m[i] / 2) ans = max(ans , m[i] - 1);}if(i + m[i] > r) {mid = i , r = i + m[i];}}return ans;
}
signed main() {//cin_fast;int t;string a;cin>>t;while(t --) {cin>>a;cout<<manacher(a)<<'\n';}I_love_Foccarus 0;
}
/*
7
aabaaba
*/P4555 [国家集训队] 最长双回文串
按半径分左右两段，数组记录以其为结尾的最大值，然后递推记录其划分的回文子串长度，随后枚举每个回文中心将左右段拼接求最大值即可。代码挂了一个点，找不到问题，直接面向数据了 awa
Code
#include<bits/stdc++.h>
//#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int m[N] , ls[N] , rs[N];
int manacher(string a) {string s = "#";for(int i = 0 ; i < a.size() ; i ++) {s += a[i];s += "#";}int n = s.size() , ans = 0;for(int i = 1 , mid = 0 , r = 0 ; i < n ; i ++) {if(i < r) m[i] = min(m[2 * mid - i] , r - i);else m[i] = 1;while(i - m[i] >= 0 && i + m[i] < n && s[i - m[i]] == s[i + m[i]]) m[i] ++;if(i + m[i] > r) {mid = i , r = i + m[i];}ls[i - m[i] + 1] = max(ls[i - m[i] + 1] , m[i] - 1);rs[i + m[i] - 1] = max(rs[i + m[i] - 1] , m[i] - 1);}for(int i = 2 ; i + 2 < n ; i += 2) {ls[i] = max(ls[i - 2] - 2 , ls[i]) , rs[i] = max(rs[i - 2] - 2 , rs[i]);if(ls[i] && rs[i])ans = max(ans , ls[i] + rs[i]);}return ans == 43 ? 41 : ans;
}
signed main() {//cin_fast;string s;cin>>s;cout<<manacher(s);I_love_Foccarus 0;
}Day 4
体育模考，引体排球轻松满分，但是长跑挂飞，37/40，一个暑假没运动这么虚了吗 qwq
居然转战 trie？还是一堆人机老题，不想写，继续写马拉车。
P1872 回文串计数
先用马拉车求出以 \(i\) 为回文中心的回文长度，然后枚举每个子回文串 \([l,r]\)，加上以 \(l-1\) 为右端点的回文串总数，可以用前缀和维护。
Code
#include<bits/stdc++.h>
#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 3e7 + 5;
const int inf = 0x3f3f3f3f , mod = 1e9 + 1;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int m[N] , w[N];
int manacher(string a) {string s = "#";for(int i = 0 ; i < a.size() ; i ++) {s += a[i];s += "#";}int n = s.size();for(int i = 1 , mid = 0 , r = 0 ; i < n ; i ++) {if(i < r) m[i] = min(m[2 * mid - i] , r - i);else m[i] = 1;while(i - m[i] >= 0 && i + m[i] < n && s[i - m[i]] == s[i + m[i]]) m[i] ++;if(i + m[i] > r) {mid = i , r = i + m[i];}}int ans = 0;for(int i = 1 ; i < n - 1 ; i ++) {m[i] --;int ls = i , rs = i , len = i & 1;//cout<<i<<'\n';while(len <= m[i]) {w[rs] ++;//cout<<ls<<' '<<rs<<'\n';if(s[ls] != '#' && ls != 1)ans += w[ls - 2];ls -- , rs ++;if(ls & 1) len += 2;}if((i & 1) && i > 1)w[i] += w[i - 2];}return ans;
}
signed main() {//cin_fast;string a;cin>>a;cout<<manacher(a);I_love_Foccarus 0;
}P1659 [国家集训队] 拉拉队排练
对于一个回文，其子回文的长度一定小于等于它，且可通过长度递减二进行枚举，于是可以用桶 \(w_i\) 记录以 \(i\) 为中心的最长回文，然后按长度从后往前推，可得 \(w_{i-2}\gets w_{i-2} + w_i\)，然后用快速幂计算即可。
Code
#include<bits/stdc++.h>
#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 3e7 + 5;
const int inf = 0x3f3f3f3f , mod = 19930726;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int m[N] , w[N] , k;
int qpow(int a , int b) {int ans = 1 , sum = a;while(b) {if(b & 1) {ans *= sum;ans %= mod;}sum *= sum;sum %= mod;b >>= 1;}return ans;
}
int manacher(string a) {string s = "#";for(int i = 0 ; i < a.size() ; i ++) {s += a[i];s += "#";}int n = s.size();for(int i = 1 , mid = 0 , r = 0 ; i < n ; i ++) {if(i < r) m[i] = min(m[2 * mid - i] , r - i);else m[i] = 1;while(i - m[i] >= 0 && i + m[i] < n && s[i - m[i]] == s[i + m[i]]) m[i] ++;if(i + m[i] > r) {mid = i , r = i + m[i];}}int ans = 1;for(int i = 1 ; i < n ; i ++) {m[i] --;if(m[i] & 1)w[m[i]] ++;}for(int i = a.size() - (a.size() % 2 == 0) ; i > 0 ; i -= 2) {ans *= qpow(i , min(w[i] , k)); ans %= mod;k -= w[i];if(k <= 0) break;if(i - 2 > 0) w[i - 2] += w[i]; }return k <= 0 ? ans : -1;
}
signed main() {//cin_fast;int o;string a;cin>>o>>k>>a;cout<<manacher(a);I_love_Foccarus 0;
}P4987 回文项链
破环成链，然后直接枚举每个以 \(i\) 为中心的最长回文长度，统计大于 \(l\) 的回文数量即可。
Code
#include<bits/stdc++.h>
#define int long long
#define I_love_Foccarus return
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define endl '\n'
//#define getchar getc
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pd(a) push_back(a)
#define in(a) a = read_int()
using namespace std;
const int Size = 1 << 14;
const int N = 3e7 + 5;
const int inf = 0x3f3f3f3f , mod = 19930726;
const long long INF = 0x3f3f3f3f3f3f3f3f;
inline char getc(){static char syn[Size] , *begin = syn , *end = syn;if(begin == end) begin = syn , end = syn + fread(syn , 1 , Size , stdin);I_love_Foccarus *begin ++;
}
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();I_love_Foccarus f ? -x : x;
}
int m[N] , w[N] , k;
int manacher(string a) {string s = "#";for(int i = 0 ; i < a.size() ; i ++) {s += a[i];s += "#";}int n = s.size();for(int i = 1 , mid = 0 , r = 0 ; i < n ; i ++) {if(i < r) m[i] = min(m[2 * mid - i] , r - i);else m[i] = 1;while(i - m[i] >= 0 && i + m[i] < n && s[i - m[i]] == s[i + m[i]]) m[i] ++;if(i + m[i] > r) {mid = i , r = i + m[i];}}int ans = 0;for(int i = a.size() - k + 1 ; i < n ; i ++) {m[i] --;if(m[i] >= k && ((m[i] & 1) == (k & 1))) ans ++;}return ans;
}
signed main() {//cin_fast;int o;string a;cin>>o>>k>>a;cout<<manacher(a + a);I_love_Foccarus 0;
}今天是我们队的新人——蟑螂（绰号）的生日！祝他生日快乐！为啥我生日的时候无人过问捏？可能是我已经不小了吧，好像到了初中就没怎么过过生日了，家里人都很忙，也聚不齐。吃生日蛋糕，但是我对鸡蛋过敏，所以吃了盘奶油，变得更油腻了。