蓝桥杯

First Post:

Last Update:

Word Count:
1.5k

Read Time:
7 min

Page View: loading...

救赎

基础知识

1.欧几里得辗转相除法 求解 最大公约数 最小公倍数

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

2.求质数

1
2
3
4
5
6
7
/* 判断素数 */
bool isPrime(LL n) {
	for (int i = 2; i * i <= n; ++i)
		if (n % i == 0)
			return false;
	return true;
}

3.栈

1
2
3
4
5
6
7
#include <stack>
stack<类型> mystack;
s.empty();         //如果栈为空则返回true, 否则返回false;
s.size();          //返回栈中元素的个数
s.top();           //返回栈顶元素, 但不删除该元素
s.pop();           //弹出栈顶元素, 但不返回其值
s.push();          //将元素压入栈顶

4.队列

1
2
3
4
5
6
7
8
#include <queue>
queue<类型> myqueue;
push() //在队尾插入一个元素
pop() //删除队列第一个元素
size() //返回队列中元素个数
empty() //如果队列空则返回true
front() //返回队列中的第一个元素
back() //返回队列中最后一个元素

5.DFS(深度优先)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int mp[N][N];//存放迷宫
int vis[N][N];//表示是否访问过，初始为flase
void DFS(int x, int y)	//x,y是坐标点的位置 
{
	if(vis[x][y] || (x==n && y==n)) return; //表示已经访问过了或者到达终点,递归的出口
	vis[x][y] = true; //表示没有访问过，现在正在访问，置为访问过
	for(int i=0; i < 4; i++){	//遍历四个方向，顺序依次是，上下左右
		int nx = x + dx[i];
		int ny = y + dy[i];
      //进行了合法性检验，
      //1.首先判断了该点是否越界，即是否在迷宫内  nx > 0 && nx <= n && ny > 0 && ny <= n
      //2.然后判断是否访问过  !vis[nx][ny] 未访问过就继续
      //3.最后判断是否为路  mp[nx][ny] == '0' 为路就继续
		if(nx > 0 && nx <= n && ny > 0 && ny <= n && !vis[nx][ny] && mp[nx][ny] == '0')
			dfs(nx,ny);
	} 
}
//注意!! 应该判断一下起点是否可走

6.BFS(广度优先搜索)

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
int X[4]={0, 0, -1, 1};
int Y[4]={-1, 1, 0, 0};
int matrix[N][N]; //存储迷宫信息
int vis[N][N];	//存储每个状态点是否走过

struct node{
	int x;
	int y;
}Node, top;

bool judge(int xx, int yy)
{
	if(xx<0||yy<0||xx>=N||yy>=N) //注意边界
		return false;
	if(vis[xx][yy]==true||matrix[xx][yy]==0)	//下一个点走过或者为墙 0不能走，1能走
		return false;
	return true;
}


void BFS(int x, int y)
{
	queue<node> q;
	Node.x=x;
	Node.y=y;
	q.push(Node);	//将起点入队列
	while(!q.empty())	//队列不空就扩散
	{
		top=q.front();	//取出队首元素
		int nx=top.x;
		int ny=top.y;	//从四个方面机进行扩散
         if(nx == ex && ny == ey) //找到终点
             return top;
		for(int i=0; i<4; i++)
		{
			if(judge(nx+X[i], ny+Y[i])) //检查四个方向，如果有路就进队列
			{
				Node.x=nx+X[i];
				Node.y=ny+Y[i];
				q.push(Node);	
			}
		}
		ans++;	//计数器
		vis[nx][ny]=true;
		q.pop();	//表示这个点的邻接点已经全部入队列，丢弃这个点
	}
}

7.二分模板

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
/*
    作者:FengBOOOOOOOOOOOOOOO
    二分模板返回大于x的第一个位置    
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1005
using namespace std;

int a[N],n,q;

int find(int l,int r,int key)//l为-1，r为数组长度
{
    while(l + 1 < r)
    {
        int mid = l + r>>1;
        if(a[mid] <= key)
        　　l = mid;
        else
        　　r = mid;
    }
    return r;//返回大于Key的第一个位置
}

int main()
{
    int k;
    scanf("%d%d",&n,&q);
    for(int i = 0; i < n; ++i)
    　　scanf("%d",&a[i]);
    for(int i = 0; i < q; ++i)
    {
        scanf("%d",&k);
        printf("%d\n",find(-1,n,k));
    }
}

最短路径问题

1.SPFA最短路径(类似与BFS)

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
71
72
73
74
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#define ll long long
#define inf 0x3f3f3f3f
#define pii pair<int, int>
const int mod = 1e9+7;
const int maxn = 2e5+7;
using namespace std;
struct node {int to,w,next;} edge[maxn];
int head[maxn], cnt;
int dis[maxn], vis[maxn];
int n, m, s, t;
struct Spfa
{
    void init()
    {
        memset(head,-1,sizeof(head));
        memset(dis,0x3f3f3f3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        cnt = 0;
    }
 
    void add(int u,int v,int w)
    {
        edge[cnt].to = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt ++;
    }
 
    void spfa()
    {
        dis[s] = 0; vis[s] = 1;
        queue <int> Q; Q.push(s);
        while(!Q.empty())
        {
            int now = Q.front();
            Q.pop(); vis[now] = 0;    //从队列中弹出now , vis[now] 标记为未访问
            for(int i = head[now]; i != -1; i = edge[i].next)
            {
                int v = edge[i].to;
                if(dis[v] < dis[now] + edge[i].w)
                {
                    dis[v] = dis[now] + edge[i].w;
                    if(vis[v]) continue;    //如果访问过了(也就是 已经在队列中),就不用再push
                    vis[v] = 1; Q.push(v);
                }
            }
        }
    }
}sp;
 
int main()
{
    while(~scanf("%d%d",&n,&m) && n+m)
    {
        sp.init();
        for(int i = 0; i < m; i++)
        {
            int u, v, w;
            scanf("%d%d%d",&u, &v, &w);
            sp.add(u, v, w);
            sp.add(v, u, w);
        }
        s = 1, t = n; //s起点，t终点
        sp.spfa();
        printf("%d\n", dis[t]);
    }
}

2.Dijkstra

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
//主要思想一个大循环+两个小循环
void dijkstra(){
	int u, minx;
	book[S] = 1;
	for(int i = 0; i < N; i++){
	//dist[]数组初始化，把起始结点S到i结点的距离赋值给diat[i]
		dist[i] = v[S][i];
	}

	for(int i = 0; i < N; i++){//大循环
		minx = INT_MAX;
		for(int j = 0; j < N; j++){//寻找没有被标记并且最短的路径，并记录此结点 
			if(!book[j] && minx > dist[j]){
				minx = dist[j];
				u = j;
			} 
		}
		book[u] = 1;
		for(int k = 0; k < N; k++){
		//如果A到B的距离大于A到C的距离加C到B的距离，那么更新数据
			if(!book[k] && dist[k] > dist[u]+v[u][k]){
				dist[k] = dist[u]+v[u][k];
			}
		}
	}
}

3.Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

≡