慕容琳的后花园
慕容琳的后花园
算法进阶#基本数据结构#B

T1-Snowflakes

给定n个长度为6的序列,求有无相同的序列,相同序列的定义是顺时针或逆时针的最小表示相同

解法

每次将读进来的序列哈希一下,做个哈希表,判断有无相同序列

ac代码

#include<bits/stdc++.h>
using namespace std; 
const unsigned long long inf=160001; 
unsigned long long h[inf],a[21],n;
int fd(unsigned long long k)
{
    unsigned long long g=k%inf,i=0; 
    while(i<inf&&h[(g+i)%inf]&&h[(g+i)%inf]!=k)i++; 
    return (g+i)%inf; 
}
bool hsh(unsigned long long ans1,unsigned long long ans2)
{
    bool b=0;unsigned long long i,summ,ans=ans1,sum=0;  
    for(i=0;i<6&&a[ans1+i]==a[ans2-i];i++);
    if(a[ans1+i]>a[ans2-i]){ans=ans2;b=1;}
    if(b)
    {
        for(unsigned long long j=ans;j>ans-6;j--)
            sum=sum*13131+a[j]; 
    }
    else
    {
        for(unsigned long long j=ans;j<ans+6;j++) 
            sum=sum*13131+a[j];
    }
    if(h[(summ=fd(sum))]==sum)return 1; 
    h[summ]=sum;return 0; 
}
int main()
{
    scanf("%llu",&n);
    while (n--)
    {
        for(unsigned long long i=7;i<=12;i++) 
            scanf("%llu",&a[i]),a[i-6]=a[i+6]=a[i]; 
        int ii=7,jj=8,kk; 
        while(ii<=12&&jj<=12)
        {
            kk=0;while(kk<=6&&a[ii+kk]==a[jj+kk])kk++; 
            if(kk==6)break;
            if(a[ii+kk]>a[jj+kk]){ii=ii+kk+1;if(ii==jj)ii++;} 
            else {jj=jj+kk+1;if(ii==jj)jj++;}
        }
        unsigned long long ans1=min(ii,jj);ii=12,jj=11;
        while(ii>=7&&jj>=7)
        {
            kk=0;while(kk<=6&&a[ii-kk]==a[jj-kk])kk++; 
            if(kk==6)break;
            if(a[ii-kk]>a[jj-kk]){ii=ii-kk-1;if(ii==jj)ii--;} 
            else{jj=jj-kk-1;if(ii==jj)jj--;}
        }
        unsigned long long ans2=max(ii,jj); 
        if(hsh(ans1,ans2))
        {
            printf("Twin snowflakes found.");
            return 0; 
        }
    }
    printf("No two snowflakes are alike."); 
}

T2-兔子与兔子

很久很久以前,森林里住着一群兔子。有一天,兔子们想要研究自己的DNA序列。我们首先选取一个好长好长的DNA序列(小兔子是外星生物,DNA序列可能包含26个小写英文字母),然后我们每次选择两个区间,询问如果用两个区间里的DNA序列分别生产出来两只兔子,这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的DNA序列一模一样。

解法

线性的将所有前缀的哈希值求出,之后只要按照数位相减就可以求得一个区间的哈希值

ac代码

#include<bits/stdc++.h>
using namespace std; 
char s[1000010];
unsigned long long f[1000010],p[1000010];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1),q;
    scanf("%d",&q);
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        f[i]=f[i-1]*131+(s[i]-'a'+1);
        p[i]=p[i-1]*131;
    }
    for(int i=1;i<=q;i++)
    {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(f[r1]-f[l1-1]*p[r1-l1+1]==f[r2]-f[l2-1]*p[r2-l2+1])puts("Yes");
        else puts("No");
    }
    return 0;
}

T3-Manacher

给定一个字符串,求出其最长回文子串。

解法

就是Manacher算法,最长回文串模板题。

ac代码

#include<bits/stdc++.h>
using namespace std;
char s[12000005],st[12000005];
int p[12000005],cnt=0;
int change()
{
    int len=strlen(st),j=2;
    s[0]='^',s[1]='$';
    for(int i=0;i<len;i++)s[j++]=st[i],s[j++]='$';
    s[j]='&';
    return j;
}
int manacher()
{
    int len=change(),mid=1,mx=1,ans=-1;
    for(int i=1;i<len;i++)
    {
        if(i<mx)p[i]=min(mx-i,p[mid*2-i]);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(mx<i+p[i])mid=i,mx=i+p[i];
        ans=max(ans,p[i]-1);
    }
    return ans;
}
int main()
{
    while(~scanf("%s",st)&&st[0]!='E')printf("Case %d: %d\n",++cnt,manacher());
}

T4-后缀数组

给定一个字符串,求出这个字符串的后缀按照字典序排序的结果,并求出排名为i与排名为i-1的后缀的最长公共前缀

解法

这道题数据范围是30w,所以可以用hash,二分来实现求解最长公共前缀,用倍增或DC3解后缀排序

ac代码

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
unsigned long long t1[N],t2[N],sa[N],h[N],rk[N],c[10*N],a[N],f[N],p[N];
char s[N];
unsigned long long m,n;
void calcsa(unsigned long long n,unsigned long long m){
    unsigned long long *x=t1,*y=t2,p=0,f=0;
    for(unsigned long long i=1;i<=m;i++)c[i]=0;
    for(unsigned long long i=1;i<=n;i++)c[x[i]=a[i]]++;
    for(unsigned long long i=1;i<=m;i++)c[i]+=c[i-1];
    for(unsigned long long i=n;i;i--)sa[c[x[i]]--]=i;
    for(unsigned long long i=1;i<=n&&p<=n;i<<=1){
        p=0;
        for(unsigned long long j=n-i+1;j<=n;j++)y[++p]=j;
        for(unsigned long long j=1;j<=n;j++)if(sa[j]>i)y[++p]=sa[j]-i;
        for(unsigned long long j=1;j<=m;j++)c[j]=0;
        for(unsigned long long j=1;j<=n;j++)c[x[y[j]]]++;
        for(unsigned long long i=1;i<=m;i++)c[i]+=c[i-1];
        for(unsigned long long j=n;j;j--)sa[c[x[y[j]]]--]=y[j];
        swap(x,y);x[sa[1]]=1;p=2;
        for(unsigned long long j=2;j<=n;j++)
        x[sa[j]]=y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i]?p-1:p++;
        m=p;
    }
    for(unsigned long long i=1;i<=n;i++)rk[sa[i]]=i;
    for(unsigned long long i=1;i<=n;i++){
        unsigned long long j=sa[rk[i]-1];
        if(f)f--;while(a[i+f]==a[j+f])f++;
        h[rk[i]]=f;
    }
}
unsigned long long get_hash(unsigned long long l,unsigned long long r){return f[r]-f[l-1]*p[r-l+1];}
//最长公共前缀,二分+Hash 
unsigned long long lcp(unsigned long long x,unsigned long long y)
{
    unsigned long long l=0,r=min(n-x+1,n-y+1)+1;
    while(l<r)
    {
        unsigned long long mid=(l+r+1)>>1;
        if(get_hash(x,x+mid-1)==get_hash(y,y+mid-1))l=mid;else r=mid-1;
    }
    return l;
}
int main(){
    scanf("%s",s+1),p[0]=1;
    unsigned long long len=strlen(s+1);
    for(unsigned long long i=1;i<=len;i++)a[++n]=s[i]-' ',f[i]=f[i-1]*133+s[i]-'a'+1,p[i]=p[i-1]*133;
    calcsa(n,10000);
    for(unsigned long long i=1;i<=n;i++)printf("%d ",sa[i]-1);
    printf("\n0");
    for(unsigned long long i=2;i<=n;i++)printf(" %d",lcp(sa[i-1],sa[i]));
    return 0;
}

T5-周期串

给定一个字符串S,我们想知道S的前缀是否是周期串。
也即对于任意的i∈[2,N],我们想知道以i为长度的S的前缀,是否能表示成Ak(即字符串A可以重复K次)
如:S=aabaabaabaab,其长度N=12。
对于任意2<=i<=12长度的前缀我们可以得到:
i=2,长度为2的前缀为‘aa’,可以表示成a2;
i=3,4,5时的前缀都没有周期串;
i=6,前缀为‘aabaab’,可以表示成(aab)2;
i=7、8、10、11时的前缀都没有周期串;
i=9,前缀为‘aabaabaab’,可以表示成(aab)3;
i=12,前缀为‘aabaabaabaab’,可以表示成(aab)4;

解法

求一个next数组,然后手推一下

ac代码

#include<bits/stdc++.h>
using namespace std;
char a[1000010];
int next[1000010],n,T;
void calc_next()
{
    next[1]=0;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j>0&&a[i]!=a[j+1])j=next[j];
        if(a[i]==a[j+1])j++;
        next[i]=j;
    }
}
int main()
{
    while(cin >> n && n)
    {
        scanf("%s",a+1),calc_next();
        printf("Test case #%d\n",++T);
        for(int i=2;i<=n;i++)
            if(i%(i-next[i])==0&&i/(i-next[i])>1)printf("%d %d\n",i,i/(i-next[i]));
        puts("");
    }
}

T6-前缀统计

给定N个字符串S1,S2…SN,接下来进行M次询问,每次询问给定一个字符串T,求S1~SN中有多少个字符串是T的前缀。输入字符串的总长度不超过10^6,仅包含小写字母。

解法

先把给定的字符串压进字典树,在终点+1,然后询问时也走字典树,答案是经过的所有的路径的累加和

ac代码

#include<bits/stdc++.h>
using namespace std;
int a[2000000],n,m,l,len=1,so[2000000][30];
char s[1000010];
int fd()
{
    int p=1;
    for(int k=0;k<l;k++)
    {
        int ch=s[k]-'a';
        if(so[p][ch]==0)so[p][ch]=++len;
        p=so[p][ch];
    }
    a[p]++;
}
int getans()
{
    int p=1,ans=0;
    for(int k=0;k<l;k++)
    {
        p=so[p][s[k]-'a'];
        if(p==0)return ans;
        ans+=a[p];
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",s),l=strlen(s),fd();
    for(int i=1;i<=m;i++)
        scanf("%s",s),l=strlen(s),printf("%d\n",getans());
    return 0;
}

T7-The XOR Largest Pair

在给定的N个整数A1,A2……AN中选出两个进行xor运算,得到的结果最大是多少?

解法

因为xor计算实质是在二进制上的计算,写一个字典树,先把这个数插进去,然后搜答案的时候尽量走反的路径

ac代码

#include<bits/stdc++.h>
using namespace std;
int a[100010],n,len=1,so[2000000][2],ans=0;
int fd(int ll)
{
    int p=1;
    for(int k=30;k>=0;k--)
    {
        int ch=ll>>k&1;
        if(so[p][ch]==0)so[p][ch]=++len;
        p=so[p][ch];
    }
}
int getans(int ll)
{
    int p=1,res=0;
    for(int k=30;k>=0;k--)
    {
        int ch=ll>>k&1;
        if(so[p][ch^1])
        {
            res|=1<<k;
            p=so[p][ch^1];
        }
        else p=so[p][ch];
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),fd(a[i]),ans=max(ans,getans(a[i]));
    printf("%d",ans);
    return 0;
}

T8-The xor-longest Path

给定一个n个结点的树,树上每条边都有一个权值。从树中选择两个点 x 和y,把从x到y的路径上的所有边权值xor起来,得到的结果最大是多少?注意结点编号从0开始

解法

因为a^a=1,所以我们深搜一遍,d[i]就是i到根节点的异或和,之后就和上一道题一样,压进字典树

ac代码

#include<bits/stdc++.h>
using namespace std;
int a[100010],n,len,so[2000000][2],ans;
int fd(int ll)
{
    int p=1;
    for(int k=30;k>=0;k--)
    {
        int ch=ll>>k&1;
        if(so[p][ch]==0)so[p][ch]=++len;
        p=so[p][ch];
    }
}
int getans(int ll)
{
    int p=1,res=0;
    for(int k=30;k>=0;k--)
    {
        int ch=ll>>k&1;
        if(so[p][ch^1])
        {
            res|=1<<k;
            p=so[p][ch^1];
        }
        else p=so[p][ch];
    }
    return res;
}
struct edge{int to,next,w;}e[200010];
int head[100010],x,y,z,cnt;
void add(){x++,y++,e[++cnt]=(edge){y,head[x],z},head[x]=cnt,e[++cnt]=(edge){x,head[y],z},head[y]=cnt;}
void dfs(int u,int fa,int s)
{
    a[u]=a[fa]^e[s].w;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        if(e[i].to==fa)continue;
        dfs(e[i].to,u,i);
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(head,-1,sizeof(head)),cnt=0,len=1,ans=0;
        memset(a,0,sizeof(a)),memset(so,0,sizeof(so));
        for(int i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),add();
        dfs(1,1,0);
        for(int i=1;i<=n;i++)ans=max(ans,getans(a[i])),fd(a[i]);
        printf("%d\n",ans);
    }
    return 0;
}

T9-Matrix

给定一个M行N列的01矩阵(只包含数字0或1的矩阵),再执行Q次询问,每次询问给出一个A行B列的01矩阵,求该矩阵是否在原矩阵中出现过。

解法

我们对n×m的原矩阵中所有a×b的子矩阵求hash值,建立哈希表,之后求出询问的矩阵的hash值,在哈希表中查找

ac代码

#include<bits/stdc++.h>
const int base1=10016957,base2=10016959,mod=10100;
using namespace std;
struct abcd
{
    unsigned num;
    int next;
}table[1000010];
int m,n,a,b,q,hash_table[mod],tot;
unsigned sum[1010][1010],power1[1010],power2[1010];
void Hash(unsigned x)
{
    int pos=x%mod;
    table[++tot].num=x,table[tot].next=hash_table[pos],hash_table[pos]=tot;
}
bool Get_Hash(unsigned x)
{
    int pos=x%mod;
    for(int i=hash_table[pos];i;i=table[i].next)
    if(table[i].num==x)return true;
    return false;
}
int main()
{
    scanf("%d%d%d%d",&m,&n,&a,&b);
    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)scanf("%1d",&sum[i][j]);
    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)sum[i][j]+=sum[i-1][j]*base1;
    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)sum[i][j]+=sum[i][j-1]*base2;
    power1[0]=power2[0]=1;
    for(int i=1;i<=1000;i++)power1[i]=power1[i-1]*base1,power2[i]=power2[i-1]*base2;
    for(int i=a;i<=m;i++)for(int j=b;j<=n;j++)
    {
        unsigned temp=sum[i][j]-sum[i-a][j]*power1[a]-sum[i][j-b]*power2[b]+sum[i-a][j-b]*power1[a]*power2[b];
        Hash(temp);
    }
    for(scanf("%d",&q);q;q--)
    {
        for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)scanf("%1d",&sum[i][j]);
        for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)sum[i][j]+=sum[i-1][j]*base1;
        for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)sum[i][j]+=sum[i][j-1]*base2;
        unsigned temp=sum[a][b];
        if(Get_Hash(temp))puts("1");else puts("0");
    }
    return 0;
}

T10-Necklace

给定两个项链的表示,判断他们是否可能是一条项链。

解法

求两个字符串的最小表示,之后判断是否相同即可

ac代码

#include<bits/stdc++.h>
using namespace std;
char s1[2000010],s2[2000010];
int n,l,r,k,ans1,ans2;
int main()
{
    scanf("%s",s1+1);
    n=strlen(s1+1),l=1,r=2,k;;
    for(int i=1;i<=n;i++)s1[n+i]=s1[i];
    while(l<=n&&r<=n)
    {
        for(k=0;k<n&&s1[l+k]==s1[r+k];k++);
        if(k==n)break;
        if(s1[l+k]>s1[r+k])
        {
            l+=k+1;
            if(l==r)l++; 
        }
        else
        {
            r+=k+1;
            if(l==r)r++;
        }
    }
    ans1=min(l,r);
    /*****/
    scanf("%s",s2+1);
    n=strlen(s2+1),l=1,r=2,k;;
    for(int i=1;i<=n;i++)s2[n+i]=s2[i];
    while(l<=n&&r<=n)
    {
        for(k=0;k<n&&s2[l+k]==s2[r+k];k++);
        if(k==n)break;
        if(s2[l+k]>s2[r+k])
        {
            l+=k+1;
            if(l==r)l++; 
        }
        else
        {
            r+=k+1;
            if(l==r)r++;
        }
    }
    ans2=min(l,r);
    for(int i=1;i<=n;i++)
    {
        if(s1[ans1+i-1]!=s2[ans2+i-1])
        {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    for(int i=1;i<=n;i++)
        printf("%c",s1[ans1+i-1]);
    return 0;
}

T11-Milking Grid

每天早晨FARMER JOHN的奶牛都会在挤奶时排成矩形,R行(1<=R<=10,000),C列(1<=C<=75)。我们知道,FARMER JOHN是奶牛专家,他打算写一本关于喂养奶牛的书。他发现,当奶牛按照不同的血统标记以后,整个大矩形就像由很多相同的小矩形拼起来的一样。
请帮助FJ找到面积最小的小矩形,使它能拼出整个大矩形。小矩形的尺寸不一定要整除大矩形的,但是小矩形的排列一定要非常整齐,不允许出现错位之类的情况,即你可以用若干个小矩形拼出一个包含大矩形的矩形。
比如,对于下面的矩形:
ABABA
BABAB
最小的面积应该是4,而不是2。

解法

就是求出横向和纵向最小重复的子串,使用KMP的next数组,和之前周期串的题目相同

ac代码

#include<bits/stdc++.h>
using namespace std;
char s[10010][80],a[80];
int next[10010],i,j,x,y,r,c,f[80];
int main()
{
    scanf("%d%d",&r,&c);
    for(i=0;i<c;i++)f[i]=0;
    for(i=0;i<r;i++)
    {
        scanf("%s",s[i]),strcpy(a,s[i]);
        for(j=c-1;j>0;j--)
        {
            a[j]=0;
            for(x=0,y=0;s[i][y];x++,y++)
            {
                if(!a[x])x=0;
                if(a[x]!=s[i][y])break;
            }
            if(!s[i][y])f[j]++;
        }
    }
    for(i=0;i<c;i++)if(f[i]==r)break;
    x=i,next[0]=-1;
    for(i=0;i<r;i++)s[i][x]=0;
    for(i=1,j=-1;i<r;i++)
    {
        while(j!=-1&&strcmp(s[j+1],s[i]))j=next[j];
        if(!strcmp(s[j+1],s[i]))j++;
        next[i]=j;
    }
    printf("%d\n",(r-1-next[r-1])*x);
    return 0;
}

T12-匹配统计

阿轩在纸上写了两个字符串,分别记为A和B。利用在数据结构与算法课上学到的知识,他很容易地求出了“字符串A从任意位置开始的后缀子串”与“字符串B”匹配的长度。
不过阿轩是一个勤学好问的同学,他向你提出了Q个问题:在每个问题中,他给定你一个整数x,请你告诉他有多少个位置,满足“字符串A从该位置开始的后缀子串”与B匹配的长度恰好为x。
例如:A=aabcde,B=ab,则A有aabcde、abcde、bcde、cde、de、e这6个后缀子串,它们与B=ab的匹配长度分别是1、2、0、0、0、0。因此A有4个位置与B的匹配长度恰好为0,有1个位置的匹配长度恰好为1,有1个位置的匹配长度恰好为2。

解法

求出B对于A的next数组,之后手推一下

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,m,q,nxt[200010],f[200010],cnt[200010],x;
char a[200010],b[200010];
unsigned long long Ha[200010],Hb[200010],p[200010];
void nt()
{
    nxt[1]=0;
    for(int i=2,j=0;i<=m;i++)
    {
        while(j>0&&b[i]!=b[j+1])j=nxt[j];
        if(b[i]==b[j+1])j++;
        nxt[i]=j;
    }
}
int main()
{
    scanf("%d%d%d%s%s",&n,&m,&q,a+1,b+1),nt();
    for(int i=1,j=0;i<=n;i++)
    {
        while(j>0&&(j==m||a[i]!=b[j+1]))j=nxt[j];
        if(a[i]==b[j+1])j++;
        f[i]=j;
    }
    for(int i=1;i<=n;i++)cnt[f[i]]++;
    for(int i=m;i>=1;i--)cnt[nxt[i]]+=cnt[i];
    while(q--)scanf("%d",&x),printf("%d\n",cnt[x]-cnt[x+1]);
    return 0;
}

T13-Phone List

给定一些字符串,求这些字符串中有无字符串是别的字符串的前缀

解法

可以按长度从大到小排序,之后一个个压进字典树并查找,也可以全部压进去后一个个搜索

ac代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int a[200000],n,l,len=1,so[200000][10];
string s[10010];
int fd(int x)
{
    int p=1;
    for(int k=0;k<l;k++)
    {
        int ch=s[x][k]-'0';
        if(so[p][ch]==0)so[p][ch]=++len;
        p=so[p][ch];
        a[p]++;
    }
    a[p]--;
    if(a[p])return 1;
    else return 0;
}
bool cmp(string sa,string sb)
{
    return sa.length()>sb.length();
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int flg=0;
        len=1,memset(a,0,sizeof(a)),memset(so,0,sizeof(so)),scanf("%d",&n);
        for(int i=1;i<=n;i++)cin >> s[i];
        //sort(s+1,s+1+n,cmp);
        for(int i=1;i<=n;i++){l=s[i].length();if(fd(i))flg=1;}
        if(!flg)for(int i=1;i<=n;i++){l=s[i].length();if(fd(i))flg=1;}
        if(flg)printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

算法进阶#基本数据结构#B
T1-Snowflakes 给定n个长度为6的序列,求有无相同的序列,相同序列的定义是顺时针或逆时针的最小表示相同 解法 每次将读进来的序列哈希一下,做个哈希表,判断有无相同序列 ac代码 #…
扫描二维码继续阅读
2019-05-06
功能