题目描述
传送门
题目大意:给出k,求一个最长的M位01串,使其从每一个位置向后走k个得到的M个k位01串互不相同(最后一个和第一个相邻,即是一个环)。输出字典序最小的答案。
题解
这道题实际上是将k-1位的二进制数看做点,k位的二进制数看成边,并且连接两个点的边就是将这两个点的权怼起来
像这样
然后每个点的入度和出度相等并且全部是偶点,是一个标准的欧拉图,所以只需要在这个图中找字典序最小的欧拉回路就行了
可以贪心地找字典序较小的边,然后实在不行了就回溯
这样的话时间复杂度我不大会…不过实测了一下是接近 O(n+m) 的吧
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 3000000int k,cnt,last[N],ans[N];
bool vis[N],flag;void find(int x,int y)
{ans[0]=0;while (x!=y){ans[++ans[0]]=x;x=last[x];}ans[++ans[0]]=y;
}
void dfs(int x)
{vis[x]=1;++cnt;if (cnt==(1<<k)){find(x,0);flag=1;return;}for (int i=0;i<=1&&!flag;++i){int vt=(x&((1<<(k-1))-1))<<1|i;if (vis[vt]) continue;last[vt]=x;dfs(vt);}vis[x]=0;--cnt;
}
int main()
{scanf("%d",&k);dfs(0);printf("%d ",ans[0]);for (int i=ans[0];i>=1;--i)putchar((ans[i]>>(k-1))+'0');puts("");
}