2022.1.28 考试总结+题解
T1.Palindromic Partitions
-
题面
洛谷题面
-
解析
这题十分钟才看懂到底要干啥……
就是说，把每个小块看成是一整个，然后用小块来组成回文串
比如样例的 bonobo ：
可以分成 bo、 no、 bo ，这样首尾小块相同，构成回文串
嗯……块如何辨别很好办，直接 \(\tt hash\) 就行
但是怎么保证划分出来数量最多？
一个显然的贪心策略是，能划分小块就尽量划分小块.
考虑正确性：
记首尾某两个块为 \(S\) 和 \(T\) .
若 \(S=T\) ，那么划分出来一定可以构成回文串，记录该种划分方案为 \(X_1\) ；此时 \(S\) 向右延伸 \(1\) 长度， \(T\) 向左延伸 \(1\) 长度，若仍有 \(S=T\) ，因为 \(S\) 与 \(T\) 中间的块长度减少 \(2\) ，划分出来一定不比 \(X_1\) 更优.
若 \(S \ne T\) ，无法划分，应继续延伸直到可划分，此时遵从情况一.
故贪心正确.
处理上，我们可以用三个指针 p1 、 p2 、 k ，分别指向首块的起始位置（从左往右延伸），尾块的起始位置（从右往左延伸）和延伸的块长，若 \(S_{p1,p1+k-1} \ne S_{p2-k+1,p2}\) ，则 ++k ；若相等则两块头指针同时移动并且统计答案，注意是分出两块所以 ans+=2 .
另外注意结束条件，当首尾两块交叉时应该 ++ans 并退出，因为这说明中间一整块无法被细分.
最后还要判断答案是否为 \(0\) ，如果是就设成 \(1\) ，因为最少也能分出一整块. 因为这个WA了20pts
-
code
#include
#define ri register int
#pragma GCC optimize("3","Ofast","inline")
#define MAXN 1000005
#define ull unsigned long long
using namespace std;
const int p=12289;
int T,len;
ull hush[MAXN];
ull pre[MAXN];
char s[MAXN];
inline ull ha5h(int l,int r){
if(l==r) return (ull)s[l];
if(l==1) return hush[r];
return hush[r]-hush[l-1]*pre[r-l+1];
}
inline void Sync(){
ios::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
}
int main()
{
Sync();
cin>>T; pre[0]=1;
for(ri i=1;i<=MAXN-1;i++)
pre[i]=pre[i-1]*p;
while(T--){
cin>>s+1; len=strlen(s+1);
for(ri i=1;i<=len;i++)
hush[i]=hush[i-1]*p+s[i];
ri p1=1,p2=len,k=1,ans=0;
while(p1=p2-k+1){
ans++;
break;
}
if(ha5h(p1,p1+k-1)==ha5h(p2-k+1,p2))
p1+=k,p2-=k,ans+=2,k=1;
if(p1==p2){
ans++;
break;
}
} cout< T2.绿绿和串串
-
题面
洛谷题面
-
解析
我的题解
之前打 \(\tt Manacher\) 的时候按标签搜索，总共就 \(5\) 道题，把其它四道都做了，只有这个没碰
我以为这是紫题会很难来着
看到这题一下就懂力，又考原题（
回文串，\(\tt Manacher\)
问题就在于马怎么拉这个车
首先考虑到答案里一定有一个是给出的串 \(S\) 的长度
然后就是怎么求出其它答案了
考虑翻转若干次后能够覆盖 \(S\) 的前缀 \(P\) ，它的结尾点在 \(\tt Manacher\) 中跑出来的回文串长一定大于 \(1\) ，此时分两种情况：
\(1.\) 它第一次翻转不能覆盖 \(S\) .
这种情况下，直接把它翻转然后跳跃到翻转过去的位置再判断，也就是跳跃到它的回文串右端点.
但是有可能它翻折过去之后不能和 \(S\) 在翻折终点位置的字符相匹配，注意到这等价于它的回文串的左右端点在 \(S\) 两端之内，直接判掉.
\(2.\) 它第一次翻转能够覆盖 \(S\) .
这就更好办了，只需要判断以它为轴的回文串右端点是否等于 \(S\) 的右端点即可.
然后……就做完了……
这题真的能紫嘛（
-
code
#include
#define ri register int
#define MAXN 3000001
#define ll long long
using namespace std;
//THU集训原题……
//但是那天晚上就这个没去看 草
//Manacher
//蛤蛤，整个manacher只有5道题，除了这个都做了(快乐
int T,lens;
string s;
int Rel[MAXN];
#define judge Shimokitazawa
inline void Manacher(){
lens=s.length();
string buf="%#";
for(ri i=0;iMxr)
Mxr=i+Rel[i],ind=i;
#ifndef judge
cout<<"len["<>T;
while(T--){
reset(Rel,0);
cin>>s;
Manacher();
for(ri i=2;i2&&j+Rel[j]-2<=lens-2;j+=Rel[j]-2){
//cout<<"j="<