题目大意

戳我看题

字符集大小为 $m$,要求你构造一个最短的字符串,使得长度为 $n$的不同子串至少有 $K$个。

题目分析

原来我不会欧拉路.avi

思路很简单,首先,将任意长度为 $n-1$的子串看做节点,每个节点连 $m$条边出去到新的节点。可以证明(但没必要),原图存在一条欧拉回路。于是我们可以让字符串的任意长度为 $n$的子串都不相同,构造出的字符串长度就为 $n+K-1$。

但是图会非常大,我们不可能真的把这条欧拉回路找出来。

首先显然,如果我当前 dfs 的深度大于等于 $K$,那么已经出现了一条在图中走 $K$条边的路径,可以直接将该路径作为答案输出。

如果求欧拉路算法中的答案栈里面的边也有 $K$条了,也可以将他们作为答案输出了。

愚蠢的 litble 纠结了一上午为什么答案栈里面直接输出就行了,这充分说明了 litble 压根就不会欧拉路。因为 dfs 的过程是,若有能继续走的边,则一定继续走而不会返回,那么若将原图所有不再答案栈里面的边删除,每个点的出度也一定等于入度,答案边也一定构成了欧拉回路。所以这是没有问题的!

然后就是判断边有没有走过的问题了,虽然可以哈希,但效率更高的做法是,若原图中有 $2^{40}$以上的边,随机走走出合法路径的概率极大,所以就直接走。否则,用一个 long long 就可以完成哈希了。

由于我 dfs 的每一步操作,要么新走一个点让深度+1,要么回溯一下,深度-1 但答案栈里面的元素+1,所以复杂度是 $O(k)$的。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
const LL lim=1099511627776LL;
int n,m,K,top1,top2,dig[12],st1[200005],st2[200005];LL orzxzy;
map<LL,int> mp;

void print0() {for(RI i=1;i<=K+n-1;++i) printf("%d",dig[rand()%m]);}
void print1() {
    for(RI i=1;i<=n-1;++i) printf("%d",dig[0]);
    for(RI i=1;i<=K;++i) printf("%d",dig[st1[i]]);
}
void print2() {
    for(RI i=1;i<=n-1;++i) printf("%d",dig[0]);
    for(RI i=top2;i>=top2-K+1;--i) printf("%d",dig[st2[i]]);
}
void dfs(LL x) {
    if(top1>=K) {print1();exit(0);}
    for(RI i=0;i<m;++i) {
        LL kl=x*(LL)m+(LL)i;
        if(!mp[kl]) {
            mp[kl]=1,st1[++top1]=i;
            dfs(kl%orzxzy),--top1,st2[++top2]=i;
            if(top2>=K) {print2();exit(0);}
        }
    }
}
int main()
{
    srand(19260817);
    scanf("%d%d%d",&n,&m,&K);
    for(RI i=0;i<m;++i) scanf("%d",&dig[i]);
    LL orzabs=1;
    for(RI i=1;i<=n;++i) {
        orzabs*=(LL)m;
        if(orzabs>=lim) {print0();return 0;}
    }
    orzxzy=1;for(RI i=1;i<=n-1;++i) orzxzy*=(LL)m;
    dfs(0);
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

2 条评论

Remmina · 2019年1月14日 2:41 下午

嗯嗯,你成功抢了我新域名第一篇文章 🔪🔪🔪

发表评论

电子邮件地址不会被公开。 必填项已用*标注