本文最后更新于 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，故写出以下错误答案代码
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，判错误，理由为答案错误，尝试修改，得到以下错误答案
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");
}
}
}
后百度搜索一笔画条件，发现忽视欧拉定理第一个条件，故重写算法
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行，得到
int[] points1,points2,points;
修改15、16、17行
points1 = new int[Q]; points2 = new int[Q]; points = new int[P];
得到Accepted结果，通过时间112，内存335
之后多次负优化均无法达到以上速度，不过内存占用小一点点……
下面献丑献上最后一版负优化版本
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去了
qwq日常膜拜dalao
不是那种能造轮子的人（
所以吾要加油学习造轮子嘛