PAT甲级C++总结（一）

﹏ヽ暗。殇╰゛Y 2022-01-27 14:37 225阅读 0赞

1.min和max：返回a和b的最小值或最大值，有三个参数，前两个必需，为比较的参数，第三个为比较的方法，使用时需要加上头文件algorithm

2.C/C++，用0x3f3f3f3f表示无穷大，0xc0c0c0c0表示无穷小

3.dijk最短路径算法：(懒得解释，直接上代码）

#include<iostream>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    const int N=100,INF=0x3f3f3f3f;
    int m,n,c;//m为点数目,n为线的数目,c为起点
    int map[N][N],vis[N],dis[N];//map为各点之间的权值数组,vis用于判断点是否用过,dis为起点到目标点的最短距离数组
    
    void dijk(int c){
        dis[c]=0;//起点到起点的距离为0
        for(int i=0;i<m;i++){//循环n次每次加一个点，每次加入的点都是已更新完成的点
            int v=-1;
            for(int j=0;j<m;j++){
                //每次都遍历所有的点，从没加入图中的点中选一个到原点距离最小的点，加入图中
                if(!vis[j]&&(v==-1||dis[j]<dis[v])){
                    v=j;
                }
            }
            vis[v]=1;
            for(int j=0;j<m;j++){//进行松弛操作
                dis[j]=min(dis[j],dis[v]+map[v][j]);
            }
        }
        return ;
    }
    
    int main(){
        cin>>m>>n>>c;
        memset(dis,INF,sizeof(dis));
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                if(i==j){
                    map[i][j]=0;
                }else{
                    map[i][j]=INF;
                }
            }
        }
        for(int i=0;i<n;i++){
            int a,b,d;
            cin>>a>>b>>d;
            map[a][b]=d;
            map[b][a]=d;
        }
        dijk(c);
        return 0;
    }

4.如果需要调用函数的过程中对参数的改变保留下来，需要使用指针作为函数参数：

void doubleValue(int *val)
    {
       *val *= 2;
    }
    int main(){
    	int val;
    	doubleValue(&val);
    	return 0；
    }

如果直接使用函数参数，不会对参数本身造成影响

5.C语言判断溢出一般判断是否突然小于0即可，题目一些坑点在于整型变量本身并没有超过int范围，但是有一些运算中比如相加超过了int的范围，要注意

6.二分法查找，可以减少遍历的次数，每次比较开始和结束的中间值，通过对比中间值和查找值的大小来反复更改开始和结束值

long long int left=max+1,right=res1+1;
        while(left<=right){
            long long int mid=(left+right)/2;
            res2=toDecimal(a,mid);
            if(res2==res1){
                cout<<mid;
                flag=1;
                break;
            }else if(res2>res1||res2<0){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }

7.n个互相独立的连通分量组成一个连通图，只需要连n-1条线就可以

8.深度优先遍历dfs获取图的连通分量的数量：  
用矩阵v\[i\]\[j\]表示图的边，1为有，0为没有；用visit表示图的点是否已经经过

void dfs(int node){
    	visit[node]=true;
    	for(int i=0;i<n;i++){
    	if(visit[n]==false&&v[node][i]=1){
    	dfs(i);
    	}
    	}
    
    
    int main(){
    ...
    int cnt=0;//连通分量的数量
    for(int i=0;i<n;i++）{
    if(visit[i]==false){
    dfs(i);//每次dfs运行到结束，将会将某个连通分量的所有点的visit数组值设置为true，即遍历完一个连通分量
    cnt++;
    }
    ...
    return 0；

9.通过树的两种遍历获得另外的遍历，参考柳神的代码：  
[https://blog.csdn.net/liuchuo/article/details/52137796][https_blog.csdn.net_liuchuo_article_details_52137796]

[https_blog.csdn.net_liuchuo_article_details_52137796]: https://blog.csdn.net/liuchuo/article/details/52137796