题集通道：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 }
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 }
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, 0x7f, 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 }
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 }
原文：https://www.cnblogs.com/codewars/p/11343335.html
