手柄君的小阁

个人私货聚集地

时间

17/04/11 22:21

作者

分类

学习笔记 Java品鉴

标签

, , , ,
3 条评论

NYOJ 题目42 一笔画问题(Java)

本文最后更新于 2018 年 5 月 10 日，其中的内容可能有所发展或发生改变，敬请注意。

题目来自于 南阳理工学院ACM在线测评系统

时间限制：3000 ms | 内存限制：65535 KB
难度：4

描述
zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。
规定，所有的边都只能画一次，不能重复画。

输入
第一行只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000)，分别表示这个画中有多少个顶点和多少条连线。（点的编号从1到P）
随后的Q行，每行有两个正整数A,B(0<A,B<P)，表示编号为A和B的两点之间有连线。

输出
如果存在符合条件的连线，则输出"Yes",
如果不存在符合条件的连线，输出"No"。

样例输入

2
4 3
1 2
1 3
1 4
4 5
1 2
2 3
1 3
1 4
3 4

样例输出

No
Yes

来源
[张云聪]原创

解题思路
首先，由于前一阵子刚好学到过一笔画相关解题法，故想起来需满足欧拉定理：
    如果图形可以一笔画，那么一定满足以下条件：1.图形是封闭联通的；2.图形中和奇数个数边相连的点只有0个或者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

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int loops = in.nextInt();
		int P,Q;
		int T;
		for(int i = 0; i < loops; i++){
			P = in.nextInt();
			Q = in.nextInt();
			int[] points = new int[P];
			for(int j = 0; j < Q; j++){
				points[in.nextInt()-1]+=1;
				points[in.nextInt()-1]+=1;
			}
			T = 0;
			for(int j = 0; j < P; j++){
				T += points[j] % 2;
			}
			System.out.println(T==0|T==2 ? "yes" : "no");
		}
		in.close();
	}
}

提交到NYOJ，判错误，理由为答案错误，尝试修改，得到以下错误答案

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

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int loops = in.nextInt();
		int[] set = new int[loops];
		int P,Q;
		int T;
		for(int i = 0; i < loops; i++){
			P = in.nextInt();
			Q = in.nextInt();
			int[] points = new int[P];
			for(int j = 0; j < Q; j++){
				points[in.nextInt() - 1]+=1;
				points[in.nextInt() - 1]+=1;
			}
			T = 0;
			for(int j = 0; j < P; j++){
				if (points[j] == 0) {
					T = 1;
					return;
				}
				T += points[j] % 2;
			}
			set[i] = T;
		}
		in.close();
		for (int i = 0; i < set.length; i++){
			System.out.println(set[i] == 0 || set[i] == 2 ? "Yes" : "No");
		}
	}
}

后百度搜索一笔画条件，发现忽视欧拉定理第一个条件，故重写算法

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.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int loops = in.nextInt();//一共有多少组待判断的图形
		int[] set = new int[loops];//用于输出结果的数组
		int P,Q;
		int T;//用于输出的临时存储媒介
		for(int i = 0; i < loops; i++){
			P = in.nextInt();//点的数量
			Q = in.nextInt();//边的数量
			int[] points1 = new int[Q];//待输入的边的端点数组1
			int[] points2 = new int[Q];//待输入的边的端点数组2
			int[] points = new int[P];
			for(int j = 0; j < Q; j++){
				points1[j] = in.nextInt();
				points2[j] = in.nextInt();
			}
			int[] pointsIn = new int[P];//互相联通的端点-数组
			pointsIn[points1[0]-1] = points1[0];
			pointsIn[points2[0]-1] = points2[0];
			T = 0;
			//判断是否连通图形
			//非连贯性地写入已和已知联通端点相联通的端点
			for(int j = 1; j < Q; j++){
				if(inInt(pointsIn,points1[j])){
					pointsIn[points2[j]-1] = points2[j];
				} else if(inInt(pointsIn,points2[j])){
					pointsIn[points1[j]-1] = points1[j];
				}
			}
			for(int j = 0; j < P; j++){
				//如果有端点未被包含在已联通的点内，则说明该图形并不是封闭联通的
				if (pointsIn[j] == 0) T = 1;
			}
			//判断是否符合欧拉定理第二条
			for(int j = 0; j < Q; j++){
				points[points1[j]-1] += 1;
				points[points2[j]-1] += 1;
			}
			if (T==0) {for(int j = 0; j < P; j++){
					T += points[j] % 2;//计算奇数端点数量
				}
			}
			set[i] = T;//将该组结果写入数组，等待输出
		}
		in.close();
		for (int i = 0; i < set.length; i++){
			System.out.println(set[i] == 0 || set[i] == 2 ? "Yes" : "No");//输出结果
		}
	}
	//定义方法，用于判断某个数是否包含在某数组内
	private static boolean inInt(int[] array,int searchInt){
		for (int i=0;i<array.length;i++){
			if (array[i] == searchInt){
				return true;
			}
		}
		return false;
	}
}

得到Accepted结果，通过时间169，内存335
优化，预先定义数组，增加新的第11行，得到

11

		int[] points1,points2,points;

修改15、16、17行

15
16
17

			points1 = new int[Q];
			points2 = new int[Q];
			points = new int[P];

得到Accepted结果，通过时间112，内存335
之后多次负优化均无法达到以上速度，不过内存占用小一点点……
下面献丑献上最后一版负优化版本

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

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int loops = in.nextInt();
		boolean[] set = new boolean[loops];
		int P,Q;
		int[] points1,points2,pointsIn,points;
		boolean bool;
		for(int i = 0; i < loops; i++){
			P = in.nextInt();
			Q = in.nextInt();
			points1 = new int[Q];
			points2 = new int[Q];
			for(int j = 0; j < Q; j++){
				points1[j] = in.nextInt();
				points2[j] = in.nextInt();
			}
			pointsIn = new int[P];
			points  = new int[P];
			pointsIn[points1[0]-1] = points1[0];
			pointsIn[points2[0]-1] = points2[0];
			set[i] = true;
			//判断是否连通图形
			for(int j = 1; j < Q; j++){
				bool = false;
				for (int k = 0; k < P ; k++){
						if (pointsIn[k] == points1[j]){
							bool = true;
							break;
						}
				}
				if(bool){
					pointsIn[points2[j]-1] = points2[j];
				} else {
					bool = false;
					for (int k = 0; k < P ; k++){
							if (pointsIn[k] == points2[j]){
								bool = true;
								break;
							}
					}
					if(bool){
						pointsIn[points1[j]-1] = points1[j];
					}
				}
			}
			for(int j = 0; j < P; j++){
				if (pointsIn[j] == 0) set[i] = false;
			}
			//判断是否符合欧拉定理第二项
			if (set[i]) {
				for(int j = 0; j < Q; j++){
					points[points1[j]-1] += 1;
					points[points2[j]-1] += 1;
				}
				for(int j = 0, k = 0; j < P; j++){
					k += points[j] % 2;
					set[i] = (k == 0 || k == 2 ? true : false);
				}
			}
		}
		in.close();
		for (int i = 0; i < set.length; i++){
			System.out.println(set[i] ? "Yes" : "No");
		}
	}
}

以上，学到了些什么呢？
    1.设计算法烧脑子
    2.设计算法烧脑子
    3.再见我去打OW去了

0

相关文章

蓝桥杯(大专组) 校内训练 1002.单位转换 蓝桥杯(大专组) 校内训练 1004.算术运算 蓝桥杯(大专组) 校内训练 1003.奇偶排序 蓝桥杯(大专组) 校内训练 1001.不重复数
  1. Katyusha Katyusha说道：
    05/21/2017 13:12

    qwq日常膜拜dalao

    吐槽TA
  2. 头像 镜子说道：
    04/12/2017 09:22

    不是那种能造轮子的人（

    吐槽TA
    1. 头像 Handle说道：
      04/12/2017 15:56

      所以吾要加油学习造轮子嘛

      吐槽TA

来一发吐槽