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

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

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<<'*';
          else
              cout<<i<<'^'<<s<<'*';
              
         
      }
       if(n>1)
          cout<<n;
  }
  
  
  int main()
  {
      ll n;
      cin>>n;
      
      cout<<n<<"=";
      
      if(n==1)
          cout<<n<<endl;
      else
          f(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个3f
      else cout<<dist[i]<<" ";
  	
  	return 0;
   } 
  

• 反思

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

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

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

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