当学了一种算法，是一定要先写写题目。不要自以为 OK 就结束了，不然你都不知道，这能干啥子？或者你用不用的来 QAQ只好 把一些中等题目的题解放上来
为了拉低站里题目的难度（蒟蒻自以为中等的题）
让我们愉悦的学习吧 OvO
先放个题目链接
POI2010 ANT-Antisymmetry
POI2010 KOR-Beads
POI2012 OKR-A Horrible Poem
First. ANT-Antisymmetry
题意 ： 对于一个 0,1 序列，求出其中异或意义下有回文子串的数量。
我们可以看出，这个其实是一个对于异或意义下的回文子串数量的统计我们对回文的定义是，对于任意 $i,S[i]=~S[n−i+1]$，而我们把相等改为异或操作，那么，异或意义下就是当且仅当 1 与 0 相匹配时，返回值为 1 也就是 “真”。
思路：正解是 Manache 算法 变形，这里先写个哈希做，符合的串肯定是偶数长 且 前后对应的字符相反，那么把原串和反串都做一次哈希比较，然后枚举分界点二分最远的距离。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
const int maxn=1e6+7;
const ll mod=1e9+7;
char s[maxn],t[maxn];
//t[] 表示 s[] 异或后的数组
ll base[maxn],p[maxn],q[maxn];
//base 用来做 hash，p[] 保存的是 s[] 的哈希表,q[] 保存的是 t[] 的哈希表
ll hashs(int pos,int len,int flag){
if(!flag) return (p[pos] - p[pos-len] * base[len] % mod + mod) % mod;//对 s[] 后 len 进行 hash
else return (q[pos] - q[pos+len] * base[len] %mod + mod) % mod;//对 t[] 前 len 进行 hash
}
int cal(int pos,int len){
if(s[pos] == s[pos+1]) return 0;//如果相等，表示距离为 0，数量为 0
int l=1,r=len;
while(l <= r){
if(hashs(pos,mid,0) != hashs(pos+1,mid,1)) r=mid-1;//返回刚好 hash 不相等的 r 再 -1
else l=mid+1;
}//pos+1 是 s[pos] == t[pos+1] 进行匹配
return r;
}
int n;
ll ans;
int main(int argc, char const *argv[])
{
scanf("%d",&n);
base[0]=1;
fors(i,1,n) base[i]=base[i-1] * 233 % mod;
scanf("%s",s+1);
fors(i,1,n){
t[i] = '1'- s[i] +'0' ;//相当于 1- '1' +0 = 0 1- '0' +0= 1 表示取反
p[i]=(p[i-1] * 233 % mod +s[i]) % mod;//保存 t[] 的哈希表
}
ford(i,n,1){
q[i]=(q[i+1] * 233 % mod + t[i]) %mod;//保存 s[] 的哈希表
}
fors(i,1,n-1)
ans+=cal(i,min(i,n-i));//min() 操作-len 对 1~n-1 的点 cal() 累加
printf("%lld\n",ans);
return 0;
}
正解的 Manache 算法
const int maxn=1e7+7;//要开两倍数组
const ll mod=1e9+7;
char s[maxn],t[maxn],to[120];
//读入 s, 用 t 做 Manache，to, 做取反
int n,len[maxn],tot=1;
int main(int argc, char const *argv[])
{
scanf("%d%s",&n,t+1);
//Manache 初始化
s[0]='$',s[1]='#';
to['1']='0',to['0']='1',to['#']='#',to['$']='$';
//取反
fors(i,1,n){
s[++tot]=t[i],s[++tot]='#';//因为处理不了奇数长度所以*2，每个字符后面再加个字符
}
int pos=1,maxs=1;
ll ans=0;
for(int i=1;i<=tot;i+=2){
len[i]=(i < maxs ? min(maxs-i , len[pos*2 - i]) : 1) ; 初始化长度
while(s[i+len[i]] == to[s[i-len[i]]])
++len[i];//最大回文串长度
if(len[i]+i > maxs) {
maxs=len[i]+i;
pos=i;//更新
}
ans+=len[i]>>1;
}
printf("%lld\n",ans);
return 0;
}
~
~
Second. KOR-Beads
题意：给出 n 个数，可将它们分为若干个串，每个串有 k 个数（长度不足 k 则丢弃），求使得不同的串最多的 k 值及串的个数。串可翻转，即子串 1,2,3 和 3,2,1 被认为是一样的。
思路 ： 因为枚举数是个调和级数
$(n/1 + n/2 + n/3 +…+n/n) $
$≈ n * (1+1/2+1/3+…+1/n ) <= ln ~n）$
所以直接暴力枚举, 再哈希判断一下。
set<ll> S;
int n,ank,siz,a[maxn],ans[maxn];
ll base[maxn],hashs1[maxn],hashs2[maxn];
int main(int argc, char const *argv[])
{
cin>>n;
base[0]=1;
fors(i,1,n){
base[i]=base[i-1]*233;//做哈希的幂数组
hashs1[i]=hashs1[i-1]*233+a[i];//前缀哈希
cin>>a[i];
}
ford(i,n,1){
hashs2[i]=hashs2[i+1]*233+a[i];//后缀哈希
}
fors(i,1,n){
if(n/i < ank) break;//长度 < 个数 不合题意 结束
S.clear();
int cnt=0;
for(int j=i;j<=n;j+=i){//暴力枚举
int tmp1=hashs1[j]-hashs1[j-i]*base[i];
int tmp2=hashs2[j-i+1]-hashs2[j+1]*base[i];
int tmp3=tmp2*tmp1;//如果相同就是相当于平方了，在放到 set 判定。
if(S.count(tmp3)) continue;//如果相同则跳过
S.insert(tmp3);
++cnt;
}
if(cnt > ank){//更新个数
ank = cnt;
siz=0;
ans[++siz]=i;
}
else if(cnt == ank) ans[++siz]=i;
}
printf("%d %d\n",ank,siz);
for(int i=1;i<=siz;i++)
printf("%d ",ans[i]);
return 0;
}
~
~
Third. OKR-A Horrible Poem
题意 ： 给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。
思路：
1、循环节一定是长度的约数
2、如果 $len$是一个循环节，那么 $k*n$也必定是一个循环节（关键所在）
3、n 是 $[l,r]$这一段的循环节 的充要条件是 $[l,r-len]$和 $[l+len,r]$相同
所以我们可以在求出这个区间的长度之后，判断它的每个约数是否是循环节（应用性质 3），并且因为性质 1，它的约数是循环节，原串一定也是。
所以只要不断除以质因数（相当于从大到小枚举约数），缩小 L 的长度，最后就是最小的长度。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define fors(i,a,b) for(int i=(a);i=(b);--i)
typedef long long ll;
const int maxn=5e5+7;
ll hash1[maxn],base[maxn],prime[maxn],vis[maxn],nexts[maxn],minpe[maxn];
int k;
int read(){
int s=0;
char c=getchar();
while(c>'9' || c<'0') c=getchar();
while(c<='9' && c>='0') {s=(s<<1)+(s<<3)+c-'0';c=getchar();}
return s;
}
void init(){
fors(i,2,maxn){
if(!vis[i]){
prime[++k]=i;
nexts[i]=i;//记录因子
}
for(int j=1,l=0;j<=k && (l=i*prime[j]) <=maxn;++j ){
vis[l]=1;
nexts[l]=prime[j];
if(i%prime[j]==0) break;
}
}
}
int check(int l,int r,int len){
return hash1[l+len-1]-hash1[l-1]*base[len]==hash1[r]-hash1[r-len]*base[len];//以 l,r 为基点分别+-len 做哈希判断
}
int q,n,ans;
char s[maxn];
int main(){
n=read();
scanf("%s",s+1);
hash1[0]=base[0]=1;
fors(i,1,n){
hash1[i]=hash1[i-1]*23+s[i]-'a'+1;
base[i]=base[i-1]*23;
}
init();
for (int T=read(),l,r,len; T; --T){
for (l=read(),r=read(),ans=len=r-l+1; len>1; len/=nexts[len])
if (check(l,r,r-l+1-ans/nexts[len])) ans/=nexts[len];
printf("%d\n",ans);//r-l+1-ans/nexts[len] 为长度
}
return 0;
}
如果发现哪里有 BUG ， 还请 dalao 们提出 OVO 。
0 条评论