PAT 1001-1004

1001 A+B Format

分析:

基础题

在处理正负号问题上要注意下，可以借鉴计算机组成原理中浮点数符号的处理的思想——单独讨论符号

代码:

/*
    Author:HWL   
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    int c = abs(a+b);
    //处理digits
    /*
        1.转成字符串 使用string的相关函数 
        2.手动专成字符串 
    */  
    
    //1.使用string相关函数
    string str = to_string(c);  
    if(a+b<0)
        cout<<"-";          
    int len = str.size();
    for(int i=0;i<len%3;i++)
        cout<<str[i];
    if(len%3>0&&len>3)
        cout<<",";      
    for(int i=0;i<len-len%3;i++)
    {
        cout<<str[i+len%3];             
        if((i+1)%3==0&&(i+len%3)!=len-1)
            cout<<",";          
    }   
    
    //2.手动转
//  char str[30];
//  int cnt = 0;
//  int x = 0;  
//  if(c==0)
//  {
//      cout<<0<<endl;
//      return 0;       
//  }       
//  while(c)
//  {               
//      str[cnt++] = c%10+'0';
//      if((x+1)%3==0&&c/10!=0)
//          str[cnt++]=',';
//      x++;            
//      c/=10;
//  }           
//  char ans[30];   
//  int j=0;    
//  for(int i=cnt-1;i>=0;i--)
//      ans[j++]=str[i];
//  ans[j]='\0';
//  if(a+b<0)
//      cout<<"-";
//  cout<<ans<<endl;        
    return 0;
}

1002 A+B for Polynomials

分析:

基础题
注意项系数为0的情况，也注意浮点数判0的方法(这题==也可以过)

代码:

/*
    Author:HWL   
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    //下标是幂，值为系数 
    double A[2001];
    double B[2001];
    
    int vis[2001]={0};//标志哪个下标有效        
    int sum = 0;
    int k;
        
    cin>>k; 
    while(k--)
    {
        int expo;
        double coef;        
        cin>>expo>>coef;
        A[expo]=coef;
        if(!vis[expo])  
            sum++;
        vis[expo]=1;
    }
    cin>>k;
    while(k--)
    {
        int expo;
        double coef;        
        cin>>expo>>coef;
        B[expo]=coef;
        if(!vis[expo])  
            sum++;
        else{
            if(fabs(A[expo]+B[expo])<0.000000001)
                sum--;
        }
        vis[expo]=1;        
    }           
    cout<<sum;
    for(int i=2000;i>=0;i--)    
    {       
        if(vis[i])
        {   
            if(fabs(A[i]+B[i])<0.000000001)
                continue;
            cout<<" "<<i<<" ";
            printf("%.1f",A[i]+B[i]);
        }
    }
    return 0;
    
}

1003 Emergency

分析

考察点:图的遍历(DFS)
图的存储:邻接矩阵

这题用DFS就可以过，有几个地方注意:
1.用剪枝的方式，快速筛掉不必要的递归
2.如果想要进一步优化时间，可以用邻接表来存储图
3."在相同最短路径下找最大的"类型题可以用的技巧：
请看代码递归原子操作的部分

时间复杂度:O(n2)
空间复杂度:O(n2)

代码

/*
    Author:HWL   
*/
#include<bits/stdc++.h>
using namespace std;
int mincost = 100000000;
int maxres = 0;
int sum = 0;
int resteam[501];
int mat[501][501];//邻接矩阵 
int vis[501] = {0};

void dfs(int start,int end,int cost,int resnum)
{
    if(start==end)
    {       
        if(cost==mincost)
        {
            //相同最短路径下找最大的救援，并且最短路的种数加一 
            sum++;
            maxres = max(maxres,resnum);
        }       
        else if(cost<mincost)   
            {
                //最短路发生更新，则种数和最大救援都要更新 
                sum = 1;                
                mincost = cost;
                maxres = resnum;
            }               
    }
    for(int i=0;i<500;i++)
    {
        if(mat[start][i]!=100000000&&!vis[i])
        {
            if(mat[start][i]+cost>mincost)
                continue;   //这里做一个剪枝，不然会有一个case超时 
            vis[i]=1;
            dfs(i,end,cost+mat[start][i],resnum+resteam[i]);
            vis[i]=0;   //注意回溯这一步  
        }
    }
    
}
int main(){
    
    for(int i=0;i<501;i++) 
        for(int j=0;j<501;j++)
            mat[i][j]=100000000;
    int n,m,c1,c2;
    cin>>n>>m>>c1>>c2;
    
    for(int i=0;i<n;i++)
        cin>>resteam[i];
        
    for(int i=0;i<m;i++)
    {
        int f,t,c;//from,to,cost
        cin>>f>>t>>c;       
        mat[f][t]=c;
        mat[t][f]=c;//注意是无向图        
    }   
    dfs(c1,c2,0,resteam[c1]);
    cout<<sum<<" "<<maxres<<endl;
}

1004 Counting Leaves

分析

考察点:
树的层次遍历，使用BFS即可
基础题

代码:

/*
    Author:HWL   
*/
#include<bits/stdc++.h>
using namespace std;
struct node{
    vector<int> child;
};
int main(){
    int n,m;
    cin>>n>>m;
    if(n==0)
        return 0;
    vector<node> nodes(100);    
    while(m--)  
    {
        int root,num;
        cin>>root>>num;     
        while(num--)
        {
            int tmp2;
            cin>>tmp2;          
            nodes[root].child.push_back(tmp2);          
        }                   
    }
    vector<int> ans;
    int leaf_num=0; //某层的叶子节点数目 
    //BFS
    queue<node> q;
    q.push(nodes[1]);
    int floor = 1;  //第1层    
    int number = 1; //某层的节点数 
    while(!q.empty())
    {
        node tmp = q.front();
        q.pop();
        number--;       
        if(tmp.child.size()==0)
        {
            leaf_num++;
        }
        for(int i=0;i<tmp.child.size();i++)         
        {
            q.push(nodes[tmp.child[i]]);
        }
        if(number==0)
        {                
            floor++; //切换到下一层
            ans.push_back(leaf_num);
            leaf_num=0; 
            number = q.size();  
        }                                   
    }   
            
    cout<<ans[0];
    for(int i=1;i<ans.size();i++)       
        cout<<" "<<ans[i];
    return 0;
}