学习笔记

学习笔记-算法

主要是方便我以后复习，以下内容可能有些不严谨。

一、辗转相除法（欧几里德定理）

​ 用来求最大公约是和最小公倍数

gcd = (b, a % b) lcm = a * b / gcd

​ 例如：a b c(a % b)

​ 65 15 5

​ 15 5 0

​ 所以最大公约数为5

伪代码：

if(a < b) {
    t = a;
    a = b;
    b = t;
}
d = a * b;
c = a % b;
while(c != 0) {
    a = b;
    b = c;
    c = a % b;
}
cout<<"最大公约数:"<<b<<endl;
cout<<"最小公倍数:"<<d / b<<endl;

二、并查集

一开始我想的是DFS，但是DFS一直没学会呜呜呜，这个题很像染色定理，然后看了讲解发现这个题还可以用并查集做（明明学过并查集为什么我没想到呢）。

三、DFS

当时第一反应是并查集，写完之后不对，又读了一遍题目，题目要求是认识的人不能在一个考场，如果用并查集解决的话应该是认识的人在一个考场，最后发现是用DFS。