蓝桥杯刷题冲刺 | 倒计时10天

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

1.有边数限制的最短路

• 题目

  链接： 853. 有边数限制的最短路 - AcWing题库

  给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

  请你求出从 11 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

  注意：图中可能 存在负权回路 。

  输入格式

  第一行包含三个整数 n,m,k。

  接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

  点的编号为 1∼n。

  输出格式

  输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

  如果不存在满足条件的路径，则输出 impossible。

  数据范围

  1≤n,k≤500,
  1≤m≤10000,
  1≤x,y≤n，
  任意边长的绝对值不超过 10000。

  输入样例：

  3 3 1
  1 2 1
  2 3 1
  1 3 3
  

  输出样例：

  3
  

• 我的题解

  #include<bits/stdc++.h>
  using namespace std;const int N=510,M=10010;int n,m,k;
  int dist[N];
  int backup[N];struct node{int a,b,c;
  }g[N];int Bellman()
  {memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<k;i++){memcpy(backup,dist,sizeof dist);for(int j=0;j<m;j++){int a=g[j].a,b=g[j].b,w=g[j].c;dist[b]=min(dist[b],backup[a]+w);}}if(dist[n]>0x3f3f3f3f/2) return 0x3f3f3f3f/2+1;return dist[n];
  }int main()
  {scanf("%d%d%d",&n,&m,&k);for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);g[i]={a,b,c};}int t=Bellman();if(t>0x3f3f3f3f/2)   puts("impossible");else cout<<t;    return 0;
  }
  

2.九进制转十进制

• 题目

  链接： 九进制转十进制 - 蓝桥云课 (lanqiao.cn)

  本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

  九进制正整数 (2022)${}_9$ 转换成十进制等于多少？

• 我的题解1 AC 100%

  #include<bits/stdc++.h>
  using namespace std;int main()
  {string s="2022";int x=stoi(s,0,9);  //将n进制的字符串转化为十进制cout<<x;return 0;
  }
  

• 我的题解2 ——第一次 AC 0%

  #include<bits/stdc++.h>
  using namespace std;int main()
  {int n=2022;int res=0;while(n>0){int t=n%10;n/=10;res=res*9+t;cout<<res<<endl; }cout<<res;return 0;
  }
  

  这样计算的话，就反了，计算的是 2202的十进制

  第二次 AC 100%

  #include<bits/stdc++.h>
  using namespace std;int main()
  {string s="2022";int res=0;for(int i=0;i<=s.size()-1;i++)  //借助于字符串{res=res*9+s[i]-'0';}cout<<res;return 0;
  }
  

• 反思

  进制转化问题：

  1. 填空题直接借助于计算器
  2. 编程，注意累乘的进位的顺序，别整反了；使用字符串来储存数字
  3. '0’是字符0的意思，他所对应的ASCII码为48；而0是数字0，ASCII中的0

• ASCII 转换公式 ps 补充一下，以防以后遇到

  	0-9	A-Z	a-z
  ASCII码值	48-57	65-90	97-122

  • ASCII码值大小：数字<大写字母<小写字母
  • 以上三种ASCII码因为都是连续的，所以都可以加相应的数从而得到之后的ASCII码值
  • 小写转大写：小写字母 - ‘a’ + ‘A’
  • 大写转小写：大写字母 - ‘A’ + ‘a’
  • 小写转数字：小写字母 - ‘a’ + ‘0’
  1. 原值减去 原对应类型的第一个值 (置零)；
  2. 然后加上 所求类型的第一个值的ASCII。