列表

详情

NC51086. Substrings 2

描述

Two strings and are isomorphic if and only if k = l and there exists a injection such that for all .
Note that a function f is injection if and only if for all .

Bobo would like to choose some strings from all substrings of the given string .
Find out the maximum number of strings he may choose so that no two chosen strings are isomorphic.

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains a string .

* 
* 
* There are at most  test cases, and at most 5 of them have n > 50.

输出描述

For each test case, print an integer which denotes the result.

示例1

输入: 

3
1 2 3
3
1 2 2
5
1 3 1 2 5

输出: 

3
4
7

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

C++14(g++5.4) 解法, 执行用时: 2785ms, 内存消耗: 181408K, 提交时间: 2019-07-22 10:12:00 

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define per(i,a,b) for(int i=(a);i>=(b);i--)

#define REP(i,n) for(int i=(0);i<(n);i++)

#define fi first

#define se second

#define pb push_back

#define mp make_pair

using namespace std;

typedef pair<int,int> pii;

typedef vector<int> vi;

typedef long long ll;



template<class T> inline void read(T &x){

    int f=0;x=0;char ch=getchar();

    for(;!isdigit(ch);ch=getchar())f|=(ch=='-');

    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';

    if(f)x=-x;

}



const int bas=2333,mod=998244353;

const int N=50005,T=250;

const int B=T+5,M=N/T+5;

int id[N][M],pre[N][M],b[N][B],s[N][B];

int bel[N],st[N],a[N],rk[N],p[N],las[N];

int n,sz,cnt;



inline void upd(int k,int x,int v){

    int pos=bel[x],las=id[k][pos];

    id[k][pos]=++sz;

    REP(i,st[pos+1]-st[pos]){

        if(i+st[pos]==x)b[sz][i]=v;

        else b[sz][i]=b[las][i];

        s[sz][i]=b[sz][i];

        if(i)s[sz][i]=(s[sz][i]+(ll)s[sz][i-1]*bas)%mod;

    }

    rep(i,pos,cnt){

        int len=st[i+1]-st[i];

        pre[k][i]=((ll)pre[k][i-1]*p[len]

                        +s[id[k][i]][len-1])%mod;

    }

}

inline int qry(int k,int x){

    int pos=bel[x],len=x-st[pos]+1;

    return ((ll)pre[k][pos-1]*p[len]+s[id[k][pos]][len-1])%mod;

}

inline int val(int k,int x){

    if(x>n)return -1;int pos=bel[x];

    return b[id[k][pos]][x-st[pos]];

}

inline int getlcp(int x,int y){

    int l=0,r=n-max(x,y)+1,m;

    while(l<r){

        m=(l+r+1)>>1;

        qry(x,x+m-1)==qry(y,y+m-1)?l=m:r=m-1;

    }

    return l;

}

inline int cmp(int x,int y){

    int t=getlcp(x,y);

    return val(x,x+t)<val(y,y+t);

}



int main(){

    p[0]=1;

    rep(i,1,N-5)p[i]=(ll)p[i-1]*bas%mod;

    for(;~scanf("%d",&n);){

        sz=0;

        rep(i,1,n){

            read(a[i]);

            rk[i]=i,las[i]=0;

        }

        cnt=(n-1)/T+1;

        rep(i,1,cnt)

            bel[st[i]=(i-1)*T+1]=i;

        st[cnt+1]=n+1;

        rep(i,1,n)

            if(!bel[i])bel[i]=bel[i-1];

        memset(id[n+1],0,sizeof id[n+1]);

        memset(pre[n+1],0,sizeof pre[n+1]);

        per(i,n,1){

            rep(j,1,cnt)id[i][j]=id[i+1][j],pre[i][j]=pre[i+1][j];

            if(las[a[i]]){

                int j=las[a[i]];

                upd(i,j,j-i);

            }

            las[a[i]]=i;

        }

        sort(rk+1,rk+n+1,cmp);

        int ans=(ll)n*(n+1)/2;

        rep(i,2,n)ans-=getlcp(rk[i-1],rk[i]);

        printf("%d\n",ans);

    }

    return 0;

}

C++11(clang++ 3.9) 解法, 执行用时: 2359ms, 内存消耗: 239300K, 提交时间: 2019-07-18 23:03:14 

#include<bits/stdc++.h>

#define rep(i,x,y) for(auto i=(x);i<=(y);++i)

#define dep(i,x,y) for(auto i=(x);i>=(y);--i)

#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)

#define pb push_back

#define fr first

#define sc second

using namespace std;

typedef long long ll;

typedef pair<int,int>pii;

const int N=5e4+10;

const int M=300;

const ll mo=998244353;

const ll D=18113219;

const ll DL=181321;

ll pw[M],s[N][M],nw[N][M];int n,m,b[N],l[N],r[N];

inline bool cmp(int x,int y){

    rep(i,0,m)if(s[x][i]!=s[y][i]){

        rep(j,0,m){int p=m*i+j;

            if(x+p>n)return 1;

            if(y+p>n)return 0;

            int X=l[x+p]<x?0:l[x+p]-x+1;

            int Y=l[y+p]<y?0:l[y+p]-y+1;

            if(X<Y)return 1;

            if(X>Y)return 0;

        }

    }return 0;

}

void sol(){

    if(scanf("%d",&n)==EOF)exit(0);

    map<int,int>mp;m=sqrt(n)+1;

    rep(i,1,n){int x;

        scanf("%d",&x);

        if(mp[x])r[mp[x]]=i;

        l[i]=mp[x];r[i]=0;mp[x]=i;

    }

    rep(i,0,m)nw[n][i]=s[n][i]=0;

    s[n][0]=DL;

    dep(i,n-1,1){ll ls=DL;bool lf=0;

        rep(j,0,(n-i)/m){

            int p=i+(j+1)*m,c;

            nw[i][j]=(nw[i+1][j]*D+lf)%mo;lf=0;

            if(r[i]&&(r[i]-i)/m==j)(nw[i][j]+=pw[r[i]-(i+j*m)])%=mo;

            if(p<=n&&l[p]>i){

                lf=1;(nw[i][j]+=mo-pw[m])%=mo;

            }

            if(p<=n){

                if(l[p]<=i)c=DL;else c=DL+l[p]-i;

            }else c=0;

            s[i][j]=(s[i+1][j]*D+mo-c*pw[m]%mo+ls+nw[i][j])%mo;ls=c;

        }

    }

    rep(i,1,n)b[i]=i;

    sort(b+1,b+n+1,cmp);

    ll ans=n-b[1]+1;

    rep(i,2,n){int lcp=0;

        rep(j,0,m)if(s[b[i-1]][j]!=s[b[i]][j]){

            rep(k,0,m){int p=m*j+k;

                if(max(b[i-1],b[i])+p>n||

                (l[b[i-1]+p]<b[i-1]?0:l[b[i-1]+p]-b[i-1]+1)

                !=(l[b[i]+p]<b[i]?0:l[b[i]+p]-b[i]+1))break;

                ++lcp;

            }break;

        }else lcp+=m;

        ans+=n-b[i]-lcp+1;

    }

    printf("%lld\n",ans);

}

int main(){pw[0]=1;

    rep(i,1,M-1)pw[i]=pw[i-1]*D%mo;

    for(;;)sol();

}

上一题

© 2025 nowcoder.com