先来一波胡测（未完）

Round 0

T1 po姐的送温暖题，但是我为啥就没去想 >.<

统计从左上到右下两条路径不相交的方案数。

如果只有一条路这是普及组。

记 $f(i,j,k,l)$ 为从 $(i,j)$到$(k,l)$的方案数。

如果我们没有相交，显然有

$$ans = f(2,1,n,m-1) cdot f(1,2,n-1,m)$$

接下来考虑只统计相交的路径。

神思路：

找到最后一个交点，转一下变为$(2,1)$走到$(n-1,m)$的路径和一条从$(1,2)$走到$(n,m-1)$的路径

然后我们惊讶地发现原先每种不合法的方案对应一个反转后的方案。

所以相交的对数为

$$f(1,2,n,m-1) cdot f(2,1,n-1,m)$$

思路很神，但是代码就没什么意思了。。。

T2 zrt的题，HEOI Day2 T3加强版

在一个子序列自动机和一个后缀自动机上dfs记忆化，有$O(n)$的边，$O(n^2)$的状态。

然后就没有然后了。。。

#include <cstdio>
#include <cstring>

#define N 4010
#define LL long long
#define mod 1000000007

using namespace std;

struct node{
    node *ch[26],*fa;
    int len,id;
    LL v;
};

struct SAM{
    node *root,spT[N<<1],*now;

    int tot;

    void addin(char c){
        int t=c-'a';
        node *np=&spT[++tot],*p=now;
        np->id=tot;
        np->len=p->len+1;
        now=np;
        for(;p&&!p->ch[t];p=p->fa) p->ch[t]=np;
        if(!p) np->fa=root;
        else{
            if(p->ch[t]->len==p->len+1) np->fa=p->ch[t];
            else{
                node *nq=&spT[++tot],*q=p->ch[t];
                *nq=*q;
                nq->len=p->len+1;
                nq->id=tot;
                q->fa=np->fa=nq;
                for(;p&&p->ch[t]==q;p=p->fa) p->ch[t]=nq;
            }
        }
    }
    
    void dfs(node *p){
        p->v=1;
        for(int i=0;i<26;i++)
            if(p->ch[i]){
                if(!p->ch[i]->v) dfs(p->ch[i]);
                (p->v+=p->ch[i]->v)%=mod;
            }
    }
    
    void build(char *S){
        now=root=&spT[tot=1];
        int len=strlen(S);
        for(int i=0;i<len;i++) addin(S[i]);
        dfs(root);
    }
}A1,A2;

struct SBM{
    node spT[N],*root,*a[26];
    int tot;
    
    void build(char *S){
        root=&spT[tot=1];
        root->id=tot;
        for(int i=0;i<26;i++) a[i]=NULL;
        for(int i=strlen(S)-1;~i;i--){
            node *p=&spT[++tot];
            p->id=tot;
            p->v=1;
            memcpy(p->ch,a,sizeof(a));
            for(int t=0;t<26;t++)
                if(p->ch[t]) (p->v+=p->ch[t]->v)%=mod;
            int t=S[i]-'a'; a[t]=p;
        }
        memcpy(root->ch,a,sizeof(a));
        for(int i=0;i<26;i++)
            if(root->ch[i]) root->v+=root->ch[i]->v;
    }
}B1,B2;

char S1[N],S2[N];
LL f[N][N];

LL dfs(node *a,node *b){
    if(!b) return a->v;
    if(f[a->id][b->id]!=-1) return f[a->id][b->id];
    LL ans=0;
    for(int t=0;t<26;t++)
        if(a->ch[t]) (ans+=dfs(a->ch[t],b->ch[t]))%=mod;
    return f[a->id][b->id]=ans;
}

int main(){
    scanf("%s%s",S1,S2);
    A1.build(S1);
    A2.build(S2);
    B1.build(S1);
    B2.build(S2);
    memset(f,-1,sizeof(f));
    printf("%lld
",dfs(A1.root,A2.root));
    memset(f,-1,sizeof(f));
    printf("%lld
",dfs(A1.root,B2.root));
    memset(f,-1,sizeof(f));
    printf("%lld
",dfs(B1.root,A2.root));
    memset(f,-1,sizeof(f));
    printf("%lld
",dfs(B1.root,B2.root));
    return 0;
}
View Code

T3呀。。算了吧，不过

是非常好的提答题（比CTSC的好多了）

Round 1

膜 ioi ZYF laekov

难了一点但是题很好。

T1

ioi大爷的题，LCT 莫对

ioi：“这种做法虽然在修改上多了一个log，但是由于常熟十分小，期望分数还是100分的”

报警了。

写的$O(nsqrt(n))$算法

首先对询问的串分块，然后每个块建AC自动机

查询$O(msqrt(n)+m|S|)$

然而：

int t=0;
for(int i=1;i<=n;i++){
    l[i]=t;
    scanf("%s",S1+t);
    t=strlen(S1);
    r[i]=t-1;
    Kmp_init(i);
}

QAQ读入是$O(n^2)$的变成30分真是醉了。

改了被卡常95分，不想（hui）卡常，不管了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <ctime>
#include <cctype>

#define N 500010
#define L(x) ((x-1)*size+1)
#define R(x) (min(x*size,n))

using namespace std;

inline int max(int a,int b){
    if(a<b) return b;
    return a;
}

char S1[N],S2[N];
int n,m,size,l[N],r[N],tot;

struct node{
    node *ch[26],*fail;
    int v,len;
}*q[N],spT[500010];

struct ACam{
    node* root;
    
    inline void init(){
        root=&spT[++tot];
    }
    
    inline void addin(int l,int r){
        node* tmp=root;
        for(int i=l;i<=r;i++){
            int t=S1[i]-'a';
            if(!tmp->ch[t]) tmp->ch[t]=&spT[++tot];
            tmp=tmp->ch[t];
        }
        tmp->v++;
        tmp->len=r-l+1;
    }
    
    int st,en;
    
    inline void getfail(){
        q[st=en=1]=root;
        while(st<=en){
            node* tmp=q[st++];
            if(tmp!=root){
                tmp->len=max(tmp->len,tmp->fail->len);
                tmp->v+=tmp->fail->v;
            }
            for(int t=0;t<26;t++){
                if(tmp->ch[t]!=NULL){
                    if(tmp==root) tmp->ch[t]->fail=root;
                    else tmp->ch[t]->fail=tmp->fail->ch[t];
                    q[++en]=tmp->ch[t];
                }
                else{
                    if(tmp==root) tmp->ch[t]=root;
                    else tmp->ch[t]=tmp->fail->ch[t];
                }
            }
        }
    }
    
    inline int ask(char *c){
        int ans=0;
        node* tmp=root;
        while(*c!=''){
            int t=*c-'a';
            tmp=tmp->ch[t];
            if(tmp->v) ans=max(ans,tmp->len);
            c++;
        }
        return ans;
    }
}AM[620];

int wb[N],f[N],lk[N],rk[N],ft[N],nt,tot_n=0;
char S[N];

inline void Kmp_init(int x){
    nt=0;
    for(int i=l[x];i<=r[x];i++) S[nt++]=S1[i];
    f[0]=0; f[1]=0;
    for(int i=1;i<nt;i++){
        int j=f[i];
        while(j&&S[i]!=S[j]) j=f[j];
        f[i+1] = S[i]==S[j]? j+1:0;
    }
    lk[x]=tot_n;
    for(int i=0;i<nt;i++) ft[tot_n++]=f[i];
    rk[x]=tot_n-1;
}

inline int ask(int x,char *St){
    nt=0;
    for(int i=l[x];i<=r[x];i++) S[nt++]=S1[i];
    int tmp=0;
    for(int i=lk[x];i<=rk[x];i++) f[tmp++]=ft[i];
    int nl=strlen(St),j=0;
    for(int i=0;i<nl;i++){
        while(j&&S[j]!=St[i]) j=f[j];
        if(S[j]==St[i]) j++;
        if(j==nt) return nt;
    }
    return 0;
}

inline int com_ask(int l,int r,char* S){
    int lb=wb[l],rb=wb[r],ans=0;
    if(lb==rb){
        for(int i=l;i<=r;i++)
            ans=max(ans,ask(i,S));
    }
    else{
        if(l!=L(lb)){
            for(int i=l;i<=R(lb);i++)
                ans=max(ans,ask(i,S));
        }
        for(int i= ((l==L(lb))? lb:lb+1);i<= ((r==R(rb))?rb:rb-1);i++)
            ans=max(ans,AM[i].ask(S));
        if(r!=R(rb)){
            for(int i=L(rb);i<=r;i++)
                ans=max(ans,ask(i,S));
        }
    }
    return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    int t=0;
    char ch;
    for(int i=1;i<=n;i++){
        l[i]=t;
        while(!isalpha(ch=getchar()));
        S1[t++]=ch;
        while(isalpha(ch=getchar())) S1[t++]=ch;
        r[i]=t-1;
        Kmp_init(i);
    }
    size=(int)sqrt(n+0.5);
    for(int i=1;i<=n;i++) wb[i]=(i-1)/size+1;
    for(int i=1;i<=wb[n];i++) AM[i].init();
    for(int i=1;i<=n;i++) AM[wb[i]].addin(l[i],r[i]);
    for(int i=1;i<=wb[n];i++) AM[i].getfail();
    for(int i=1,l,r;i<=m;i++){
        scanf("%d%d",&l,&r);
        t=0;
        while(!isalpha(ch=getchar()));
        S2[t++]=ch;
        while(isalpha(ch=getchar())) S2[t++]=ch;
        S2[t]='';
        printf("%d
",com_ask(l,r,S2));
    }
    return 0;
}
View Code

T2

QAQ，QAQ

一直在做T1 T3，没有理T2，最后发现裸的KD-tree 优化dp呀[捂脸]

ZYF业界良心。

（代码还是算了吧）

T3

QAQ还不会，待补完。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lawyer/p/4570263.html