2021“MINIEYE杯”中国大学生算法设计超级联赛（10）

终于要补完多校了。

[1001 Pty loves sequence]

solution

题面：

做法：

[1002 Pty with card]

solution

题面：

做法：

[1003 Pty loves lines]

solution

题面：问条直线的可能交点个数，需保证没有三线共点，也没有直线重合。

做法：把平行的直线分成一组，那只要枚举每一组有多少个数即可。这个显然可以用 bitset 优化，不过没什么卵用。

我考场是猜测答案的连续段个数不会太多，所以直接存连续段，然后用归并排序合并下即可。后来打表发现确实只有段，所以总复杂度为。

//2021.8.19 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=700+10;
namespace MAIN{
    Pair f[N][N],g[N<<1];
    int fx[N],gx;
    int a[N*N],ax;
    inline void MAIN(){
        res Case=read();
        f[1][0]=mp(0,0),fx[1]=1;
        for(res n=2;n<=N-10;n++){
            f[n][0]=(mp(0,0)),fx[n]=1;
            for(res i=1;i<n;i++){
                gx=0;
                res l=0,r=0,szl=fx[n-i]-1,szr=fx[n]-1;
                while(l<=szl&&r<=szr){
                    RG Pair x=mp(f[n-i][l].fi+i*(n-i),f[n-i][l].se+i*(n-i));
                    if(x<f[n][r])g[gx++]=(x),l++;
                    else g[gx++]=(f[n][r]),r++;
                }
                while(l<=szl){
                    RG Pair x=mp(f[n-i][l].fi+i*(n-i),f[n-i][l].se+i*(n-i));
                    g[gx++]=(x),l++;
                }
                while(r<=szr)g[gx++]=(f[n][r]),r++;
                fx[n]=1;
                f[n][0]=(g[0]);
                res now=0;
                for(res i=1;i<gx;i++){
                    if(f[n][now].se>=g[i].fi-1)f[n][now].se=max(f[n][now].se,g[i].se);
                    else f[n][fx[n]++]=(g[i]),now++;
                }
            }
        }
        while(Case--){
            res n=read();
            ax=0;
            for(res j=0;j<fx[n];j++){
                RG Pair x=f[n][j];
                for(res i=x.fi;i<=x.se;i++)a[++ax]=i;
            }
            for(res i=1;i<ax;i++)print(a[i]),sr[++C]=' ';
            print(a[ax]);
            sr[++C]='\n';
        }
    }
}

[1004 Pty hates prime numbers]

solution

题面：给定，求，其中表示第个质数。

做法：直接暴力容斥是不允许通过的，可以考虑一些适当的预处理。

注意到不是的倍数意味着不是的倍数，于是的贡献就是 $的答案$ 。于是就可以预处理出前几个质数，后面的直接暴搜即可。时间复杂度。

//2021.9.17 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int prim[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
const int N=30030;
const int K=16;
namespace MAIN{
    int a[N+1];
    Pair st[1<<K|10];
    int top;
    int bc[1<<K|10];
    inline void MAIN(){
        for(res i=1,sz=1<<K;i<sz;i++)bc[i]=bc[i>>1]^(i&1);
        for(res i=1;i<=N;i++)a[i]=a[i-1]+(__gcd(i,N)==1);
        res Case=read();
        while(Case--){
            RG LL _=Read();
            res k=read();
            if(k<=6){
                st[top=1]=mp(_,0);
                RG LL ans=0;
                while(top){
                    RG LL n=st[top].fi;
                    res i=st[top].se;
                    top--,bc[i]?ans-=n:ans+=n;
                    for(res j=0;j<k&&!((i>>j)&1);j++)if(n>=prim[j])st[++top]=mp(n/prim[j],i|(1<<j));
                }
                printf("%lld\n",ans);
            }
            else {
                st[top=1]=mp(_,0);
                RG LL ans=0;
                while(top){
                    RG LL n=st[top].fi;
                    res i=st[top].se;
                    top--,bc[i]?ans-=n/N*a[N]+a[n%N]:ans+=n/N*a[N]+a[n%N];
                    for(res j=6;j<k&&!((i>>j)&1);j++)if(n>=prim[j])st[++top]=mp(n/prim[j],i|(1<<j));
                }
                printf("%lld\n",ans);
            }
        }
    }
}

[1005 Pty loves book]

solution

题面：

做法：

[1006 Pty loves lcm]

solution

题面：

做法：

[1007 Pty loves graph]

solution

题面：

做法：

[1008 Pty loves string]

solution

题面：给出串，多次询问，问在中的出现次数。

做法：考虑一个合法的串满足。发现等价于询问正反串的树上某个节点的子树里有多少个编号相等的点，即

$\mathrm{dfn}_x\leq \mathrm{dfn_z}\leq \mathrm{low}_x\\\\ \mathrm{dfn'}_y\leq \mathrm{dfn'_z}\leq \mathrm{low'}_y$

可持久化线段树即可，时间复杂度。

//2021.10.19 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n,q;
    char str[N];
    int fa[N],Fa[N];
    vector<int> G[N],E[N];
    int rt[N],ls[N*30],rs[N*30],sum[N*30];
    int dfn[N],low[N],idx,pos[N];
    void dfs(res x){
        pos[dfn[x]=++idx]=x;
        for(auto tox:G[x])dfs(tox);
        low[x]=idx;
    }
    int Dfn[N],Low[N];
    void Dfs(res x){
        Dfn[x]=++idx;
        for(auto tox:E[x])Dfs(tox);
        Low[x]=idx;
    }
    int tot;
    void insert(res &rt,res RT,res l,res r,const res &p){
        rt=++tot,ls[rt]=ls[RT],rs[rt]=rs[RT],sum[rt]=sum[RT]+1;
        if(l==r){sum[rt]=sum[RT]+1;return;}
        res mid=(l+r)>>1;
        if(p<=mid)insert(ls[rt],ls[RT],l,mid,p);
        else insert(rs[rt],rs[RT],mid+1,r,p);
    }
    int query(res rt,res RT,res l,res r,const res &L,const res &R){
        if(!RT)return 0;
        if(L<=l&&r<=R)return sum[RT]-sum[rt];
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query(ls[rt],ls[RT],l,mid,L,R);
        if(R>mid)ret+=query(rs[rt],rs[RT],mid+1,r,L,R);
        return ret;
    }
    inline void MAIN(){
        n=read(),q=read(),scanf("%s",str+1);
        for(res i=2;i<=n;i++){
            res now=fa[i-1];
            while(str[now+1]!=str[i]&&now)now=fa[now];
            fa[i]=now+(str[now+1]==str[i]);
        }
        Fa[n]=n+1;
        for(res i=n-1;i;i--){
            res now=Fa[i+1];
            while(str[now-1]!=str[i]&&now<=n)now=Fa[now];
            Fa[i]=now-(str[now-1]==str[i]);
        }
        for(res i=0;i<=n+1;i++)vector<int>().swap(G[i]),vector<int>().swap(E[i]),rt[i]=0;
        for(res i=1;i<=n;i++)G[fa[i]].pb(i),E[Fa[i]].pb(i);
        idx=0,dfs(0),idx=0,Dfs(n+1);
        for(res i=1;i<=tot;i++)ls[i]=rs[i]=sum[i]=0;
        tot=0;
        for(res i=1;i<=n+1;i++)insert(rt[i],rt[i-1],1,n+1,Dfn[pos[i]+1]);
        while(q--){
            res l=read(),r=n-read()+1;
            printf("%d\n",query(rt[dfn[l]-1],rt[low[l]],1,n+1,Dfn[r],Low[r]));
        }
    }
}