15届蓝桥杯刷题速成

前言
[1. 回文判定](https://www.lanqiao.cn/problems/1371/learning/?page=1&first_category_id=1&name=%E5%9B%9E%E6%96%87%E5%88%A4%E5%AE%9A)
- 代码题解
2.小明的背包
- 代码题解
3.排序
4.小明的彩灯
5.走迷宫
6.蓝桥公园
[ 7.蓝桥王国](https://www.lanqiao.cn/problems/1122/learning/?page=1&first_category_id=1&name=%E8%93%9D%E6%A1%A5%E7%8E%8B%E5%9B%BD)
结语

前言

这期我们来做一下蓝桥杯的速成题，一共七道，粗略感受一下蓝桥杯，我们做题的顺序一定是由易到难，这样能节省很多时间去做难题。

在这里插入图片描述

1. 回文判定

代码题解

#include <iostream>
#include<string>
using namespace std;int main(){string s;cin >> s;int l = 0, r = s.size() - 1;while(l<r){if(s[l]!=s[r]){cout << "N" << endl;break;}l++, r--;}if(l>=r) cout << "Y" << endl;return 0;
}

2.小明的背包

代码题解

#include <iostream>
using namespace std;#define maxn 101 //总共多少个物品
#define maxv 1001 //最大容量
#define inf -1  // 非法状态的值，因为要找最大值，所以定义为-1
#define init 0
#define vType int //价值类型void Knapsack01(int n, int V, int w[maxn], int v[maxn], vType dp[maxn][maxv]){for(int i = 1; i <= V; i++){ //初始化非法状态，因为是求最大价值，放入背包里的物品为0就没有最大值，所以是非法dp[0][i] = inf;}dp[0][0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j <= V; j++){if(j >= w[i]){//判断就是否大于等于w[i]，避免下标越界dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);}else{dp[i][j] = dp[i-1][j];}}}
}int w[maxn];
vType v[maxn];
vType dp[maxn][maxv];int main()
{int n, V;cin >> n >> V;for(int i = 1; i <= n; i++){cin >> w[i] >> v[i];}vType ret = 0;Knapsack01(n, V, w, v, dp);for(int i = 0; i <= V; i++){ret = max(ret, dp[n][i]);}cout << ret << endl;return 0;
}

3.排序

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int a[500001];int n;cin >> n;for(int i = 0; i < n; i++){cin >> a[i];}sort(a,a+n);for(int i = 0; i < n; i++){if(i) cout << " ";cout << a[i];}cout << endl;for(int i = n - 1; i >= 0; i--){if(i!=n-1) cout << " ";cout << a[i];}return 0;
}

4.小明的彩灯

#include <iostream>
using namespace std;int main()
{int n, q;long long a[500005];cin >> n >> q;for(int i = 0; i < n; i++){cin >> a[i];}for(int i = 0; i < q; i++){int l, r, x;cin >> l >> r >> x;for(int j = l - 1; j <= r -1; j++){a[j] += x;}}for(int i = 0; i < n; i++){if(i) cout <<  ' ';if(a[i] < 0) a[i] = 0;cout << a[i];}return 0;
}

5.走迷宫

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;#define maxn 101
#define base 101
int mat[maxn][maxn];int dir[4][2] = {//表示该顶点的上下左右位置{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};int main()//广度优先搜索
{int hash[maxn][maxn];//用于记录从起始点到另一个点的距离memset(hash, -1, sizeof(hash));//将hash数组元素全部初始化为-1，表示没有经过这个位置int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> mat[i][j];}}int x1, x2, y1, y2;cin >> x1 >> y1 >> x2 >> y2;queue<int> q;q.push(x1 * base + y1);hash[x1][y1] = 0;//起始位置的值一定为0    while(!q.empty()){int v = q.front();q.pop();int tx = v / base;int ty = v % base;if(tx == x2 && ty == y2) break;for(int i = 0;i < 4; i++){int rx = tx + dir[i][0];int ry = ty + dir[i][1];if(rx < 1 || rx > n || ry < 1 || ry > m) continue;//越界判断，越界坐标就是非法位置if(mat[rx][ry] == 0) continue;//从原点到该点没有路，也直接到另一个方向位置判断if(hash[rx][ry] == -1){//代表这个点没有访问过hash[rx][ry] = hash[tx][ty] + 1;//从原点到这个方向的点格子数加1q.push(rx * base + ry);}}}cout << hash[x2][y2] << endl;return 0;
}

6.蓝桥公园

#include <iostream>
#include <cstring>
using namespace std;#define maxn 401
#define eType long long eType edges[maxn][maxn];int main()
{int n, m, q;cin >> n >> m >> q;memset(edges,-1,sizeof(edges));for(int i=1;i<=n;i++){edges[i][i] = 0;//顶点到他本身的距离为0}for(int i = 0; i < m; i++){int u, v;eType w;cin >> u >> v >> w;if(edges[u][v]==-1 || edges[u][v] > w){//是无向图所以u到v的距离等于v到u的距离edges[u][v] = w;}if(edges[v][u] == -1 || edges[v][u] > w){edges[v][u] = w;}}for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){if(i == k) continue;//i到除他自己以外的顶点if(edges[i][k] == -1) continue;//i到k没有路for(int j = 1; j <= n; j++){if(j == k || j == i) continue;//与上同理if(edges[k][j] == -1) continue;if(edges[i][k] + edges[k][j] < edges[i][j] || edges[i][j] == -1){edges[i][j] = edges[i][k] + edges[k][j];}}}}while(q--){int u,v;cin >> u >> v;cout << edges[u][v] <<endl;}return 0;
}

7.蓝桥王国

#include <iostream>
#include<queue>
#include<vector>
using namespace std;#define inf 1000000001000000001
#define valueType long long
#define maxn 300001struct Dist{int v;valueType w;Dist(){}Dist(int _v,valueType _w):v(_v),w(_w){}bool operator<(const Dist& d)const{//运算符重载，比较w大小进行排序return w>d.w;}
};typedef priority_queue<Dist> Heap;//用邻接表来存储每一个元素，元素类型为Dist这个对象void addEdges(int u, int v, valueType w, vector<Dist>*edges){edges[u].push_back(Dist(v,w));
}void dijkstraInit(int n, int st, Heap& heap, bool* visited, valueType* d){for(int i=0;i<n;i++){visited[i]=false;d[i]=inf;}d[st]=0;heap.push(Dist(st,d[st]));
}int dijstraFindMin(Heap& heap){Dist s=heap.top();//因为运算符重载，优先队列已经排序好每一个顶点，所以该队列的top接口就是路径最短的顶点heap.pop();return s.v;
}void dijstraUpdate(int u, bool* visited, Heap& heap, vector<Dist>* edges, valueType* d){if(visited[u])return ;visited[u] = true;for(int i = 0; i < edges[u].size(); i++){int v = edges[u][i].v;valueType w = edges[u][i].w;if(d[u] + w < d[v]){d[v] = d[u] + w;heap.push(Dist(v, d[v]));}}
}void DijkstraHeap(int n, int st, vector<Dist>* edges, valueType* d){Heap heap;bool visited[maxn]={false};//用于标记顶点是否被访问过dijkstraInit(n, st, heap, visited, d);//while(!heap.empty()){int u=dijstraFindMin(heap);dijstraUpdate(u, visited, heap, edges, d);//更新该点到其他点的最短路径}
}vector<Dist> edges[maxn];
valueType d[maxn];int main()
{int n, m;cin >> n >> m;for(int i = 0; i < m; i++){int u, v ,w;cin >> u >> v >> w;--u, --v;//编号从0开始，改图为单向边addEdges(u, v, w, edges);}DijkstraHeap(n, 0, edges, d);for(int i = 0; i < n; i++){if(i)cout << " ";if(d[i] == inf)cout << -1;else cout << d[i];}cout << endl;return 0;
}