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

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

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

1.质因子

• 题目

  链接： 1545. 质因子 - AcWing题库

  给定一个整数 N，找出它的所有质因子，并按如下格式输出：

  N=$p{1}^{k1}\ast p{2}^{k2}\ast ...\ast p{m}^{km}$

  注意: 如果 N=1 则输出 1=1。

  输入格式

  一个整数 N。

  输出格式

  输出时，按 N=p1^k1*p2^k2*...*pm^km 的格式输出答案。

  其中 pi 是质因子，应按照递增顺序排列，ki 是 pi 的指数，如果 ki 为 1，则不必输出。

  数据范围

  1≤N≤$2^{31}$−1

  输入样例：

  97532468
  

  输出样例：

  97532468=2^2*11*17*101*1291
  

• 第一次 AC 90%

  #include<bits/stdc++.h>
  using namespace std;typedef long long ll;void f(int n)
  {for(int i=2;i<=n/i;i++){int s=0;while(n%i==0){n/=i;s++;}if(s==0)continue;if(s==1) cout<<i<<'*';elsecout<<i<<'^'<<s<<'*';}if(n>1)cout<<n;
  }int main()
  {ll n;cin>>n;cout<<n<<"=";if(n==1)cout<<n<<endl;elsef(n);return 0;
  }
  

  第一次的符号输出有问题

• 题解

  #include<bits/stdc++.h>
  using namespace std;int main()
  {long long n;cin>>n;if(n==1)  //特判{cout<<"1=1";return 0;}cout<<n<<"=";bool first_use =1;  //解决符号问题for(long long i=2;i<=n/i;i++)  //分解质因子的模板{  if(n%i==0)  //注意这里需要判断，再s=0{int s=0;while(n%i==0){n/=i;s++;}if(first_use) first_use=0;  //符号这里要注意else cout<<'*';cout<<i;if(s>1) cout<<'^'<<s;}}if(n>1)if(first_use)cout<<n;else cout<<'*'<<n;return 0;
  }
  

• 反思

  1. 数据范围复习

     unsigned int	0～4294967295 (10位数，4e9)
     int	-2147483648～2147483647 (10位数，2e9 $2^{31}$-1)
     long long	-9223372036854775808～9223372036854775807 (19位数， 9e18 ) $2^{63}$-1
     unsigned long long	0～18446744073709551615 (20位数，1e19) $2^{64}$ - 1

     其实，这个题我试了试 不用 long long 也能 AC

     但是 考试的时候 还是 long long 吧，万一越界了呢 ，我胆小

  2. 这个题输出带有运算符号

     第一次，我都整晕了，没有想起来有 flag 来标记第一个+* 带在每一质因子的前面，一直想的是*带在后面，想了好久，最后一个怎么不带 这个符号 T-T

     • 输出技巧：使用 flag 标记第一个数，符号带在数的前面（说的有点抽象，结合上面这个题理解）
     • 使用 多个 if else 来判断条件，是否输出相对应的符号

2.蓝桥王国

• 题目

  链接： 蓝桥王国 - 蓝桥云课 (lanqiao.cn)

  小明是蓝桥王国的王子，今天是他登基之日。

  在即将成为国王之前，老国王给他出了道题，他想要考验小明是否有能力管理国家。

  题目的内容如下：

  蓝桥王国一共有 N 个建筑和 M 条单向道路，每条道路都连接着两个建筑，每个建筑都有自己编号，分别为 1∼N 。（其中皇宫的编号为 1）

  国王想让小明回答从皇宫到每个建筑的最短路径是多少，但紧张的小明此时已经无法思考，请你编写程序帮助小明回答国王的考核。

  输入描述

  输入第一行包含三个正整数N,M。

  第 2 到 M+1 行每行包含三个正整数 u,v,w，表示 u→v 之间存在一条距离为 w 的路。

  1≤N≤3×$10^5$，1≤m≤$10^6$，1≤ui, vi≤N，0≤wi≤$10^9$ 。

  输出描述

  输出仅一行，共 N 个数，分别表示从皇宫到编号为 1∼N 建筑的最短距离，两两之间用空格隔开。（如果无法到达则输出 −1）

  输入输出样例

  示例 1

  输入

  3 3 
  1 2 1
  1 3 5
  2 3 2
  

  输出

  0 1 3
  

• 第一次 AC 0%

  #include<bits/stdc++.h>
  using namespace std;const int N=3*1e2+10,M=1e6+10;int n,m;
  bool st[N];
  int g[N][N];
  int dist[N];void dijkstra()
  {memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=1;i<=n;i++){int t=-1;for(int j=1;i<=n;j++)if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;st[t]=true;for(int j=1;j<=n;j++){dist[j]=min(dist[j],dist[t]+g[t][j]);	}}	}int main()
  {	scanf("%d%d",&n,&m);memset(g,0x3f,sizeof g);while(m--){int a,b,w;scanf("%d%d%d",&a,&b,&w);g[a][b]=min(g[a][b],w);}dijkstra();for(int i=1;i<=n;i++)if(dist[i]==0x3f3f3f3f)	cout<<-1;else cout<<dist[i]<<' ';return 0;
  }
  

  没输出

• 第二次 AC 50%

  #include<bits/stdc++.h>
  using namespace std;typedef pair<int,int> PII;const int N=3*1e5+10;int n,m;
  int h[N],e[N],w[N],ne[N],idx;
  bool st[N];
  int dist[N];void add(int a,int b,int c)
  {e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
  }void dijkstra()
  {memset(dist,0x3f,sizeof dist);dist[1]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,1});while(heap.size()){auto t=heap.top();heap.pop();int vis=t.second,distance=t.first;if(st[vis])continue;st[vis]=1;for(int i=h[vis];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>distance+w[i]){dist[j]=distance+w[i];heap.push({dist[j],j});}}}
  }int main()
  {scanf("%d%d",&n,&m);memset(h,-1,sizeof h);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}dijkstra();for(int i=1;i<=n;i++)if(dist[i]==0x3f3f3f3f) cout<<-1<<' ';else cout<<dist[i]<<' ';return 0;} 
  

• 第三次 AC 100%

  #include<bits/stdc++.h>
  using namespace std;typedef long long ll;typedef pair<long long,int> PII;const int N=5*1e5+10;ll n,m;
  ll h[N],e[N],w[N],ne[N],idx;
  bool st[N];
  ll dist[N];void add(ll a,ll b,ll c)
  {e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
  }void dijkstra()
  {memset(dist,0x3f,sizeof dist);dist[1]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,1});while(heap.size()){auto t=heap.top();heap.pop();ll vis=t.second;long long distance=t.first;if(st[vis])continue;st[vis]=1;for(ll i=h[vis];i!=-1;i=ne[i]){ll j=e[i];if(dist[j]>distance+w[i]){dist[j]=distance+w[i];heap.push({dist[j],j});}}}
  }int main()
  {scanf("%lld%lld",&n,&m);memset(h,-1,sizeof h);while(m--){ll a,b,c;scanf("%lld%lld%lld",&a,&b,&c);add(a,b,c);}dijkstra();for(ll i=1;i<=n;i++)if(dist[i]>=0x3f3f3f3f3f3f3f3f) cout<<-1<<' ';   //long long 需要 8个3felse cout<<dist[i]<<" ";return 0;} 
  

• 反思

  1. 第一次直接用错模板了

     朴素版的模板用于稠密图（矩阵存），堆优化版用于稀疏图（邻接表存）

     m是 $10^5$ 级别的话就是稠密图，m是n级别的就是稀疏图

  ps数组元素个数不能太多，一开始用的 1e5 ，编译过不去