首页 > 搜索 > DFS搜索 > HDU 1627 Krypton Factor-字符串-[解题报告] C++
2013
12-16

HDU 1627 Krypton Factor-字符串-[解题报告] C++

Krypton Factor

问题描述 :

You have been employed by the organisers of a Super Krypton Factor Contest in which contestants have very high mental and physical abilities. In one section of the contest the contestants are tested on their ability to recall a sequenace of characters which has been read to them by the Quiz Master. Many of the contestants are very good at recognising patterns. Therefore, in order to add some difficulty to this test, the organisers have decided that sequences containing certain types of repeated subsequences should not be used. However, they do not wish to remove all subsequences that are repeated, since in that case no single character could be repeated. This in itself would make the problem too easy for the contestants. Instead it is decided to eliminate all sequences containing an occurrence of two adjoining identical subsequences. Sequences containing such an occurrence will be called “easy”. Other sequences will be called “hard”.

For example, the sequence ABACBCBAD is easy, since it contains an adjoining repetition of the subsequence CB. Other examples of easy sequences are:

BB
ABCDACABCAB
ABCDABCD

Some examples of hard sequences are:

D
DC
ABDAB
CBABCBA

输入:

In order to provide the Quiz Master with a potentially unlimited source of questions you are asked to write a program that will read input lines that contain integers n and L (in that order), where n > 0 and L is in the range , and for each input line prints out the nth hard sequence (composed of letters drawn from the first L letters in the alphabet), in increasing alphabetical order (alphabetical ordering here corresponds to the normal ordering encountered in a dictionary), followed (on the next line) by the length of that sequence. The first sequence in this ordering is A. You may assume that for given n and L there do exist at least n hard sequences.

For example, with L = 3, the first 7 hard sequences are:

A
AB
ABA
ABAC
ABACA
ABACAB
ABACABA
As each sequence is potentially very long, split it into groups of four (4) characters separated by a space. If there are more than 16 such groups, please start a new line for the 17th group.

Therefore, if the integers 7 and 3 appear on an input line, the output lines produced should be

ABAC ABA
7
Input is terminated by a line containing two zeroes. Your program may assume a maximum sequence length of 80.

样例输入:

30 3
0 0

样例输出:

ABAC ABCA CBAB CABA CABC ACBA CABA
28

这个题呢其实不难,要求求出用前m个字母组成的第n个不含有连续的重复序列的字符串

用DFS类似八皇后问题做,需要注意的是我每隔4个需要有一个空格,每行只能输出80个,由于存在空格,所以我直接对64取余判断即可

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=10001;
int n,m,ans[maxn];
void DFS(int cur)
{
    for(int i=0;i<m;i++)
    {
	ans[cur]=i;
	bool is=false;
	for(int j=1;2*j<=cur+1;j++)
	{
	    bool flag=0;
	    for(int k=0;k<j;k++)
		if(ans[cur-j-k]!=ans[cur-k])
		{
		    flag=1;
		    break;
		}
	    if(!flag)
	    {
		is=true;
		break;
	    }
	}
	if(is)
	    continue;
	if(--n==0)
	{
	    for(int i=0;i<=cur;i++)
	    {
		if(i&&i%64==0)
		    printf("\n");
		else if(i&&i%4==0)
		    printf(" ");
		printf("%c",'A'+ans[i]);
	    }
	    printf("\n%d\n",cur+1);
	    return;
	}
	DFS(cur+1);
	if(!n)
	    return;
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
	DFS(0);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/z309241990/article/details/10996715


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  3. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。