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

程序开发人生的经验问题解析

2018-06-28 14:08:35         来源:lijf2001的博客  
收藏   我要投稿

程序开发人生的经验问题解析

这里写图片描述
这里写图片描述

题目大意

给定c个小写字母,再给出一个长度l,要求构造一个字符串,
使得这个字符串包含所有由c个字母构成的长度为l的字符串,且这个字符串的长度最短。

题解

首先先考虑长度,
如何构造可以使得长度最短,
设想一种最优的方案,新增的每一个串都与前面的那一个串有l-1个公共的,
这样最终长度就是cl+l1" role="presentation">cl+l?1
可是在上面条件下才会出现这种最优情况?

我们将每个字符串看成一个点,
那么每个点都可以向外连出c条边,
最终就是求一条欧拉回路。

其实这里并不需要将所有点和边都建出来,
将一个字符串压成一个数就可以了。

code

#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
上一篇:【基础练习习题】FJ的字符串
下一篇:Light It Up(思维)解析
相关文章
图文推荐
文章
推荐
热门新闻

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

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