首页 > 其他分享 >UVa 129 Krypton Factor (回溯好题)

UVa 129 Krypton Factor (回溯好题)

时间:2023-04-12 11:36:32浏览次数:57  
标签:Krypton cur sequence int hard 好题 sequences 129 line


129 - Krypton Factor

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=65

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 sequence 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

Input and Output

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:


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 ABA7


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

Sample Input


30 30 0


Sample Output


ABAC ABCA CBAB CABA CABC ACBA CABA28



树型搜索。回溯之。

都写在注释里了。


完整代码:

/*0.015s*/

#include<cstdio>

int n, L, cnt;
int S[100];

int dfs(int cur)  // 返回0表示已经得到解,无须继续搜索
{
	if (cnt++ == n)
	{
		for (int i = 0; i < cur; i++)
		{
			if (i)
			{
				if (i % 64)
				{
					if (i % 4 == 0) putchar(' ');
				}
				else putchar(10);
			}
			putchar('A' + S[i]); // 输出方案
		}
		printf("\n%d\n", cur);
		return 0;
	}
	for (int i = 0; i < L; i++)
	{
		S[cur] = i;
		int ok = 1;
		for (int j = 1; j * 2 <= cur + 1; j++)  // 只算前一半
		{
			int equal = 1;
			for (int k = 0; k < j; k++)   // 检查后一半是否等于前一半
				if (S[cur - k] != S[cur - k - j])
				{
					equal = 0;
					break;
				}
			if (equal)
			{
				ok = 0;    // 后一半等于前一半,方案不合法
				break;
			}
		}
		if (ok && !dfs(cur + 1)) return 0; // 递归搜索。如果已经找到解,则直接退出
	}
	return 1;
}

int main()
{
	while (scanf("%d%d", &n, &L), n)
	{
		cnt = 0;
		dfs(0);
	}
	return 0;
}



标签:Krypton,cur,sequence,int,hard,好题,sequences,129,line
From: https://blog.51cto.com/u_5535544/6185335

相关文章

  • UVA - 129 Krypton Factor 回溯+剪枝
    题目大意:给出N种字母,要求用这N种字母组成一个困难的串,困难的串指在串中没有相连的两个子串相同,要求输出第M个困难的串解题思路:像八皇后一样,前面判断的就不需要再去判断了,直接往后判断即可#include<cstdio>#include<cstring>intn,L;intans[100];boolflag;intcnt;boolju......
  • 129. 颜色交替的最短路径
    题目链接:129.颜色交替的最短路径方法:BFS解题思路当边的权重为\(1\)时,可以使用\(BFS\)计算最短路径;因为起始边有两种情况,所以都需要计算,最后取两者的最小值;代码classSolution{public:vector<int>shortestAlternatingPaths(intn,vector<vector<int>>&redEd......
  • 202031607129-杨炜 实验一 软件工程准备—博客园技巧与博客首秀
    项目内容班级博客链接2023年春软件工程(2020级计算机科学与技术本次作业要求链接实验一软件工程准备我的课程学习目标注册博客园和Github账号,学习使用博客园,了解Github的基本操作。本次作业在哪些方面帮我实现学习目标按照实验内容,借助各种链接的例子,一步步......
  • 三菱FX3U,用ST语言与梯形图,混合编写的16仓位的配方程序,程序大小约12984步
    三菱FX3U,用ST语言与梯形图,混合编写的16仓位的配方程序,程序大小约12984步,可以配1到16种不同的产品,16种配方可以根据自己的需求随意设置配方数量与产品数量,可以用条形码设置配方数据与生产数量,也可以使用触摸屏手动设置,共使用了两台秤同时工作,一台秤配8个仓位的配料,使用FX3U485ADP走......
  • CF1295E Permutation Separation 题解 线段树优化dp
    题目链接:https://codeforces.com/problemset/problem/1295/E题目大意:将排列\(p_1,p_2,\ldots,p_n\)先分成\(p_1,\ldots,p_k\)与\(p_{k+1},\ldots,p_n\)两个......
  • bnuoj 12976 Collecting Gold 状压dp
    http://www.bnuoj.com/problem_show.php?pid=12976状态转移方程:dp[s|1<<j][j]=min(dp[s|1<<j][j],dp[s][i]+dis(i,j));code:#include<iostream>#include<stdio.h>#in......
  • Centos7-tar包自定义安装mysql -ERROR 2002_ERROR 1045_ERROR 1054_ERROR 1290_ERROR
    @目录1.自定义安装mysql参考链接ERROR2002/ERROR1045/ERROR1054/ERROR12901.1、ERROR2002报错解决方法:1.2、ERROR1045报错解决方法:2.关于登录mys......
  • “性能续航小超人”iQOO Z7系列登场:售价仅1299元起
    2023年3月20日,“性能续航小超人”iQOOZ7系列正式发布,带来同价位领先的闪充大电池体验,并具备出色的游戏性能体验以及全方位的功能配置,普及领先科技体验,带给对注重产品品质和......
  • N04、重建二叉树(给出前序中序,重建二叉树,好题 绝对的好题)
    ​​4、重建二叉树​​(给出前序中序,重建二叉树)好题绝对的好题输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重......
  • 第129篇:JS模块化开发
    好家伙,本篇为《JS高级程序设计》第二十六章“模块”学习笔记 JS开发会遇到代码量大和广泛使用第三方库的问题。解决这个问题的方案通常需要把代码拆分成很多部分,然后......