[The 14th Beihang University Collegiate Programming Contest Onsite B]zzh与子序列

这场比赛,虽然签到失败,但是怼出来了这道稍微有点水平的题,也算还行吧。

Problem

给定数组,问字典序第k大的子序列是谁并输出,n\le 5000

Solution

这种题必定是从高到低一位位确定,具体的比较类似在值域线段树上找第k大的值。
对于这道题,主要的思路就是考虑每个位置被多少个前缀覆盖着。假如已经确定了一个前缀,位置ix个前缀覆盖着,那么位置i就会对下一位填a[i]的方案方案数产生2^{n-i}的贡献。
注意,我的写法将下一位为空视作为0,和其它的字符等同处理。下一位为空的总方案数就是已有的前缀个数。
统计前缀对后面位置的覆盖用差分做就好了。

Code

const int XN=5e3+11;
const long long INF=1e18;

long long Mul(long long const &a,long long const &b) {
    return (long double)a*(long double)b<INF?a*b:INF;
}

void Work() {
    static int a[XN];
    int n,m;long long k;
    std::cin>>n>>m>>k;
    ++k;
    static long long cnt[XN],pw2[XN]={1};
    for(int i=1;i<=n;++i) {
        std::cin>>a[i];
        cnt[i]=1;
        pw2[i]=Mul(pw2[i-1],2);
    }
    static long long sum[XN];
    std::vector<int> Ans;
    sum[0]=1;
    for(int b=1;b<=n;++b) {
        for(int i=1;i<=m;++i)
            sum[i]=0;
        for(int i=1;i<=n;++i)
            Reduce(sum[a[i]]+=Mul(cnt[i],pw2[n-i]),INF);
        int v=0;
        while(k>sum[v])
            k-=sum[v++];
        if(v)
            Ans.push_back(v);
        else
            break;
        sum[0]=0;
        if(a[n]==v)
            sum[0]+=cnt[n];
        for(int i=n;i>=1;--i)
            sum[0]+=(cnt[i]=a[i-1]==v?cnt[i-1]:0);
        for(int i=1;i<=n;++i)
            Reduce(cnt[i]+=cnt[i-1],INF);
    }
    for(size_t i=0;i<Ans.size();++i)
        std::cout<<Ans[i]<<(i==Ans.size()-1?'\n':' ');
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

[hdu6223][Shenyang Onsite 2017]Infinite Fraction Path

Link

每个点有一个出边,每个点上有一个字符。求字典序最大的长度为n的路径。

Solution

广义后缀数组!预处理一下一个点往后跳2^i步到的点,然后魔改一下后缀数组就好了。

Code

const int XN=150000+11,XLOGN=18;

int par[XN][XLOGN];
char v[XN];
void Work() {
    int n;fin>>n>>(v+1);
    for(int i=1;i<=n;++i)
        par[i][0]=((long long)(i-1)*(i-1)+1)%n+1;
    for(int b=1;(1<<b)<=n;++b)
        for(int i=1;i<=n;++i)
            par[i][b]=par[par[i][b-1]][b-1];
    static int temp[2][XN],cnt[XN],*x=temp[0],*y=temp[1],sa[XN];
    int m=256;
    std::fill(cnt+1,cnt+1+m,0);
    for(int i=1;i<=n;++i)
        cnt[x[i]=v[i]]++;
    std::partial_sum(cnt+1,cnt+1+m,cnt+1);
    for(int i=1;i<=n;++i)
        sa[cnt[x[i]]--]=i;
    for(int b=0;(1<<b)<n;++b) {
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[par[i][b]]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=1;i<=n;++i)
            y[cnt[x[par[i][b]]]--]=i;
        std::fill(cnt+1,cnt+1+m,0);
        for(int i=1;i<=n;++i)
            cnt[x[i]]++;
        std::partial_sum(cnt+1,cnt+1+m,cnt+1);
        for(int i=n;i>=1;--i)
            sa[cnt[x[y[i]]]--]=y[i];
        std::swap(x,y);
        int p=x[sa[1]]=1;
        for(int i=2;i<=n;++i)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[par[sa[i-1]][b]]==y[par[sa[i]][b]]?p:++p;
        if((m=p)==n)
            break;
    }

    for(int i=1,p=sa[n];i<=n;++i,p=par[p][0])
        fout<<v[p];
    fout<<'\n';
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        Work();
    }
    return 0;
}