文档章节

蓝桥杯-凑平方数

李韬_varyshare
 李韬_varyshare
发布于 2017/05/02 17:02
字数 841
阅读 943
收藏 0

 题目描述

 

 

凑平方数

把0~9这10个数字,分成多个组,每个组恰好是一个平方数,这是能够办到的。

比如:0, 36, 5948721

再比如:

1098524736

1, 25, 6390784

0, 4, 289, 15376

等等...

大家注意正确的答案是300,这是官方给的答案。

 思路

这道题思路很简单就是数据量大了,主要题意就是说让你把一个数字串分割,然后每个小分组都是平方数。

这道题可以从结果来推,先把10位以内所有平方数算出来当然要用到大整数不然会溢出。然后对这600多个数进行全排列,在排列过程中当然还要减支。

减支1:几个分组合在一起的字符串不能超过10个

减支2:剩下可用长度比当前选择的字符串长度还小后面就不用看了,因为我们生成平方数从小到大生成的,后面的数肯定比当前的大(这个减支不必须只是会大大降低时间),比当前数大也就意味着基本比当前数长很多。毕竟是平方肯定不会存在下个平方数比当前平方数还短的情况。

减支3:当前选的数不能和前面已经选的字符串有相同字符,这个题目有要求。

正确答案是:300

具体代码: 



import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class SelPow {
	//保存10位以内所有的平方数,方便进行全排列
	static ArrayList<BigInteger> digitlist;
    //在深度优先搜索过程中标记digitlist中数字是否被选
	public static boolean[] select;

	// 检查当前字符串是否有相同字符
	public static boolean check(String digitstr) {
		int len = digitstr.length();
		Set<Character> set = new HashSet<>();
		for (int i = 0; i < len; i++)
			set.add(digitstr.charAt(i));
		if (set.size() == len)
			return true;
		else
			return false;
	}

	// 保存所有的结果用集合去重,题目要求说生成的序列是无序的
	public static Set<Set<String>> result = new HashSet<>();

	//对所有的平方数排列
 //dfs(还剩多少待选数字,之前选好的合并的数字串(方便检查是否有重复数字), 之前选好的数字集合)
	public static void dfs(int len, String figure, Set<String> figureset) {
		if (len < 0)
			return;
		if (len == 0) {
			result.add(figureset);//满足条件加入到结果集合中
			return;
		}
// 填剩下的那len个数字,当然不只填一个数可以很多,但一次dfs只填一个剩下的交给下一次dfs
		for (int i = 0; i < select.length; i++) {
			if (!select[i]) {
				select[i] = true;
				String temp = digitlist.get(i).toString();
				//因为最先所有的平方数最先都是从小到大生成的后面的数肯定比当前的数要长因此后面就不用看了
				if (len < temp.length()) {
					select[i] = false;
					break;
				}
               //检查当前选的数字是否和以前选的有重复数字如果有则放弃这个,否则进行下一层dfs
				if (check(figure + temp)) {
					HashSet<String> tempset = new HashSet<>();
					tempset.addAll(figureset);
					tempset.add(temp);
					dfs(len - temp.length(), figure + temp, tempset);
				}
				select[i] = false;
			}
		}
	}

	public static void main(String[] args) {
		int i = 0;
		digitlist = new ArrayList<>();
		//由小到大生成平方数
		while (true) {
			BigInteger temp = BigInteger.valueOf(i++).pow(2);
			if (temp.toString().length() <= 10) {
				if (check(temp.toString()))
					digitlist.add(temp);
			} else
				break;
		}
		select = new boolean[digitlist.size()];
		
		dfs(10, "", new HashSet<String>());
         // 输出最终计算出的所有结果数目
		System.out.println(result.size());
	}
}

 

© 著作权归作者所有

李韬_varyshare

李韬_varyshare

粉丝 7
博文 27
码字总数 18588
作品 1
广州
个人站长
私信 提问
蓝桥杯,你怎么看???

蓝桥杯又要报名了,各位大boss们怎么看待蓝桥杯~~~

嘚瑟的小孩
2016/11/29
581
7
【蓝桥杯】2019第十届蓝桥杯B组C++年号字串

小明用字母A 对应数字1,B 对应2,以此类推,用Z 对应26。对于27 以上的数字,小明用两位或更长位的字符串来对应,例如AA 对应27,AB 对 应28,AZ 对应52,LQ 对应329。 请问2019 对应的字符...

Debug客栈
03/27
0
0
2016年蓝桥杯省赛C/C++ A组题解(含题目)

1. 网友年龄 某君新认识一网友。 当问及年龄时,他的网友说: “我的年龄是个2位数,我比儿子大27岁, 如果把我的年龄的两位数字交换位置,刚好就是我儿子的年龄” 请你计算:网友的年龄一共有...

woshirenno01
2017/03/13
0
0
蓝桥杯——Java基础(进制)

本文属xxKarina原创,转载请注明 个人博客地址: https://xxkarina.github.io/ 在前面的一篇Java基础博客中,不少人蛮喜欢的,这让我备受鼓舞,决定再出蓝桥——Java基础(续) 1.数列排序 ...

xxKarina
2017/12/11
0
0
历届试题 危险系数 (BFS暴力水过)

问题描述 抗日战争时期,冀中平原的地道战曾发挥重要作用。 地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。 我们来定...

akatsuki__itachi
2018/03/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分页查询

一、配置 /*** @author beth* @data 2019-10-14 20:01*/@Configurationpublic class MybatisPlusConfig { @Bean public PaginationInterceptor paginationInterceptor(){ ......

一个yuanbeth
19分钟前
2
0
在LINQPad中使用Ignite.NET

LINQPad是进行.NET开发的一款优秀工具,非常有利于Ignite.NET API的快速入门。 入门 下载LINQPad:linqpad.net/Download.aspx,注意要选择64位操作系统的AnyCPU版本; 安装Ignite.NET的NuGet...

李玉珏
32分钟前
2
0
JS其他类型值转化为Boolean类型规则

本文转载于:专业的前端网站➤JS其他类型值转化为Boolean类型规则 由于最近在笔试的时候,发现好多关于其他类型转化为Boolean类型的题目,因此总结一下! 一、String类型转化为Boolean 1.转化...

前端老手
43分钟前
4
0
EurekaClient自动装配及启动流程解析

在上篇文章中,我们简单介绍了EurekaServer自动装配及启动流程解析,本篇文章则继续研究EurekaClient的相关代码 老规矩,先看spring.factories文件,其中引入了一个配置类EurekaDiscoveryClie...

Java学习录
49分钟前
9
0
析构函数是否必须为虚函数?为何?

p517 在C++中,基类指针可以指向一个派生类的对象。如果基类的析构函数不是虚函数,当需要delete这个指向派生类的基类指针时,就只会调用基类的析构函数,而派生类的析构函数无法被调用。容易...

天王盖地虎626
50分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部