给定c个小写字母,再给出一个长度l,要求构造一个字符串,
使得这个字符串包含所有由c个字母构成的长度为l的字符串,且这个字符串的长度最短。
首先先考虑长度,
如何构造可以使得长度最短,
设想一种最优的方案,新增的每一个串都与前面的那一个串有l-1个公共的,
这样最终长度就是
可是在上面条件下才会出现这种最优情况?
我们将每个字符串看成一个点,
那么每个点都可以向外连出c条边,
最终就是求一条欧拉回路。
其实这里并不需要将所有点和边都建出来,
将一个字符串压成一个数就可以了。
#include#include #include #include #include #include #include #include #include #define ll long long #define N 1024*1024*12 #define M 103 #define db double #define P putchar #define G getchar #define inf 998244353 #define pi 3.1415926535897932384626433832795 using namespace std; char ch; void read(int &n) { n=0; ch=G(); while((ch<'0' || ch>'9') && ch!='-')ch=G(); ll w=1; if(ch=='-')w=-1,ch=G(); while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G(); n*=w; } int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a9) write(x/10);P(x%10+'0');} char s[30]; int c,l,top,m,tot,z[N]; short int cnt[N],p[N],ans[N]; int ksm(int x,int y) { int s=1; for(;y;y>>=1,x=x*x) if(y&1)s=s*x; return s; } void work() { int x,to; z[top=1]=0; for(;top;) { x=z[top]; if(cnt[x] 1)ans[++tot]=p[top--]; else break; } } int main() { freopen("life.in","r",stdin); freopen("life.out","w",stdout); read(c);read(l); for(ch=G();ch<'a' || ch>'z';ch=G());s[1]=ch; for(register int i=2;i<=c;i++)s[i]=G(); write(ksm(c,l)+l-1);P('\n'); if(l==1) { for(register int i=1;i<=c;i++)P(s[i]); return 0; } m=ksm(c,l-2); for(register int i=1;i