首页 > 其他 > 详细

PAT 2018 春

时间:2019-08-17 22:53:06      阅读:102      评论:0      收藏:0      [点我收藏+]

A 1140 Look-and-say Sequence

  简单模拟。可能要注意字符串第一个字符和最后一个字符的处理。

技术分享图片
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string>
 5 #include <vector>
 6 
 7 using namespace std;
 8 string numToString(int n)
 9 {
10     string tmpStr;
11     int tmpNum;
12     while(n > 0)
13     {
14         tmpNum = n%10;
15         n /= 10;
16         tmpStr = (char)(tmpNum + 0)+tmpStr; 
17     }
18     return tmpStr;
19 }
20 int main()
21 {
22     int m, tmpNum;;
23     string tmpStr, rstStr;
24     char tmpC;
25     cin >> tmpStr >> m;
26     rstStr = tmpStr;
27     m--;
28     while(m--)
29     {
30         rstStr.clear();
31         tmpNum = 0;
32         tmpC = A;
33         for(int i = 0; i < tmpStr.size(); ++i)
34         {
35             if(tmpStr[i] != tmpC)
36             {
37                 if(i > 0)
38                     rstStr = rstStr + tmpC + numToString(tmpNum);
39                 tmpNum = 1;
40                 tmpC = tmpStr[i];
41             }
42             else
43                 tmpNum++;
44             if(i == tmpStr.size()-1)
45                 rstStr = rstStr + tmpC + numToString(tmpNum);
46         }
47         tmpStr = rstStr;
48     }
49     cout << rstStr;
50     return 0;
51 }
View Code

A 1141 PAT Ranking of Institutions

  排序题目。成绩为了尽量无误差,先按A,B,T存储,最后计算并排序。

技术分享图片
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string>
 5 #include <unordered_map> 
 6 #include <vector>
 7 
 8 using namespace std;
 9 typedef struct SCHOOLINFO
10 {
11     int score;
12     int peopleCnt;
13     int AScore, BScore, TScore;
14     string id;
15     SCHOOLINFO():AScore(0),BScore(0),TScore(0),peopleCnt(0){}
16     SCHOOLINFO(string str):AScore(0),BScore(0),TScore(0),peopleCnt(0),id(str){}
17 }schoolinfo;
18 unordered_map<string, int> schoolFlagMap;
19 vector<schoolinfo> schoolDataVec;
20 bool cmp(schoolinfo a, schoolinfo b)
21 {
22     if(a.score != b.score)
23         return a.score > b.score;
24     else if(a.peopleCnt != b.peopleCnt)
25         return a.peopleCnt < b.peopleCnt;
26     else 
27         return a.id < b.id;
28 }
29 void strToLower(string &tmpStr)
30 {
31     for(int i = 0; i < tmpStr.size(); ++ i)
32     {
33         if(tmpStr[i] <= Z && tmpStr[i] >= A)
34             tmpStr[i] = tmpStr[i]-A+a;
35     }
36 }
37 int main()
38 {
39     int n, index = 1, tmpNum;
40     string tmpId, tmpSchool;
41     int tmpScore;
42     cin >> n;
43     while(n--)
44     {
45         cin >> tmpId >> tmpScore >> tmpSchool;
46         strToLower(tmpSchool);
47         if(schoolFlagMap[tmpSchool] == 0)
48         {
49             schoolFlagMap[tmpSchool] = index++;
50             schoolDataVec.push_back(SCHOOLINFO(tmpSchool));
51         }
52         tmpNum = schoolFlagMap[tmpSchool]-1;
53         schoolDataVec[tmpNum].peopleCnt++;
54         if(tmpId[0] == T)
55             schoolDataVec[tmpNum].TScore += tmpScore;
56         else if(tmpId[0] == A)
57             schoolDataVec[tmpNum].AScore += tmpScore;
58         else
59             schoolDataVec[tmpNum].BScore += tmpScore;
60     }
61     for(auto it = schoolDataVec.begin(); it != schoolDataVec.end(); ++it)
62         it->score = it->AScore + it->BScore/1.5 + it->TScore*1.5;
63     sort(schoolDataVec.begin(), schoolDataVec.end(), cmp);
64     int tmpTWS = -1, rankCnt = 0;
65     cout << schoolDataVec.size() << endl;
66     for(int i = 0; i < schoolDataVec.size(); ++i)
67     {
68         schoolinfo tmpSchool = schoolDataVec[i];
69         if(tmpSchool.score != tmpTWS)
70             rankCnt = i+1;  
71         cout << rankCnt << " " << tmpSchool.id << " " <<tmpSchool.score << " " <<tmpSchool.peopleCnt << endl;
72         tmpTWS = schoolDataVec[i].score;
73     }
74     return 0;
75 }
View Code

A 1142 Maximal Clique

  读懂题目就行,写一个判断是否与所给的其它各点连通的函数。

技术分享图片
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string>
 5 #include <unordered_map> 
 6 #include <vector>
 7 
 8 using namespace std;
 9 #define MAX_SIZE 210
10 int route[MAX_SIZE][MAX_SIZE]={0};
11 int Nv, Ne, M;
12 vector<int> cliqueVec;
13 bool judge(int u)
14 {
15     for(auto it = cliqueVec.begin(); it != cliqueVec.end(); ++it)
16     {
17         if(*it == u)
18             continue;
19         if(route[*it][u] == 0)
20             return false;
21     }
22     return true;
23 }
24 int main()
25 {
26     cin >> Nv >> Ne;
27     int tmpSt, tmpEnd, tmpCnt, tmpNum;
28     for(int i = 1; i <= Ne; ++i)
29     {
30         cin >> tmpSt >> tmpEnd;
31         route[tmpSt][tmpEnd] = 1;
32         route[tmpEnd][tmpSt] = 1;
33     }
34     cin >> M;
35     while(M--)
36     {
37         cin >> tmpCnt;
38         bool dealFlag = false;
39         vector<int> visitFlag(Nv+1, 0);
40         cliqueVec.resize(tmpCnt,0);
41         for(int i = 0; i < tmpCnt; ++i)
42         {
43             cin >> cliqueVec[i];
44             visitFlag[cliqueVec[i]] = 1;
45         }
46         for(auto it = cliqueVec.begin(); it != cliqueVec.end(); ++it)
47             if(!judge(*it))
48                 dealFlag = true;
49         if(dealFlag)
50         {
51             cout << "Not a Clique" << endl;
52             continue;
53         }
54         for(int i = 1; i <= Nv; ++i)
55             if(visitFlag[i] == 0 && judge(i))
56                 dealFlag = true;
57         if(dealFlag)
58         {
59             cout << "Not Maximal" <<endl;
60             continue;
61         }
62         cout << "Yes" << endl;
63     }
64     return 0;
65 }
View Code

A 1143 Lowest Common Ancestor

  这道题目,深刻理解树的前序遍历和BST的话,是道比较水的题目。

技术分享图片
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string>
 5 #include <unordered_map> 
 6 #include <vector>
 7 
 8 using namespace std;
 9 vector<int> treeKeyVec(10010);
10 unordered_map<int, int> keyValMap;
11 int M, N;
12 void findLCA(int a, int b)
13 {
14     for(int i = 0; i <N; ++i)
15     {
16         int tmpNum = treeKeyVec[i];
17         bool flag = false;
18         if(tmpNum == a)
19             printf("%d is an ancestor of %d.\n", a, b);
20         else if(tmpNum == b)
21             printf("%d is an ancestor of %d.\n", b, a);
22         else if(tmpNum < max(a,b) && tmpNum > min(a,b))
23             printf("LCA of %d and %d is %d.\n", a, b, tmpNum);
24         else
25             flag = true;
26         if(!flag)
27             return;
28     }
29 }
30 int main()
31 {
32     cin >> M >> N;
33     int tmpNum;
34     for(int i = 0; i < N; ++i)
35     {
36         cin >> tmpNum;
37         keyValMap[tmpNum] = 1;
38         treeKeyVec[i] = tmpNum;
39     }
40     int tmpNum1, tmpNum2;
41     for(int i = 0; i < M; ++i)
42     {
43         cin >> tmpNum1 >> tmpNum2;
44         bool flag1 = true, flag2 = true;
45         if(keyValMap[tmpNum1] == 0)
46             flag1 = false;
47         if(keyValMap[tmpNum2] == 0)
48             flag2 = false;
49         if(!flag1 && !flag2)
50             printf("ERROR: %d and %d are not found.\n", tmpNum1, tmpNum2);
51         else if(!flag1)
52             printf("ERROR: %d is not found.\n", tmpNum1);
53         else if(!flag2)
54             printf("ERROR: %d is not found.\n", tmpNum2);
55         else
56             findLCA(tmpNum1, tmpNum2);
57     }
58     return 0;
59 }
View Code

 

PAT 2018 春

原文:https://www.cnblogs.com/codewars/p/11370488.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!