深度优先

这个家伙好懒，除了文章什么都没留下

0%

【算法】吉首大学第六届新星杯暨程序设计大赛-题解-Java

发表于 分类于
本文字数： 10k 阅读时长 ≈ 9 分钟

问题 A: 难题

时间限制: 1 Sec 内存限制: 128 MB
题目描述

C语言函数，数学函数，傻傻分不清楚~~

题目很简单，我们定义F（x）是满足x取余a乘b的积等于0（即：x%（a*b）==0）这样的a，b的组数。现在给你一个n，你需要求出 F（n）。

1=10 2=10*21

3=1031 4=1022 2*3

6=102131 222

16=1024 25

25=1052 23

比如说当n=4时，a b分别可以是——11、12、14、21、22、41，共6种情况，所以F（4） = 6。

输入

多组输入（不会超过200组）
每组测试数据输入一个整数n （1 <= n <= 10^11）

输出

每组测试数据输出 Case x: y ，x 表示第x组测试数据，y表示F（n）的值，细节参考样例。

样例输入

1

2

3

4

样例输出

Case 1: 1

Case 2: 3

Case 3: 3

Case 4: 6

代码：（代码还存在问题，只能通过100*1000以内的数据）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Scanner;

public class A {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(true){
			int n=sc.nextInt();
			System.out.println("Case "+n+": "+getCase(n));	
		}
	}

	private static int getCase(int n) {
		int conut=0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n ; j++) {
				if(n%(i*j)==0){
					conut++;
					System.out.println(i+"...."+j);
				}
			}
		}
		return conut;
	}
}

问题 B: 我是难题

时间限制: 1 Sec 内存限制: 128 MB

题目描述

“回文”是指正读反读都能读通的句子，它是古今中外都有的一种修辞方式和文字游戏，如“我为人人，人人为我”等。在数学中也有这样一类数字有这样的特征，成为回文数

现在出题如下：

对于10进制数87：

STEP1：87+78 =165 STEP2：165+561 =726

STEP3：726+627 =1353 STEP4：1353+3531 =4884

上例用了4步得到回文数，在这里的一步是指进行了一次N进制的加法

写一个程序，给定一个N（2<=N<=10）进制数 , M(小于1000位数)，求最少经过几步可以得到回文数。

如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”

输入

N和M

输出

步数

样例输入

9

87

样例输出

STEP=6

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Scanner;

public class B {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int k=sc.nextInt();
		String num=sc.nextInt()+"";

		boolean fa=getBool(num);

		int conut=0;
		while(fa==false){
			String str=getAdd(k,num);
			num=str;
			fa=getBool(str);
			conut++;
			System.out.println(num);
		}
		System.out.println("STEP="+conut);
	}
	private static boolean getBool(String str) {
		int le=str.length();
		for (int i = 0; i < le/2; i++) {
			if(str.charAt(i)!=str.charAt(le-i-1)){
				return false;
			}
		}
		return true;
	}
	//K进制的加法
	private static String getAdd(int k,String num) {
		String str="";
		int jw=0;
		int le=num.length()-1;
		for (int i = num.length()-1; i >= 0; i--) {
			int x=(num.charAt(i)+num.charAt(le-i))-2*'0'+jw;
			str=x%k+str;
			jw=x/k;
		}
		if(jw==1)
			str=1+str;
		return str;
	}
}

问题 C: 我才是难题

时间限制: 1 Sec 内存限制: 128 MB

题目描述

话说，小C经过上次被小T实力坑了一把以后呀，他就决定发明一个数字游戏来坑一坑小T！游戏规则是这样~

在游戏开始前，小C会任意的选出一个正整数n（1≤n≤2^32-1），同时令m=1。在玩的过程当中，小C和小T每个人都可以将m的值扩大2到9中的任意倍数（倍数一定是整数），两个人一人扩大一次，第一个使m≥n的人就是最后的赢家。

因为两个人都在互相算计，所以都是用的最佳策略，问最后是谁赢？

（上次因为吃了先手的亏，小C决定先手，也就是说：每次都是小C第一个玩）。

1

2~9 C

10~18 T

19~36

输入

多组输入（文件尾结束）

每行一个正整数n

输出

对于每个结果：

如果小C赢，则输出”C”，

如果小T赢，则输出”T”。

（记得换行！！）

样例输入

9

样例输出

C

提示

别说学长坑你们，给你们一点提示： ** **找规律！！

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;

public class C {

	public static void main(String[] args) {
		
		double[] arr=new double[18];

		//划分赢的区间
		arr[0]=2;
		arr[1]=9;
		for (int i = 2; i < arr.length; i+=2) {
			arr[i]=arr[i-1]*2+1;//2 2*9+1  18*2*9+1
			arr[i+1]=(arr[i]-1)*9;//2*9*9 18*9*2*9
		}
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		for (int i = 0; i < arr.length; i+=2) {
			if(n==1||(arr[i]<=n && arr[i+1]>=n)){
				System.out.println("C");
				return;
			}else if(arr[i+1]<n && arr[i+2]>n){
				System.out.println("T");
				return;
			}
		}
	}
}

问题 D: 楼上都是骗人的

时间限制: 1 Sec 内存限制: 128 MB

题目描述

有小明和小曹两个无聊的人，对字符串操作起了兴趣，小曹给出一个由小写字母构成的字符串，小明给出另一个比小曹更长的字符串，也由小写字母组成，如果能通过魔法转换使小明的串和小曹的变成同一个，那么他们两个人都会很开心。这里魔法指的是小明的串可以任意删掉某个字符，或者把某些字符对照字符变化表变化。如：
小曹的串是 abba;
小明的串是 addba;
字符变化表 d b （表示d能转换成b）。
那么小明可以通过删掉第一个d，然后将第二个d转换成b将串变成abba。
现在请你帮忙判断：他们能不能通过魔法转换使两个人的串变成一样呢？

输入

首先输入T，表示总共有T组测试数据(T <= 40)。
接下来共T组数据，每组数据第一行输入小曹的字符串，第二行输入小明的字符串（数据保证字符串长度不超过1000，小明的串的长度大于等于小曹的，且所有字符均为小写字母）。接着输入字母表，先输入m，表示有m个字符变换方式（m< = 100），接着m行每行输入两个小写字母，表示前一个可以变为后一个（但并不代表后一个能变成前一个）。

输出

对于每组数据，先输出Case数。
如果可以通过魔法转换使两个人的串变成一样，输出“happy”，
否则输出“unhappy”。
每组数据占一行，具体输出格式参见样例。

样例输入

2

abba

addba

1

d b

a

dd

0

样例输出

Case #1:happy

Case #2: unhappy 代码：（没做出来，先占坑位）

问题 E: 真·难题

时间限制: 0Sec 内存限制: 128 MB

题目描述

上了大学的小明又在做题了，他好累，所以请你帮忙：

设n为正整数，令f(n)为所有gcd(x,y)的最大值，且x和y满足1<=x<y<=n，其中gcd指最大公约数。

举个例子：当n=3时，x,y可以取1,2或1,3或2,3，gcd(x,y)的最大值为1，因此f(3)=1。

给定正整数n，求当2<=i<=2*n+1时，所有f(i)的平方和。

输入

多组输入，最多100组

每组一个正整数 n < 10^9.

输出

仅一行，所求结果对10007取模的结果。

样例输入

3

样例输出

28 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class E {

	public static void main(String[] args) {
		
		int n=2;//1652087318
		double sum=0;
		int x=0;
		for (int i = 2; i <= 2*n+1; i++) {
			x=(i/2%10007);
			sum+=(x*x%10007);
		}
		System.out.println((int)sum%10007);
	}
}

问题 F: 还有比我更难的题？

时间限制: 1 Sec 内存限制: 128 MB

题目描述

拉丁方的定义： n个不同的符号（这里取1到n），在n*n的方阵中每个符号在每一行和每一列均只出现一次，那么我们称此方阵为n阶的拉丁方

求最小n阶拉丁方，最小拉丁方中每行所表示的十进制数最小

输入

多组输入，每组一个n ( n <= 12 )

输出

输出最小拉丁方，每组输出数据之间用一个换行隔开

样例输入

1

2

样例输出

1

1 2

2 1

代码：（看不懂啥意思）

问题 G: 反正楼下都是简单题

时间限制: 1 Sec 内存限制: 2 MB

题目描述

问题很简单，找出现了3*k-1次的数 ( **k > 0 )**

输入

输入一个 n 接下来就是n个数

确保有一个数出现了 3k-1次，其余数都出现了3m 次 (m > 0 )

对于所有的数在int范围内，且n小于216660

输出

*找出现了3k-1次 **的那个数

样例输入

5

3 3 3 2 2

样例输出

2

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.Scanner;

public class G {

	public static void main(String[] args) {
		
		int[] arr=new int[32];
		Scanner sc=new Scanner(System.in);
		int c=sc.nextInt();
		for (int j = 0; j < c; j++) {
			String str=getRE(sc.nextInt());
			for (int i = str.length()-1,k=arr.length-1; i >= 0; i--,k--) {
				arr[k]+=str.charAt(i)-'0';
				if(arr[k]==3)//满3清零
					arr[k]=0;
			}	
		}
		
		//将二进制转成十进制
		int sum=0;
		for (int i = 0,k=arr.length-1; i < arr.length; i++,k--) {
			sum+=arr[k]*(int)Math.pow(2,i);
		}
		System.out.println(sum/2);
	}
	
	//转二进制
	private static String getRE(int i) {
		String str="";
		while(i>0){
			str=i%2+str;
			i=i/2;
		}
		return str;
	}
}

问题 H: 听说有人说我是简单题？

时间限制: 1 Sec 内存限制: 3 MB

题目描述

小C和小T骑车去郊游，小T先出发，速度为x米每分钟，行驶m分钟后，小C带着一条狗出发，小C的速度为y米每分钟，而狗则以每分钟z米的速度向小T跑去，追上小T后又会返回，如此往复，直到小C追上小T。问：当小C追上小T的时候，狗跑了多远？

输入

第一行输入一个整数N，表示测试数据的组数(N<100)
每组测试数据占一行，是四个正整数，分别为m,x,y,z（数据保证X<Y<Z)

输出

输出狗跑的路径长度，结果保留小数点后两位。

样例输入

1

5 10 15 20

样例输出

200.00

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.math.BigDecimal;

public class H {

	public static void main(String[] args) {

		getLC(5,10,15,20);

	}

	private static void getLC(int m, int x, int y, int z) {
		
		int t=m*x/(y-x)*z;
		BigDecimal bd=new BigDecimal(t);
		String s=bd.setScale(2,BigDecimal.ROUND_HALF_UP).toString();
		System.out.println(s);
		
	}
}

问题 I: 不要吵了，我才是难题

时间限制: 1 Sec 内存限制: 128 MB

题目描述

小小成现在拥有n根火柴，假设小小成只能按照上图的方式用火柴摆数字，并且不能进行任何运算，而且必须

用完所有火柴棍，请问能摆出来的最大数字和次大数字是多少。

输入

多组输入（最多 2000 组）

每组数据仅一行，包含一个正整数 n 。

1 ≤ n≤2000

输出

对于每组数据输出一行，如果能摆出来的最大数字和次大数字都存在，则这一行包含两个非负整数，表示能摆出来的最大数字和次大数字

否则在这一行输出 small small cheng is silly boy

样例输入

5

1

样例输出

71 17

small small cheng is silly boy

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class I {
			//0,1,2,3,4,5,6,7,8,9
	static int[] arr={6,2,5,5,4,5,6,3,7,6};
	public static void main(String[] args) {
		int n=8;
		if(n<4){
			System.out.println("mall small cheng is silly boy");
			return;
		}
		if(n==4){
			System.out.println("11 4");
			return;
		}
		String str=getMax(n);
		System.out.print(str+" ");
		if(str.indexOf("7")!=-1){
			str="17"+str.substring(2);
		}else{
			str="77"+str.substring(3);
		}
		System.out.println(str);
	}
	private static String getMax(int i) {
		String str="";
		while(i/2>1){
			str=str+"1";
			i=i-2;
		}
		System.out.println(i);
		if(i==2){
			str=str+"1";
		}else if(i!=0){
			str="7"+str;
		}
		return str;
	}
}

问题 J: 我就静静的不说话

时间限制: 5 Sec 内存限制: 128 MB

题目描述

实验室除了是一个学习的地方，更是一个非常好玩的地方，有各种各样的活动充斥在学习之间。

在某一次活动中，黄sir带着大家一起去爬山。历经了千辛万苦后终于爬上了山顶，大家是又累又渴。。但是在山顶，只有一口井，每次只能容下一个人去打水。那么问题来了！

现在假设实验室有n个人，每个人打水的时间为ai，请给出一个排队的规则，使所有人的平均等待时间最小！

注意：若两个人的等待时间相同，则序号小的优先。

输入

多组输入

每组两行

第一行为n，表示有多少个人

第二行有n个数，分别表示每个人打水的时间a[1],a[2],a[3],a[4],……a[n]，每个数据之间有一个空格

数据范围: 0<n<=1000, 0<a[i]<=1000

输出

对于每组输入

输出有两行（格式见样例）

第一行为使所有人的平均等待时间最小的排队顺序

第二行为最小的平均等待时间（输出结果精确到小数点后两位）

样例输入

10

56 12 1 99 1000 234 33 55 99 812

样例输出

3 2 7 8 1 4 9 6 10 5

291.90

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.math.BigDecimal;
import java.util.Scanner;

public class J {

	public static void main(String[] args) {
		
		//java.text.DecimalFormat df =new java.text.DecimalFormat("#.00");  
		//System.out.println(df.format(235.005));
//		double sum1=523.200;
//		BigDecimal d=new BigDecimal(sum1);
//		String ss=d.setScale(2,BigDecimal.ROUND_HALF_UP).toString();
//		System.out.println(ss);
//		try {
//			double num=544.000;
//			String s=num+"000";
//			int a=s.indexOf(".");
//			int x=s.charAt(a+3)-'0';
//			int y=s.charAt(a+2)-'0';
//			if(x>4){
//				y=(y+1)%10;
//				num+=0.01;
//			}
//			s=(num+"").substring(0,a+2)+y;
//			System.out.println(s);
//		}catch (Exception e) {}
		
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] arr1=new int[n];
		int[] arr2=new int[n];
		double sum=0;
		for (int i = 0; i < arr2.length; i++) {
			arr1[i]=sc.nextInt();
			arr2[i]=i+1;
		}
		for (int i = 0; i < arr2.length; i++) {
			for (int j = 0; j < arr2.length; j++) {
				if(arr1[i]<arr1[j]){
					int tmep=arr1[i];
					arr1[i]=arr1[j];
					arr1[j]=tmep;
					
					int k=arr2[i];
					arr2[i]=arr2[j];
					arr2[j]=k;
				}
			}
		}
		for (int i = 1; i < arr1.length; i++) {
			sum+=arr1[i-1]*(n-i);
		}
		for (int i = 0; i < arr2.length; i++) {
			System.out.print(arr2[i]+" ");
		}
		System.out.println();
		sum=sum/n;
		BigDecimal d=new BigDecimal(sum);
		String s=d.setScale(2, BigDecimal.ROUND_HALF_UP).toString();
		System.out.println(s);
	}
}

问题 K: 冷漠.jpg

时间限制: 1 Sec 内存限制: 128 MB

题目描述

最近发现了一些神奇的数字，就是各个位都不相同的四位数，如1234 ，把所有数字从大到小排序后得到的数，减去从小到大得到的数，一直如此减下去，竟然一定会得到6174，那么你能求出要多少次这样的操作才能得到6174吗？

例如，从1234出发，依次可以得到4321-1234=3087、8730-378=8352、8532-2358=6174。这样就回到了6174。操作步数为3，所以输出3。

输入

第一行输入n,代表有n组测试数据。
接下来n行每行都写一个各位数字互不相同的四位数

输出

经过多少次上面描述的操作才能出现6174。

样例输入

1

1234

样例输出

3

提示

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Scanner;

public class K {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=Integer.parseInt(sc.nextLine());
		
		int[] arr=new int[n];
		for (int i = 0; i < arr.length; i++) {
			String str=sc.nextLine();
			int conut=0;
			while(!str.equals("6174")){
				str=getConut(str);
				conut++;
			}
			arr[i]=conut;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}

	private static String getConut(String nextInt) {
		String max="",min="";
		while (max.length()<nextInt.length()) {
			
			for (int i = 0; i < 10; i++) {
				if((nextInt).indexOf(""+i)!=-1){
					max=i+max;
					min=min+i;
				}
			}
		}
		int a=Integer.parseInt(max);
		int b=Integer.parseInt(min);
		return a-b+"";
	}
}

PS:有些代码可能还存在问题