Wuyanru's blog
0%

[QOJ5434] Binary Substrings

发表于 分类于 ，

神秘的构造。

题目链接。

题意

给定 ，构造一个长度为 的，本质不同子串个数最多的 串。

。

题解

首先能猜到答案的上界应该是 。

考虑如何达到这个上界，令 为最大的 满足 。

先考虑 的情况，此时只需要让所有长度为 的子串互不相同。

考虑建一张 个点的图，点的编号为 ，对于每一个点有边 和 。

此时一条边对应一个长度为 的 串，在这张图上跑欧拉回路即可。

这样就解决了 的情况。

对于剩下的情况，可以发现，再建出一张 个图，上面的做法正好也跑出了这张图的一个哈密顿路。

此时我们要在这张图的基础上，再走 条边，并且满足没有边被走过两次。

考虑这张图去掉这条哈密顿路剩下的边，一定是若干个环和一条路径（哈密顿路终点对应的连通块）。

考虑初始的时候采用随机化走边，使得最后剩下的所有连通块里，路径的长度最长。

然后随便贪一下。大概就是能走环的话就先走环，然后最后走路径的一段前缀。

时间复杂度 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
mt19937 _rand(time(0)^clock());
int fa[300001],siz[300001];
bool go[300001];
int to[300001][2];
char s[300001];
int n,k,c,cnt;
void dfs(int num,int k)
{
    int lim=(1<<k)-1;
    int fir=_rand()%2;
    if(!to[num][fir])
    {
        to[num][fir]=1;
        dfs((num<<1|fir)&lim,k);
        s[c--]=fir+'0';
    }
    fir^=1;
    if(!to[num][fir])
    {
        to[num][fir]=1;
        dfs((num<<1|fir)&lim,k);
        s[c--]=fir+'0';
    }
}
inline int run(int p)
{
    c=(2<<p)+p;
    memset(s,'0',sizeof(s));s[c+1]=0;
    memset(to,0,sizeof(to));
    dfs(0,p);

    memset(to,0,sizeof(to));
    int lim=(1<<(p+1))-1,lst=0,now=0;
    for(int i=1;i<=(2<<p)+p;i++)
    {
        now=((now<<1)+s[i]-'0')&lim;
        if(i>k) to[lst][s[i]-'0']=1;
        lst=now;
    }
    return lst;
}
inline void run(int &num,int now)
{
    int mem=now;
    do
    {
        for(int i=0;i<2;i++) if(!to[now][i])
        {
            s[num++]=i+'0';
            now=(now<<1|i)&((1<<k)-1);
            break;
        }
    }while(now!=mem);
}
void output(int num,int now)
{
    if(num==n+1)
    {
        s[n+1]=0;printf("%s\n",s+1);
        exit(0);
    }
    if(go[now]) run(num,now);
    if(num>n) return ;

    for(int i=0;i<2;i++) if(to[now][i]==1)
    {
        to[now][i]=2;s[num]=i+'0';
        output(num+1,(now<<1|i)&((1<<k)-1));
        to[now][i]=1;
    }
    for(int i=0;i<2;i++) if(to[now][i]==0)
    {
        to[now][i]=2;s[num]=i+'0';
        output(num+1,(now<<1|i)&((1<<k)-1));
        to[now][i]=0;
    }
}
inline int find(int num)
{
    if(fa[num]==num) return num;
    return fa[num]=find(fa[num]);
}
inline void merge(int u,int v)
{
    u=find(u),v=find(v);
    if(u==v) return ;
    fa[u]=v,siz[v]+=siz[u];
}
int main()
{
    n=read();
    if(n==1){ printf("0\n");return 0;}
    while(n>=(1<<(k+1))+k) k++;
    // printf("k=%d\n",k);

    while(true)
    {
        cnt++;
        int ma=(1<<k)-1,o=run(k-1);
        for(int i=0;i<=ma;i++) siz[i]=0,fa[i]=i;
        for(int i=0;i<=ma;i++) for(int j=0;j<2;j++) if(!to[i][j])
        {
            int t=(i<<1|j)&ma;
            merge(i,t),siz[find(i)]++;
        }
        int S=0;
        for(int i=0;i<ma;i++) if(find(i)==i) S=max(S,siz[i]);
        if(S!=siz[find(o)]) continue;

        int now=(1<<k)+k-1,need=n-now;
        vc<int>id;for(int i=0;i<=ma;i++) if(find(i)==i&&i!=find(o)) id.push_back(i);
        sort(id.begin(),id.end(),[](int x,int y){ return siz[x]<siz[y];});
        for(int i:id) if(need>=siz[i]) need-=siz[i],go[i]=1;

        int St=0;
        for(int i=1;i<=k;i++) St=(St<<1)|(s[i]-'0');
        output(k+1,St);
        assert(0);
    }
    return 0;
}