当学了一种算法,是一定要先写写题目。不要自以为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 。

分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *