频道栏目
首页 > 考试 > 其他 > 正文

模拟题人生的经验问题解析

2018-06-28 14:09:02         来源:HuangXinyue1017的博客  
收藏   我要投稿

模拟题人生的经验问题解析。

这里写图片描述

Input

这里写图片描述

Output

这里写图片描述

Sample Input

2 2
ab

Sample Output

5
abbaa
这里写图片描述

Data Constraint

这里写图片描述

Solution

构造答案

先考虑如何构造可以使得长度最短,
设想一种最优的方案,
每添加一个字符,
都可以与当前已构造完毕的字符串的后l1" role="presentation">l?1个构成一个新的长度为l的字符串,
那么最终长度就是cl+l1" role="presentation">cl+l?1

可是怎样才会出现这种最优情况呢?
我们将每个长度为l1" role="presentation">l?1的字符串看成一个点,
从一个字符串转换到另一个字符串只需要新增一个字符,
在转换的过程中我们考虑用c进制数表示每个字符串,
由于每个点都可以向外连出c条边,
最终就是问题转化为求一条欧拉回路。

Code

#include
#include
#include

#define N 1024*1024*10

using namespace std;

int c,l,k,top,b[30],d[N];
short int use[N],cnt[N],ans[N];
char s[30];

void solve()
{
 d[top=1]=0;
 while(top)
 {
  int x=d[top];
  if(cnt[x]1) ans[++k]=use[top--]; else break;
 }
}

int main()
{
 freopen("life.in","r",stdin);
 freopen("life.out","w",stdout);
 scanf("%d%d",&c,&l);
 scanf("%s",s);
 b[0]=1;
 for(int i=1;i<=l;i++) b[i]=b[i-1]*c;
 printf("%d\n",b[l]+l-1);
 if(l==1)
 {
  printf("%s",s);
  return 0;
 }
 for(int i=1;i
上一篇:程序开发数字分类问题解析
下一篇:贪心 : Integer Intervals
相关文章
图文推荐
热门新闻

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站