一些优雅的算法（c++）

求最大公约数：辗转相除法

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
1
2
3

求最小公倍数：两整数之积除以最大公约数

int lcm(int a, int b){
    return a*b / gcd(a, b);
}
1
2
3

十进制转n进制：

char get(int x){
	if(x<=9){
		return x+'0';
	}
	else{
		return (x-10)+'A';
	}
}
1
2
3
4
5
6
7
8

string base(int x) // 十进制转 n进制
{
    string num;
    while(x){
        num += get(x % n), x /= n;
    }
    reverse(num.begin(),num.end());
    return num;
}
1
2
3
4
5
6
7
8
9

c语言输出

printf（"%02d", a）
1

表示输出按俩位输出整形a，比如a=8，则输出08，a=24，输出24

printf("%.2f",a)
1

表示输出浮点数a小数点后俩位，比如a=8,则输出8.00，a=1.123，则输出a=1.12

最短路径问题

什么是链式前向星实现邻接表

链式前向星实现：设置三个数组，一个数组h用来存节点，一个数组e用来存值，一个数组ne用来存下一个节点。我们需要设置索引idx来实现ne的查找，不然没法链接起来

void add(int a,int b) {
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
1
2
3

例：

我们遍历的话就是从h[1]开始遍历，此时h[1]=4，然后我们找下一个节点，下一个节点对应的索引就是3，再下一个节点对应的索引就是0，当索引为-1时结束。这个过程next实际上是向前走的，关系又是链式的，因此成为链式前向星

为什么要用memset(dist,0x3f,sizeof dist)来初始化

回答:：0x3f3f3f3f的十进制是1061109567，是1e9级别的（和0x7fffffff一个数量级，0x7fffffff代表了32-bit int的最大值），而一般场合下的数据都是小于1e9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。 另一方面，由于一般的数据都不会大于10^9，所以当我们把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”），事实上0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。

floyd

E.路径（12届蓝桥杯c++B组第一场省赛）

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题。

#include 
#include 
#include 
using namespace std;
const int N = 3000;
int n = 2021;
int g[N][N];
// 求最小公约数
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void floyb() {
    for (int t = 1; t <= n; ++ t) {
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                g[i][j] = min(g[i][j], g[i][t] + g[t][j]);
            }
        }
    }
}
int main (){
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            if (abs(i - j) <= 21) {
                // 最大公倍数求法
                g[i][j] = i * j / gcd(i, j);
            }
        }
    }
    floyb();
    cout << g[1][n] << endl;
    return 0;
}
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

并查集

小蓝要用七段码数码管来表示一种特殊的文字。

上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二 极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。
例如： b 发光，其他二极管不发光可以用来表达一种字符。
例如： c 发光，其他二极管不发光可以用来表达一种字符。这种 方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如： a, b, c, d, e 发光， f, g 不发光可以用来表达一种字符。
例如： b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
【答案提交】 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#include
using namespace std;
const int N=10;
int e[N][N],use[N],ans=0,fa[N];
int find(int f){//查找父值 
	if(fa[f]==f){
		return f;
	}
	return find(fa[f]);
}
void dfs(int n){
	if(n>7){
		for(int i=1;i<=7;i++){
			fa[i]=i;//每个元素单独成一个集合 
		}
		for(int i=1;i<=7;i++){//遍历每条边 
			for(int j=1;j<=7;j++){
				if(e[i][j]&&use[i]&&use[j]){//如果ij连通且都已打开，使它们的父集相等 
					int fx=find(i),fy=find(j);
					if(fx!=fy){
						fa[fx]=fy;//合并集合：即让它们的父值相等 
					}
				}
			}
		}
		int k=0;
		for(int i=1;i<=7;i++){ 
			if(fa[i]==i&&use[i]){//判断现有元素有几个集合 
				k++;
			}
		}
		if(k==1){//如果已使用的灯在一个集合内：即父集只有一个元素 
			ans++;
		}
		return ;
	}
	use[n]=1;
	dfs(n+1);
	use[n]=0;
	dfs(n+1);
}
int main(){
	e[1][2]=e[1][6]=1;
	e[2][3]=e[2][7]=1;
	e[3][4]=e[3][7]=1;
	e[4][5]=1;
	e[5][6]=e[5][7]=1;
	e[6][7]=1;
	dfs(1);
	cout<<ans<<endl;
	return 0;
}
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

getline（）

接收一个字符串，可以接收空格并输出，读取缓冲区的回车然后舍弃

#include
#include
using namespace std;
main ()
{
string str;
getline(cin,str);
cout<<str<<endl;
}
1
2
3
4
5
6
7
8
9

输入：jkljkljkl
输出：jkljkljkl
输入：jkl jfksldfj jklsjfl
输出：jkl jfksldfj jklsjfl

push_back()

push_back() 在Vector最后添加一个元素（参数为要插入的值）

vector<int> vec;
vec.push_back(10);
//在容器中添加10
1
2
3

或者再string中最后插入一个字符；

string str;
str.push_back('d');
1
2

类似的：

pop_back() //移除最后一个元素
clear()  //清空所有元素
empty() //判断vector是否为空，如果返回true为空
erase() // 删除指定元素
1
2
3
4