PAT A1001-A1004

发布时间：2020-12-15 08:24:22 所属栏目：Java 来源：网络整理

导读：题集通道：https://pintia.cn/problem-sets/994805342720868352/problems/type/7 A1001 ：? A+B Format (20 point(s)) 解这道题的关键是题目所给的条件： - 10e6 = a,b = 10e6，所以a+b最多为7位数。代码如下： 1 #include cstdio 2 #include iostream 3 #

题集通道：https://pintia.cn/problem-sets/994805342720868352/problems/type/7

A1001 ：? A+B Format (20 point(s))

　　解这道题的关键是题目所给的条件： - 10e6 <= a,b <= 10e6，所以a+b最多为7位数。

　　代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 using namespace std;
 8 int main()
 9 {
10     int a,b;
11     cin >> a >> b;
12     int sum = a + b;
13     if(sum < 0)
14     {
15         cout << ‘-‘;
16         sum = -sum;
17     }
18     bool flag = false;
19     int tmpNum = sum/1000000;
20     sum%=1000000;
21     if(tmpNum > 0)    {printf("%d",tmpNum);flag = true;}
22     tmpNum = sum/1000;
23     sum%=1000;
24     if(flag) printf(",%03d",tmpNum);
25     else if(tmpNum > 0){printf("%d",tmpNum);flag = true;}
26     flag ? printf(",%03d",sum) : printf("%d",sum);
27     return 0;
28 }

View Code

A1002 ： A+B for Polynomials (25 point(s))

　　解这道题的关键是题目所给的条件：每个多项式的格式是幂逐渐减小的。

　　1.可以依次找多项式的较大项进行处理。

　　2.也可以直接建立一个容量1000的数组，把他们都当做1000项的多项式处理。

　　方法1的代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <vector>
 7 #include <algorithm>
 8 using namespace std;
 9 typedef struct NODE
10 {
11     int exp;
12     double val;
13     NODE():exp(0),val(0){}
14     NODE(int exp,double val):exp(exp),val(val){}
15 }node;
16 vector<node> poly1,poly2;
17 vector<node> resultPoly;
18 int main()
19 {
20     int n,tmpNum;
21     double tmpDouble;
22     cin >> n;
23     while(n--)
24     {
25         cin >> tmpNum >> tmpDouble;
26         poly1.push_back(NODE(tmpNum,tmpDouble));
27     }
28     cin >> n;
29     while(n--)
30     {
31         cin >> tmpNum >> tmpDouble;
32         poly2.push_back(NODE(tmpNum,tmpDouble));
33     }
34     int index1=0,index2 = 0;
35     while(index1 < poly1.size() && index2 < poly2.size())
36     {
37         if(poly1[index1].exp == poly2[index2].exp)
38         {
39             double tmpDouble = poly1[index1].val+poly2[index2].val;
40             if(tmpDouble != 0)
41                 resultPoly.push_back(NODE(poly1[index1].exp,tmpDouble));
42             index1 ++; index2 ++;
43         }
44         else
45             (poly1[index1].exp > poly2[index2].exp) ? resultPoly.push_back(poly1[index1++]) : resultPoly.push_back(poly2[index2++]);
46     }
47     while(index1 < poly1.size())    resultPoly.push_back(poly1[index1++]);
48     while(index2 < poly2.size())    resultPoly.push_back(poly2[index2++]);
49     cout << resultPoly.size();
50     for(auto it = resultPoly.begin(); it != resultPoly.end(); ++ it)
51         printf(" %d %.1f",it->exp,it->val);
52     return 0;
53 }

View Code

A1003 ： Emergency (25 point(s))

　　解这道题目的关键是：最短路径（Dijkstra）、最短路径数目（所有最短路径的上一个节点路径数之和）、最多救护人员（所有最短路径中上一个节点最多的救护人员+本节点救护人员数）

　　1.邻接矩阵存储，Dijkstra处理

　　代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <vector>
 7 #include <algorithm>
 8 using namespace std;
 9 const int INF = 0x7f7f7f7f;
10 int routeMap[510][510];
11 int dis[510]={0};
12 int assNum[510]={0};
13 int pathCnt[510]={0};
14 int assistCnt[510]={0};
15 int N,M,C1,C2;
16 void Dijkstra(int u)
17 {
18     dis[u] = 0;
19     assistCnt[u] = assNum[u];
20     pathCnt[u] = 1;
21     vector<bool> flagVec(510,false);
22     for(int i = 0; i < N; ++ i)
23     {
24         int minNum = INF,v = -1;
25         for(int j = 0; j < N; ++ j)
26             if(!flagVec[j] && dis[j] < minNum)
27             {
28                 minNum = dis[j];v = j;
29             }
30         if(v == -1)
31             break;
32         flagVec[v] = true;
33         for(int j = 0; j < N; ++ j)
34         {
35             if(!flagVec[j] && routeMap[v][j]+dis[v] < dis[j])
36             {
37                 dis[j] = routeMap[v][j]+dis[v];
38                 assistCnt[j] = assistCnt[v] + assNum[j];
39                 pathCnt[j] = pathCnt[v];
40             }
41             else if(!flagVec[j] && routeMap[v][j]+dis[v] == dis[j])
42             {
43                 pathCnt[j] += pathCnt[v];
44                 if(assistCnt[j] < assistCnt[v] + assNum[j])
45                     assistCnt[j] = assistCnt[v] + assNum[j];
46             }
47         }
48     }
49 }
50 int main()
51 {
52     cin >> N >> M >> C1 >> C2;
53     memset(routeMap,0x7f,sizeof(routeMap));
54     memset(dis,sizeof(dis));
55     int tmpSt,tmpEnd,tmpDis;
56     for(int i = 0; i < N; ++ i)
57         cin >> assNum[i];
58     for(int i = 0; i < M; ++ i)
59     {
60         cin >> tmpSt >> tmpEnd >> tmpDis;
61         routeMap[tmpSt][tmpEnd] = tmpDis;
62         routeMap[tmpEnd][tmpSt] = tmpDis;
63     }
64     Dijkstra(C1);
65     cout << pathCnt[C2] << " " << assistCnt[C2];
66     return 0;
67 }

View Code

A1003 ： Counting Leaves (30 point(s))

　　解这道题目的关键是：需要输出每层的叶子节点数。

　　注意：N为0时不处理

　 1.静态存储树，bfs

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <vector>
 7 #include <queue>
 8 #include <algorithm>
 9 using namespace std;
10 int N,M;
11 typedef struct NODE
12 {
13     vector<int> child;
14 }node;
15 vector<node> treeVec(105);
16 void Bfs(int u)
17 {
18     queue<int> bfsQue;
19     bfsQue.push(u);
20     bool symbolFlag = false;
21     while(!bfsQue.empty())
22     {
23         int len = bfsQue.size();
24         int leafCnt = 0;
25         for(int i = 0; i < len; ++ i)
26         {
27             int tmpNum = bfsQue.front();
28             bfsQue.pop();
29             if(treeVec[tmpNum].child.size() == 0)
30                 leafCnt++;
31             else
32             {
33                 for(auto it = treeVec[tmpNum].child.begin(); it != treeVec[tmpNum].child.end(); ++ it)
34                 {
35                     bfsQue.push(*it);
36                 }
37             }
38         }
39         symbolFlag ? printf(" ") : symbolFlag = true;
40         cout << leafCnt;
41     }
42 }
43 int main()
44 {
45     cin >> N >> M;
46     int tmpId,tmpChildCnt,tmpChild;
47     if(N == 0)
48         return 0;
49     for(int i = 0; i < M; ++ i)
50     {
51         cin >> tmpId >> tmpChildCnt;
52         for(int j = 0; j < tmpChildCnt; ++j)
53         {
54             cin >> tmpChild;
55             treeVec[tmpId].child.push_back(tmpChild);
56         }
57     }
58     Bfs(1);
59     return 0;
60 }

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!