目录
题目 1 ：
九数算式_dfs+回溯(全排列)
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
观察如下的算式：
9213×85674=789314562
左边的乘数和被乘数正好用到了 1 ~ 9 的所有数字，每个 1 次。 而乘积恰好也是用到了 1 ~ 9 的所有数字，并且每个 1 次。
请你借助计算机的强大计算能力，找出满足如上要求的 9 数算式一共有多少个？
注意：
- 总数目包含题目给出的那个示例。
- 乘数和被乘数交换后作为同一方案来看待。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
代码：
package 第十四届蓝桥杯三月真题刷题训练.day4;
import java.io.*;
import java.util.HashSet;
/**
* @author yx
* @date 2023-03-07 13:13
*/
public class 九数算式_dfs全排列 {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
static int ans=0;
static int N=9;//数组长度
static int[] nums = {1,2,3,4,5,6,7,8,9};//数组定义成全局变量
public static void main(String[] args) throws IOException {
dfs(0,8);
System.out.println(ans);
}
//from是数组交换位置的头指针（依次会+1）,to是尾指针相当于哨兵的作用，当from==to的时候退出
static void dfs(int from ,int to){
if(from==to){ //递归的出口
countAns();
}else {
for (int i = from; i <= to ; i++) {
swap(from,i);
dfs(from+1,to);
//回溯恢复
swap(from,i);
}
}
}
static void swap(int a,int b){
int temp=nums[a];
nums[a]=nums[b];
nums[b]=temp;
}
static boolean isTrue(int n){
int[] count=new int[10];
int temp=0;
while (n!=0){
temp=n%10;
count[temp]++;
n=n/10;
}
for (int i = 1; i <= 9; i++) {
if(count[i]>1||count[i]==0){
return false;
}
}
return true;
}
static void countAns(){
int a;
int b;
StringBuilder s=new StringBuilder("");
for (int i = 0; i < N; i++) {
s.append(nums[i]);
}
String ss=s.toString();
int l=1;
while (l<=N/2) {
a=Integer.parseInt(ss.substring(0,l));
b=Integer.parseInt(ss.substring(l,N));
int temp=a*b;
if(isTrue(temp)){
ans++;
}
l++;
}
}
}
(这个题目调了好久,怪自己dfs生疏了)
全排列：
递归+回溯
贴一个讲的蛮不错的视频：
题目2：
完全平方数
问题描述
一个整数 a 是一个完全平方数, 是指它是某一个整数的平方, 即存在一个 整数 b, 使得 a=b2。
给定一个正整数 n, 请找到最小的正整数 x, 使得它们的乘积是一个完全平方数。
输入格式
输入一行包含一个正整数 n 。
输出格式
输出找到的最小的正整数 x 。
样例输入 1
12
样例输出 1
3
样例输入 2
15
样例输出 2
15
评测用例规模与约定
对于 3030 的评测用例, 1≤n≤10001≤n≤1000, 答案不超过 1000 。
对于 6060 的评测用例, 1≤n≤1081≤n≤108, 答案不超过 108108 。
对于所有评测用例, 1≤n≤10121≤n≤1012, 答案不超过 10121012 。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
代码：
package 第十四届蓝桥杯三月真题刷题训练.day4;
import java.io.*;
import java.util.Scanner;
/**
* @author yx
* @date 2023-03-07 15:25
*/
public class 完全平方数 {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*/
public static void main(String[] args) throws IOException {
Scanner scanner=new Scanner(System.in);
long n=scanner.nextLong();
long ans=n;
for (long i = 1; i <= Math.sqrt(n); i++) {
if(n%(i*i)==0){
ans=n/(i*i);
}
}
out.println(ans);
out.flush();
}
}