深度优先

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

0%

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

算法训练 s01串

时间限制：1.0s 内存限制：256.0MB

问题描述

s01串初始为”0”
按以下方式变换
0变1，1变01

输入格式

1个整数(0~19)

输出格式

n次变换后s01串

样例输入

3

样例输出

101

数据规模和约定

0~19

起初还没明白这个题的意思，后来突然明白，就是每次将0换成1、把1换成01.

代码：

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 Main {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			String s="0";
			for (int i = 1; i <=n; i++) {
				String r="";
				for (int j = 0; j < s.length(); j++) {
					r+=getStr(s.charAt(j));
				}
				s=r;
			}
			System.out.println(s);
		}
	}

	private static String getStr(char c) {
		
		if(c=='0')
			return "1";
		return "01";
	}
}

算法训练 水仙花

时间限制：1.0s 内存限制：256.0MB

水仙花数

问题描述

判断给定的三位数是否 水仙花 数。所谓 水仙花 数是指其值等于它本身 每位数字立方和的数。例 153 就是一个 水仙花 数。 153=13+53+33

输入格式

一个整数。

输出格式

是水仙花数,输出”YES”,否则输出”NO”(不包括引号)

样例输入

123

样例输出

NO

数据规模和约定

一个三位的整数,否则输出”NO”

又是这种题，额。还是贴出来吧。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int a=n/100;
		int b=n/10%10;
		int c=n%10;
		if(n==a*a*a+b*b*b+c*c*c)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
}

PS:这是前几天做的，一直忘了更新。

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

历届试题 数字游戏

时间限制：1.0s 内存限制：256.0MB

问题描述

栋栋正在和同学们玩一个数字游戏。

游戏的规则是这样的：栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数字1。接下来，坐在栋栋左手边的同学要说下一个数字2。再下面的一个同学要从上一个同学说的数字往下数两个数说出来，也就是说4。下一个同学要往下数三个数，说7。依次类推。

为了使数字不至于太大，栋栋和同学们约定，当在心中数到 k-1 时，下一个数字从0开始数。例如，当k=13时，栋栋和同学们报出的前几个数依次为：
1, 2, 4, 7, 11, 3, 9, 3, 11, 7。

游戏进行了一会儿，栋栋想知道，到目前为止，他所有说出的数字的总和是多少。

输入格式

输入的第一行包含三个整数 n,k,T，其中 n 和 k 的意义如上面所述，T 表示到目前为止栋栋一共说出的数字个数。

输出格式

输出一行，包含一个整数，表示栋栋说出所有数的和。

样例输入

3 13 3

样例输出

17

样例说明

栋栋说出的数依次为1, 7, 9，和为17。

数据规模和约定

1 < n,k,T < 1,000,000；

之前写了一种穷举的法方然后只得了50分。然后在网上看了别人写的，结果也是得分不全。

穷举一个个的找：

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
import java.util.Scanner;

public class 数字游戏 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		int T=sc.nextInt();
		
		System.out.println(f(n,k,T));
	}

	private static String f(int n, int k, int t) {
		
		int shu=1;
		int conut=0;
		int sum=0;
		for (int i = 0; i < t; i++) {
			for (int j = 0; j < n; j++) {
				shu+=conut;
				conut++;
				while(shu>k-1){
					shu=shu-k;
				}
				if(j==0)
					sum+=shu;
			}
		}
		return sum+"";
	}
}

网上别人写的（他是用C语言写的，然后我改成java的）

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 数字游戏2 {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		while(sc.hasNext()){
			int n=sc.nextInt();
			int k=sc.nextInt();
			int t=sc.nextInt();
			
			long sum=1,l=1,r=n,x=1;
			for (int i = 1; i < t; i++) {
				x+=(l+r)*n/2;
				x=x%k;
				sum+=x;
				l=1+i*n;
				r=n+i*n;
			}
			System.out.println(sum);
		}
	}
}

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

算法训练 字符串变换
时间限制：1.0s 内存限制：256.0MB

问题描述
相信经过这个学期的编程训练，大家对于字符串的操作已经掌握的相当熟练了。今天，徐老师想测试一下大家对于字符串操作的掌握情况。徐老师自己定义了1,2,3,4,5这5个参数分别指代不同的5种字符串操作，你需要根据传入的参数，按照徐老师的规定，对输入字符串进行格式转化。
徐老师指定的操作如下：
1 表示全部转化为大写字母输出，如abC 变成 ABC
2 表示全部转换为小写字母输出，如abC变成abc
3 表示将字符串整个逆序输出，如 abc 变成 cba
4 表示将字符串中对应的大写字母转换为小写字母，而将其中的小写字母转化为大写字母输出，如 abC变成ABc
5表示将全部转换为小写字母，并将其中所有的连续子串转换为对应的缩写形式输出，比如abcD 转换为a-d，其次，-至少代表1个字母，既如果是ab，则不需要转换为缩写形式。
输入格式
一共一行，分别是指代对应操作的数字和字符串，两者以空格分隔，字符串全部由英文字母组成
输出格式
输出根据上述规则转换后对应的字符串
样例输入
5 ABcdEE
样例输出
a-ee
数据规模和约定
输入字符串长度最长为200。

这个题比较简单，会字符串大写和小写转换的两个方法就没什么问题了。主要是第五种情况还是有点麻烦的，需要细心点。

代码：

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
64
65
66
67
68
import java.util.Scanner;

public class 字符串变换 {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		while(sc.hasNext()){
			int n=Integer.parseInt(sc.next());
			String s=sc.next();
			
			switch (n) {
			case 1:
				System.out.println(s.toUpperCase());
				break;
			case 2:
				System.out.println(s.toLowerCase());
				break;
			case 3:
				for (int i = s.length()-1; i >= 0; i--) {
					System.out.print(s.charAt(i));
				}
				break;
			case 4:
				for (int i = 0; i < s.length(); i++) {
					if(s.charAt(i)>=97&&s.charAt(i)<=122){
						System.out.print((char)(s.charAt(i)-32));
					}else if(s.charAt(i)>=65&&s.charAt(i)<=90){
						System.out.print((char)(s.charAt(i)+32));
					}
				}
				break;
			case 5:
				s=s.toLowerCase();
				String re=s.charAt(0)+"";
				char a=s.charAt(0);
				int count=0;
				if(s.length()==2){
					System.out.println(s);
					return;
				}
				for (int i = 1; i < s.length(); i++) {
					if(s.charAt(i)-a==1){
						count++;
					}else{
						if(count>1){
							re+="-";
							re+=s.charAt(i-1);
						}
						re+=s.charAt(i);
						count=0;
					}
					a=s.charAt(i);
				}
				if(count>1){
					re+="-";
					re+=s.charAt(s.length()-1);
				}
				if(count==1){
					re+=s.charAt(s.length()-1);
				}
				System.out.println(re);
				break;
			}
		}
	}
}

算法训练 P1102
时间限制：1.0s 内存限制：256.0MB

定义一个学生结构体类型student，包括4个字段，姓名、性别、年龄和成绩。然后在主函数中定义一个结构体数组（长度不超过1000），并输入每个元素的值，程序使用冒泡排序法将学生按照成绩从小到大的顺序排序，然后输出排序的结果。
输入格式：第一行是一个整数N（N<1000），表示元素个数；接下来N行每行描述一个元素，姓名、性别都是长度不超过20的字符串，年龄和成绩都是整型。
输出格式：按成绩从小到大输出所有元素，若多个学生成绩相同则成绩相同的同学之间保留原来的输入顺序。
输入：
3
Alice female 18 98
Bob male 19 90
Miller male 17 92

输出：
Bob male 19 90
Miller male 17 92
Alice female 18 98

这个题还是蛮有意思的用两个数组，一个一维数组一个二维数组，一维数组管要输出的内容，二维数组装分数和下标。

代码：

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
import java.util.Scanner;

public class P1102 {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=Integer.parseInt(sc.nextLine());
			String[] data=new String[n];
			int[][] arr=new int[n][2];
			String s;
			for (int i = 0; i < data.length; i++) {
				s=sc.nextLine();
				String[] ch=s.split(" ");
				data[i]=s;
				arr[i][0]=i;
				arr[i][1]=Integer.parseInt(ch[3]);
			}
			
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr.length; j++) {
					if(arr[i][1]<arr[j][1]){
						int t1=arr[i][1];
						arr[i][1]=arr[j][1];
						arr[j][1]=t1;
						
						int t2=arr[i][0];
						arr[i][0]=arr[j][0];
						arr[j][0]=t2;
					}
				}
			}
			for (int i = 0; i < arr.length; i++) {
				for (int j = 0; j < arr.length; j++) {
					if(arr[i][1]==arr[j][1]){
						if(arr[i][0]<arr[j][0]){
							int k=arr[i][0];
							arr[i][0]=arr[j][0];
							arr[j][0]=k;
						}
					}
				}
			}
			for (int i = 0; i < arr.length; i++) {
				System.out.println(data[arr[i][0]]);
			}
		}
	}
}

算法训练 P1101
时间限制：1.0s 内存限制：256.0MB


有一份提货单，其数据项目有：商品名（MC）、单价（DJ）、数量（SL）。定义一个结构体prut，其成员是上面的三项数据。在主函数中定义一个prut类型的结构体数组，输入每个元素的值，计算并输出提货单的总金额。
输入格式：第一行是数据项个数N(N<100)，接下来每一行是一个数据项。商品名是长度不超过100的字符串，单价为double类型，数量为整型。
输出格式：double类型的总金额。
输入：
4
book 12.5 3
pen 2.5 10
computer 3200 1
flower 47 5

输出：
3497.500000

这个题蛮简单的，注意保留六位数小数就行了。

代码：

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;
import java.math.BigDecimal;

public class P1101 {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		while(sc.hasNext()){
			int n=Integer.parseInt(sc.nextLine());
			double sum=0;
			String s;
			for (int i = 0; i < n; i++) {
				s=sc.nextLine();
				String[] strarr=s.split(" ");
				double x=Double.parseDouble(strarr[1])*Double.parseDouble(strarr[2]);
				sum+=x;
			}
			BigDecimal bd=BigDecimal.valueOf(sum);
			String str=bd.setScale(6, BigDecimal.ROUND_HALF_UP).toString();
			System.out.println(str);
		}
	}
}

ps:这几天做的题都比较简单，明天开始做历届试题吧。一天搞懂两题。