DAY1:
上午：
引入：
对任意两个元素a，b之间关系（a，b）的取值仅为 True 或者 False，可以考虑使用图来抽象。这样我们称一个元素 a 为一个结点，（a，b）== True 则称结点 a，b 间有连边，否则 a，b 间没有连边。
问题转化：一张奇数个点的图 G，证明存在一个点度数为偶数。
转化为更强的问题为：给定一张奇数个点的图 G，证明度数为偶数的点的个数为奇数。
（相反的问题：给定一张奇数个点的图 G，证明度数为奇数的结点的个数为偶数。）
证明：考虑所有点的度数和，由于一条边会被计算到两个结点的度数上，故其必定为偶数。（小学数学易得结论？）
Ex.1：首先可证 n-1 个点与除它之外 n-2 个点连边所以可连 (n-1)(n-2)/2 条边，因此可得 n 个点和至少 ((n-1)(n-2)/2)+1 条边的图是连通图。
Ex.2：
由图可得，对于任意一个图，可将其分为若干个连通块，连通块内部各点都相连，因此其补图原来的连通块内各点于其他各连通块各点相连，因此一定是联通的。
Ex.3：
任意两边至少有一个点是重合的，即为如图：
因此当为完全图时，每点度数>=2，因此不可能为星星，反之亦然。
Ex.4：***
Ex.5：分类讨论，
当存在度数为一的点时，删掉度数为一的点剩下的图依旧是连通图。
当不存在时，选择任意一点为起点，计算其他点与起点的距离，删掉距离起点最远的点后，图依旧为连通图。
欧拉回路和哈密顿回路：
1）考虑一个度数为奇数的点，因为它的所有邻边均要遍历恰好一次，故其必须为欧
拉路径的起点或终点。因此可以立即推出，一张存在欧拉路径的图恰好有两个度数为奇数
的点，存在欧拉回路的图没有度数为奇数的点。
2）任意两个回路，可以拼成一个大的回路。
由这两个观察可以发现，Fact 1是存在欧拉路径或者欧拉回路的充要条件。
反证法，假设没有哈密顿回路。
我们由图 G 构造出一个新的没有哈密顿回路的图 G'，具体的，令 G'=G，对于每条不在图 G 中的边，如果加入 G' 后不会产生哈密顿回路，则加入，该构造的顺序不重要。
此时我们得到了一个图 G'，再加入任何一条边都会得到一条哈密顿回路，并且由于我们仅加入了新的边，所有结点的度数任然大于等于 n/2。
假设 (v1，vn) 这条边不在 G' 中，我们知道必定存在一条哈密顿路径 v1，v2，...，vn 考虑 (v1，vi) 有一条边，则 (vi-1，vn) 必定不能有边，否则可以构造出一条哈密顿回路。
因为这样的 vi 至少有 n/2 个，从而这样的 vi-1 也至少有 n/2 个，又由于 vn 不能和自己连边，故而它至多与 n-n/2-1 个点连边，<=n/2 ，因此与定理矛盾，因此假设不成立。
Ex.6：因为两数互质，因此间隔至少为2，又因为有 n+1，个小于等于 2n 的正整数，所以显然，存在两个数互质。
Ex.7：...
Ex.8：将棋盘进行黑白染色和蓝红染色
Ex.9：Luogu P1341
1 //By:Komorebi_03 2 #include<bits/stdc++.h> 3 using namespace std; 4 #define clear(a) memset(a,0,sizeof a) 5 #define ll long long 6 const int N = 1e3+5; 7 int n,sum,dis[N][N]; 8 char in[N],a[N]; 9 inline int read() 10 { 11 int x=0,f=1;char ch=getchar(); 12 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 13 while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} 14 return x*f; 15 } 16 17 void Find(int i) 18 { 19 for (int j=1;j<=150;j++) 20 { 21 if(dis[i][j]>0) 22 { 23 dis[i][j]--; 24 dis[j][i]--; 25 Find(j); 26 } 27 } 28 a[++sum]=i; 29 return ; 30 } 31 32 int main() 33 { 34 n=read(); 35 for (int i=1;i<=n;i++) 36 { 37 string s; 38 cin>>s; 39 dis[s[0]][s[1]]++; 40 dis[s[1]][s[0]]++; 41 in[s[0]]++; 42 in[s[1]]++; 43 } 44 int h=0; 45 int cnt=0; 46 for (int i=1;i<=150;i++) 47 { 48 if(in[i] & 1) 49 { 50 cnt++; 51 if(!h) 52 h=i; 53 } 54 } 55 if(!h) 56 { 57 for (int i=0;i<150;i++) 58 { 59 if(in[i]) 60 { 61 h=i; 62 break; 63 } 64 } 65 } 66 if(cnt && cnt!=2) 67 { 68 cout<<"No Solution"; 69 exit(0); 70 } 71 Find(h); 72 if(sum<n+1) 73 { 74 cout<<"No Solution"; 75 exit(0); 76 } 77 for(int i=sum;i>=1;i--) 78 cout<<a[i]; 79 return 0; 80 //Amireux_35 81 }
图的储存和遍历：