题目链接

题意分析

\(olinr\) : 序列自动机+一系列的鬼畜操作

相信我 你们没人能切

\(lzxkj\) : \(2^m+vector+\)暴力二分 跑得比你正解还快

首先一看\(m≤5\) 直接\(2^m\)枚举所有的子序列

然后我们用一个\(vector\)把匹配序列中的权值相同的位置存入一个\(vector\)

匹配当前值的时候 直接二分找到刚好可以满足的位置就可以了

复杂度\(O(q* 2^m* m* log_n)\)(应该远不及上界)

CODE:

/*-------------OI使我快乐-------------*/
int n,m,len,ans1,maxn,ans2;
int num[M],key[N],lg[N],tmp[N];
vector<int> G[M];
vector<int>::iterator it;
IL int getlen(int x)
{int res=0;for(;x;x-=x&-x) res++;return res;}
IL bool check(int x)
{
    int pos=0;
    for(;x;x-=x&-x)
    {
        int now=lg[x&-x]+1;
        it=upper_bound(G[key[now]].begin(),G[key[now]].end(),pos);
        if(it==G[key[now]].end()) return 0;
        else pos=*it;
    }
    return 1;
}
IL void comp(int &x,int y)
{
    int cdy=x,wzy=y;
    for(;cdy&&wzy;cdy-=cdy&-cdy,wzy-=wzy&-wzy)
    {
        int nowx=lg[cdy&-cdy]+1,nowy=lg[wzy&-wzy]+1;
        if(key[nowx]>key[nowy]) {x=y;return;}
        else if(key[nowx]<key[nowy]) return;
    }
}
int main()
{
//  freopen("flag.in","r",stdin);
//  freopen("flag.out","w",stdout);
    read(n);
    for(R int i=1;i<=n;++i)
    {
        read(num[i]);
        G[num[i]].push_back(i);
        maxn=max(maxn,num[i]);
    } 
    for(R int i=0;i<=6;++i) lg[1<<i]=i;
    read(m);
    while(m--)
    {
        int len,tmp=0;ans1=0;ans2=0;read(len);
        for(R int i=1;i<=len;++i) read(key[i]); 
        for(R int i=0;i<(1<<len);++i)
        {
            
            if(check(i)) 
            {
                int tmp=getlen(i);
                if(tmp>ans1) ans1=tmp,ans2=i;
                else if(ans1==tmp) ans1=tmp,comp(ans2,i);
            }
        }
        printf("%d ",ans1);
        for(R int i=1;i<=len;++i)
        if((1<<(i-1))&ans2) printf("%d ",key[i]);puts("");      
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

HEOI 2019 RP++

SP9098 LCS3

原文：https://www.cnblogs.com/LovToLZX/p/10616837.html