深度优先

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

0%

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

基础练习 矩形面积交

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

锦囊1

判断。

锦囊2

公共部分为两个矩形左边界较大值到右边界较小值，从下边界较大值到上边界较小值。

问题描述

平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。

输入格式

输入仅包含两行，每行描述一个矩形。
在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7的实数表示。

输出格式

输出仅包含一个实数，为交的面积，保留到小数后两位。

样例输入

1 1 3 3
2 2 4 4

样例输出

1.00

就是判断，再就是保留两位小数。代码：

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
69
70
71
72
73
74
import java.util.Scanner;
import java.math.BigDecimal;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		double[] arr1=new double[4];
		double[] arr2=new double[4];
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
		for (int i = 0; i < arr1.length; i++) {
			arr1[i]=sc.nextDouble();
		}
		for (int i = 0; i < arr1.length; i++) {
			arr2[i]=sc.nextDouble();
		}
		
		double[] arr3=new double[4];
		double[] arr4=new double[4];
		
		//长
		arr3[0]=arr1[0];
		arr3[1]=arr1[2];
		arr3[2]=arr2[0];
		arr3[3]=arr2[2];
		
		if((arr1[0]>arr2[0]&&arr1[0]>arr2[2])&&(arr1[2]>arr2[0]&&arr1[2]>arr2[2])){
			System.out.println("0.00");
			return;
		}
		if((arr1[0]<arr2[0]&&arr1[0]<arr2[2])&&(arr1[2]<arr2[0]&&arr1[2]<arr2[2])){
			System.out.println("0.00");
			return;
		}
		
		for (int i = 0; i < arr4.length; i++) {
			for (int j = 0; j < arr4.length; j++) {
				if(arr3[i]<arr3[j]){
					double t=arr3[i];
					arr3[i]=arr3[j];
					arr3[j]=t;
				}
			}
		}
		double chang=Math.abs(arr3[2]-arr3[1]);
		
		//宽
		arr4[0]=arr1[1];
		arr4[1]=arr1[3];
		arr4[2]=arr2[1];
		arr4[3]=arr2[3];
		for (int i = 0; i < arr4.length; i++) {
			for (int j = 0; j < arr4.length; j++) {
				if(arr4[i]<arr4[j]){
					double t=arr4[i];
					arr4[i]=arr4[j];
					arr4[j]=t;
				}
			}
		}
		double kuan=Math.abs(arr4[2]-arr4[1]);
		double d=kuan*chang;
		
		BigDecimal bd=BigDecimal.valueOf(d);
		String str=bd.setScale(2, BigDecimal.ROUND_HALF_UP).toString();
		System.out.println(str);
		}
	}
}

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

算法训练 集合运算

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

锦囊1

排序后处理。

锦囊2

先排序，对于每个集合的操作，都使用两个指针来指向排序后的集合，对于相同元素特别处理。

问题描述

给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。

输入格式

第一行为一个整数n，表示集合A中的元素个数。
第二行有n个互不相同的用空格隔开的整数，表示集合A中的元素。
第三行为一个整数m，表示集合B中的元素个数。
第四行有m个互不相同的用空格隔开的整数，表示集合B中的元素。
集合中的所有元素均为int范围内的整数，n、m<=1000。

输出格式

第一行按从小到大的顺序输出A、B交集中的所有元素。
第二行按从小到大的顺序输出A、B并集中的所有元素。
第三行按从小到大的顺序输出B在A中的余集中的所有元素。

样例输入

5
1 2 3 4 5
5
2 4 6 8 10

样例输出

2 4
1 2 3 4 5 6 8 10
1 3 5

样例输入

4
1 2 3 4
3
5 6 7

样例输出

1 2 3 4 5 6 7
1 2 3 4

当时想偷个懒，以为所有的数据都是在不大的范围内，没想到测试数据有点变态。居然还有负数和很大数据。

当时想到用各个很大的数组装就行了，从而不用排序，不过确实是行得通的，居然以下子就过了80%的数据。

代码：

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

public class 集合运算 {
	
	static int[] data=new int[8836460];
	public static void main(String[] args) {
		
		//System.out.println((int)Math.pow(2, 31)-1);
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		for (int i = 0; i < n; i++) {
			data[sc.nextInt()]=1;
		}
		
		int m=sc.nextInt();
		for (int i = 0; i < m; i++) {
			data[sc.nextInt()]+=2;
		}
		int co1=0,co2=0;
		for (int i = 0; i < data.length; i++) {
			if(data[i]==3){
				System.out.print(i+" ");
				co1=1;
			}
		}
		if(co1==1)
			System.out.println();
		for (int i = 0; i < data.length; i++) {
			if(data[i]>0){
				System.out.print(i+" ");
				co2=1;
			}
		}
		if(co2==1)
			System.out.println();
		for (int i = 0; i < data.length; i++) {
			if(data[i]==1){
				System.out.print(i+" ");
			}
		}
	}
}

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

算法训练 回文数

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

锦囊1

模拟。

锦囊2

每次对于当前数均使用题设给出的方法模拟出下一个数，再判断是不是回文数。 在模拟的时候，最好使用一个数组来表示数字，使用高精度计算的方法来处理数的加和回文数的判断。

问题描述

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。

又如：对于10进制数87：
STEP1：87+78 = 165 STEP2：165+561 = 726
STEP3：726+627 = 1353 STEP4：1353+3531 = 4884

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

写一个程序，给定一个N（2<=N<=10或N=16）进制数M（其中16进制数字为0-9与A-F），求最少经过几步可以得到回文数。
如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”

输入格式

两行，N与M

输出格式

如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是步数；否则输出一行”Impossible!”（不含引号）

样例输入

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
47
48
49
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++;
			if(conut==30){
				System.out.println("Impossible!");
				return;
			}
		}
		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;
	}
}