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 }
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 }
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 }
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 }
原文:https://www.cnblogs.com/codewars/p/11370488.html