蓝桥杯2015省赛题解,2021蓝桥杯省赛题目

文章目录第一题：卡片第二题：直线第三题：货物配置第四题：路径第五题：电路计数第六题：时间表示第七题：砝码称量第八题：杨辉三角形第九题：双向排序第十题：括号排列

相关文章：

2020年10月蓝桥杯(软件类)省赛)主题解答2020年4月蓝桥杯(软件类)第二届模拟比赛)主题解答2020年3月蓝桥杯(软件类)第一届模拟比赛)主题解答

先整理一下主题吧。 从1开始，从小到大的顺序排列，所以总是先没有一个数字(每个数字都是有限的)。 根据主题示例的呈现，解析：可以容易地找到不够拼出11，事实也是如此。 于是，正题的关键是1是最先用完的

找出刚好用到第2021个1的纸牌！

# include iostream # includes stream # includealgorithmusingnamespacestd； //整数类型转换字符串stringint_str(intI ) {string output； 流转换； 转换； 转换输出； 返回输出； (}int main ) ) {int i=1； int nOne=0； while(1) strings=int_str ) I； none=count(s.begin )、s.end )、'1' )； //记录1出现次数if(none=2021 ) break； elsei =1； }coutiendl； 返回0； }代码运行输出为3181。 应该注意的是，3181有两个1。 此时，有必要自己确认哪个1是2021年的第1个。 判断结果表明，3181中前面的1是第2020个1，后面的1是第2021个1。 所以3181正好可以拼出，但3182不能拼出。 所以最后的答案是参考代码：

第二题：直线http://www.Sina.com/http://www.Sina.com /横向直线和纵向直线分别21和20条即可轻松统计，重点统计不同倾斜直线的个数。 各直线用y=kx b表示。 也就是说，{k，b}的不同组表示不同的直线。 因此，本问题的关键是利用集合存储并统计不同倾斜直线的个数。

318140257

# include iostream # include vector # includesetusingnamespacestd； 结构点{ int x； //横坐标int y； //纵坐标； int main () {vectorpoint p； //保存所有点的for(intI=0； i=19； I ) for(intj=0； j=20； j ) p.push_back({I，j}； int len=p.size (； setpairdouble，双线； //倾斜直线y=kxbfor(intI=0； i len； I ) for(intj=0； j len； j () if ) p[I].x！=p[j].x p[i].y！=p[j].y(/统计所有倾斜直线的情况(doublek=) p[j].y-p[I].y ) *1.0/) p[j].x-p[I].x )； doubleb=(p[j].y* ) * * p[j].x [ I ].x ]-(p [ j ].y ) p [ j ].x ) x//不使用该方法，避免k引起的精度爆炸的lines.insert(pairdouble(k，double ) k，b ) )； }}coutlines.size(2021endl； //总直线=倾斜直线、横向直线、纵向直线return 0； (第三题)货物配置先找到解析：的所有因子，再根据因子判断总方案数。

总的直线=斜直线+横直线+竖直线2430

# include iostream # includevectorusingnamespacestd； constlonglongn=2021041820210418； int main () {vectorlong long factor； //容纳所有因子for(int

i = 1; i < sqrt(n); ++i){if (n%i == 0){factor.push_back(i);factor.push_back(n / i);}}//枚举情况int ans = 0;int len = factor.size(); //因数的总个数for (int i = 0; i < len; ++i)for (int j = 0; j < len; ++j){if(n%(factor[i]*factor[j])==0)ans += 1;}cout << ans << endl;return 0;} 第四题：路径

题解： 本题考点就是求最小公倍数和最短路径算法dijstra，不过此题也可以用dp做。

参考答案： 10266837

#include <iostream>#include<algorithm>using namespace std;typedef long long ll;const ll inf = 1e12;int vis[2050];ll e[2050][2050], dis[2050];ll gcd(ll a, ll b) //求最大公因数{return a % b == 0 ? b : gcd(b, a % b);}ll lcm(ll a, ll b)//求最小公倍数{return a * b / gcd(a, b);}int main(){fill(dis, dis + 2050, inf);fill(e[0], e[0] + 2050 * 2050, inf);for (int i = 1; i <= 2021;i++){for (int j = 1; j <= 21;j++) //21步以内有效{int k = i + j; //i为起点，k为终点if (k > 2021)break;e[i][k] = e[k][i] = lcm(i, k);}}dis[1] = 0;//最短路径模板 dijstra算法for (int i = 1; i <= 2021;i++){ll u = -1, minn = inf;for (int j = 1; j <= 2021;j++)//找到起点{if (!vis[j] && dis[j] < minn){minn = dis[j];u = j;}}if (u == -1)break;vis[u] = 1;for (int v = 1; v <= 2021;v++){if (!vis[v])dis[v] = min(dis[v], e[u][v] + dis[u]);}}cout << dis[2021];return 0;} 第五题：回路计数

第六题：时间显示

解析：

此题比较简单，需要注意两点即可完成：

注意单位转换，1天 = 24h = 24x60min = 24x60x60s = 24x60x60x1000ms显示问题，0-9要显示成00-09

参考代码：

#include<iostream>#include<sstream>#include<algorithm>using namespace std;int main(){long long num;cin >> num;long long time = num % (24 * 60 * 60 * 1000);//时钟 int HH = time / (60 * 60 * 1000);//分钟 int MM = time % (60 * 60 * 1000);MM = MM / 60000;//秒钟int SS = (time / 1000) % 60;printf("%02d:%02d:%02d", HH, MM, SS);return 0;} 第七题：砝码称重

题解： 采用动态规划，dp[i][j] 表示前 i 个物品，若能称出重量 j 则为 1 ，反之为 0

#include <iostream>#define N 102#define MAX_WEIGHT 100005using namespace std;int n, m, k, w[N], sum_weight, ans;bool dp[N][MAX_WEIGHT << 2];int main() {cin >> n;for (int i = 1; i <= n; ++i) {cin >> w[i];sum_weight += w[i];}dp[0][sum_weight * 2] = true;for (int i = 1; i <= n; ++i) {for (int j = sum_weight; j <= sum_weight * 3; ++j) {dp[i][j] = dp[i][j] || dp[i - 1][j] || dp[i - 1][j - w[i]] || dp[i - 1][j + w[i]];}}for (int i = 1; i <= sum_weight; ++i) {if (dp[n][sum_weight + i] || dp[n][sum_weight - i]) {++ans;}}cout << ans;return 0;} 第八题：杨辉三角形

题解：

#include <iostream>#include <algorithm>#define ll long long#define N 100005using namespace std;ll n, c[N], p, q;bool flag;int main() {cin >> n;if (n == 1) { //特判 1cout << 1 << endl;return 0;}c[0] = c[1] = 1;p = 1;while (c[2] < n) {++p;for (int i = p / 2 + 1; i > 0; --i) {c[i] += c[i - 1];}c[p] = 1;q = lower_bound(c, c + p / 2, n) - c;if (c[q] == n) {flag = true;break;}}if (flag) {cout<<(1 + p) * p / 2ll + q + 1ll;}else {cout<<(1 + n) * n / 2ll + 2ll;}return 0;} 第九题：双向排序

题解： 此题比较简单，关键在于灵活应用数组排序，这里可以借助STL算法中的sort()函数，进行升降序排序，非常方便！

#include <iostream>#include <vector>#include <algorithm>using namespace std;typedef long long ll;// 自定义降序排序谓词bool cmp(int a, int b){return a > b;}int main(){int n = 0; //序列长度int m = 0; //操作次数cin >> n >> m; //输入序列长度、操作次数vector<int> a;for (int i = 1; i <= n; i++)a.push_back(i); // 原数列for (int i = 0; i < m; i++){int p, q;cin >> p >> q; // 输入排序类型、参数（排序临界点）if (p == 0)sort(a.begin(), a.begin() + q, cmp); //降序elsesort(a.begin() + q - 1, a.end()); //升序}for (int i = 0; i < n;i++){cout << a[i] << " ";}return 0;} 第十题：括号序列

由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！

后续正在加紧更新中，祝你们都超常发挥！