首页 > 代码库 > 【PAT-A】解题报告
【PAT-A】解题报告
当你无聊的时候...可以考一考PAT...什么的...嗯
========================我是日常分割线===========================
1010. Radix (25)
1 /* 2 date:2016-09-05 3 author:CheerM 4 title:Radix(25) 5 6 题目描述: 7 Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is "yes", if 6 is a decimal number and 110 is a binary number. 8 9 Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given. 10 11 Input Specification: 12 13 Each input file contains one test case. Each case occupies a line which contains 4 positive integers: 14 N1 N2 tag radix 15 Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set {0-9, a-z} where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number "radix" is the radix of N1 if "tag" is 1, or of N2 if "tag" is 2. 16 17 Output Specification: 18 19 For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print "Impossible". If the solution is not unique, output the smallest possible radix. 20 21 Sample Input 1: 22 6 110 1 10 23 Sample Output 1: 24 2 25 Sample Input 2: 26 1 ab 1 2 27 Sample Output 2: 28 Impossible 29 30 解题思路:主要是进制转换,找出基底的上界下界,然后二分查找遍历可能的基底 31 32 1. 基底的下界:基底一定不能小于数字中出现的最大单位数 33 2. 基底的上届:当两个数字均不为零,且所找数字最小(==1)时,也有相等的可能,基底应该==另一个数字的10进制值 34 e.g. 99 1 1 10 则应该上界取99, 以99为基底时 有 99(10)== 1(99) 35 36 3. 注意超时!!!!!!(仔细看题,不超过10位的digits),不要递归 37 38 4. 注意循环边界、不重复也不要漏掉(不然会无限循环、答案错误) TAT自己挖的bug,哭着也要填完...打个草稿是多重要... 39 */ 40 41 #define _CRT_SECURE_NO_DEPRECATE 42 43 #include <iostream> 44 #include <cstdio> 45 #include <cstring> 46 47 using namespace std; 48 49 char n1[11], n2[11]; 50 51 //任意基底转10进制数 52 long long turnIntoRadix(const char* n, long long len, long long radix) { 53 long long result = 0, count = 0; 54 while (count < len) 55 { 56 int temp; 57 if (n[count] >= ‘0‘ && n[count] <= ‘9‘) temp = n[count] - ‘0‘; 58 else temp = n[count] - ‘a‘ + 10; 59 60 result = result * radix + temp; 61 count++; 62 63 if (result < 0) return -1; 64 } 65 return result; 66 } 67 68 //获取基底下界,即另一整数中单位最大数 69 long long getMinR(const char* n, long long len) { 70 long long count = len, maxR = 0; 71 while (count --) 72 { 73 int temp; 74 if (n[count] >= ‘0‘ && n[count] <= ‘9‘) temp = n[count] - ‘0‘; 75 else temp = n[count] - ‘a‘ + 10; 76 77 maxR = maxR > temp ? maxR : temp; 78 } 79 return maxR; 80 } 81 82 //遍历基底查找 83 void checkRadix(long long n1, const char* n2, long long len2, long long minR, long long maxR) { 84 if (maxR < minR) { 85 printf("Impossible\n"); 86 return; 87 } 88 89 //取中间基底二分查找 90 long long medR = minR + (maxR - minR) / 2; 91 long long result = 0; 92 bool flag = false; 93 while (minR <= maxR) 94 { 95 result = turnIntoRadix(n2, len2, medR); 96 if (result > n1 || result == -1) { 97 maxR = medR - 1; 98 medR = minR + (maxR - minR) / 2; 99 }100 else if (result == n1) {101 flag = true;102 break;103 }104 else {105 minR = medR + 1;106 medR = minR + (maxR - minR) / 2;107 }108 }109 110 if (flag) printf("%lld\n", medR);111 else printf("Impossible\n");112 113 return;114 }115 116 int main() {117 long long tag, radix, len1, len2;118 scanf("%s %s %lld %lld", n1, n2, &tag, &radix);119 120 len1 = strlen(n1), len2 = strlen(n2);121 122 long long first, second, maxR, minR;123 if (tag == 1) {124 first = turnIntoRadix(n1, len1, radix);125 maxR = first + 1;126 minR = getMinR(n2, len2) + 1;127 checkRadix(first, n2,len2, minR, maxR);128 }129 else {130 second = turnIntoRadix(n2, len2, radix);131 maxR = second + 1;132 minR = getMinR(n1, len1) + 1;133 checkRadix(second, n1, len1, minR, maxR);134 }135 136 system("pause");137 return 0;138 }
1026. Table Tennis (30)
部分正确...待修改...
1 /* 2 date: 2016-09-06 3 author: CheerM 4 title: Table Tennis (30) 5 待修改,部分正确(19/30) 6 7 题目描述: 8 A table tennis club has N tables available to the public. The tables are numbered from 1 to N. For any pair of players, if there are some tables open when they arrive, they will be assigned to the available table with the smallest number. If all the tables are occupied, they will have to wait in a queue. It is assumed that every pair of players can play for at most 2 hours. 9 10 Your job is to count for everyone in queue their waiting time, and for each table the number of players it has served for the day. 11 12 One thing that makes this procedure a bit complicated is that the club reserves some tables for their VIP members. When a VIP table is open, the first VIP pair in the queue will have the priviledge to take it. However, if there is no VIP in the queue, the next pair of players can take it. On the other hand, if when it is the turn of a VIP pair, yet no VIP table is available, they can be assigned as any ordinary players. 13 14 Input Specification: 15 16 Each input file contains one test case. For each case, the first line contains an integer N (<=10000) - the total number of pairs of players. Then N lines follow, each contains 2 times and a VIP tag: HH:MM:SS - the arriving time, P - the playing time in minutes of a pair of players, and tag - which is 1 if they hold a VIP card, or 0 if not. It is guaranteed that the arriving time is between 08:00:00 and 21:00:00 while the club is open. It is assumed that no two customers arrives at the same time. Following the players‘ info, there are 2 positive integers: K (<=100) - the number of tables, and M (< K) - the number of VIP tables. The last line contains M table numbers. 17 18 Output Specification: 19 20 For each test case, first print the arriving time, serving time and the waiting time for each pair of players in the format shown by the sample. Then print in a line the number of players served by each table. Notice that the output must be listed in chronological order of the serving time. The waiting time must be rounded up to an integer minute(s). If one cannot get a table before the closing time, their information must NOT be printed. 21 22 Sample Input: 23 9 24 20:52:00 10 0 25 08:00:00 20 0 26 08:02:00 30 0 27 20:51:00 10 0 28 08:10:00 5 0 29 08:12:00 10 1 30 20:50:00 10 0 31 08:01:30 15 1 32 20:53:00 10 1 33 3 1 34 2 35 Sample Output: 36 08:00:00 08:00:00 0 37 08:01:30 08:01:30 0 38 08:02:00 08:02:00 0 39 08:12:00 08:16:30 5 40 08:10:00 08:20:00 10 41 20:50:00 20:50:00 0 42 20:51:00 20:51:00 0 43 20:52:00 20:52:00 0 44 3 3 2 45 46 */ 47 48 49 #include <iostream> 50 #include <algorithm> 51 #include <vector> 52 #include <string> 53 54 using namespace std; 55 56 //将数字转化为字符串时间 57 string turnIntoStr(int hh, int mm, int ss) { 58 string result = ""; 59 60 result.push_back(hh / 10 + ‘0‘); 61 result.push_back(hh % 10 + ‘0‘); 62 result.push_back(‘:‘); 63 result.push_back(mm / 10 + ‘0‘); 64 result.push_back(mm % 10 + ‘0‘); 65 result.push_back(‘:‘); 66 result.push_back(ss / 10 + ‘0‘); 67 result.push_back(ss % 10 + ‘0‘); 68 69 return result; 70 } 71 72 //时间变化 73 string addTime(const string& time, int min) { 74 //转成时间 75 int hh, mm, ss; 76 hh = (time[0] - ‘0‘) * 10 + time[1] - ‘0‘; 77 mm = (time[3] - ‘0‘) * 10 + time[4] - ‘0‘; 78 ss = (time[6] - ‘0‘) * 10 + time[7] - ‘0‘; 79 80 hh = ((mm + min) / 60 + hh) % 24; 81 mm = (mm + min) % 60; 82 83 return turnIntoStr(hh, mm, ss); 84 } 85 86 typedef struct Table{ 87 Table(int sn, int st, bool v) { 88 serveNum = sn; 89 serveTime = st; 90 isVIP = v; 91 } 92 int serveNum; 93 int serveTime; 94 bool isVIP; 95 }; 96 97 typedef struct Client{ 98 Client(string& at, int ut) { 99 arriveTime = at;100 useTime = ut;101 waitTime = 0;102 }103 //到达时间104 string arriveTime;105 int useTime;106 //算秒数107 int waitTime;108 };109 110 bool compare(const Client& A,const Client& B) {111 return A.arriveTime < B.arriveTime;112 }113 114 //客人的到达时间是否超出营业时间115 bool isOverTime(const string& time, int min) {116 if (time < "08:00:00") return true;117 string result = addTime(time, min);118 if (result > "21:00:00") return true;119 return false;120 }121 122 //四舍五入123 int wtime(int waitTime) {124 return (waitTime + 30) / 60;125 }126 127 int waitForNextClient(string& now, string& next) {128 int t1[3] = { 0, 0, 0 }, t2[3] = {0, 0, 0};129 for (int i = 0, count = 0; i < now.size(); i++) {130 if (now[i] >= ‘0‘ && now[i] <= ‘9‘) t1[count] = t1[count] * 10 + now[i] - ‘0‘;131 else count++;132 }133 for (int i = 0, count = 0; i < now.size(); i++) {134 if (next[i] >= ‘0‘ && next[i] <= ‘9‘) t2[count] = t2[count] * 10 + next[i] - ‘0‘;135 else count++;136 }137 return (t2[0] - t1[0]) * 3600 + (t2[1] - t1[1]) * 60 + t2[2] - t1[2];138 }139 140 int main() {141 vector<Table> table;142 vector<Client> ordinary, vip;143 144 int t, ut, n, m;145 string str;146 bool vipflag;147 cin >> t;148 while (t--) {149 cin >> str >> ut >> vipflag;150 if (vipflag) vip.push_back(Client(str, ut * 60));151 else ordinary.push_back(Client(str, ut * 60));152 }153 154 //按到达时间把顾客排序155 sort(vip.begin(), vip.end(), compare);156 sort(ordinary.begin(), ordinary.end(), compare);157 158 //输入桌子数量、vip桌子数量159 cin >> n >> m;160 for (int i = 1; i <= n; i++) table.push_back(Table(0, 0, 0));161 162 int *vipTableMark = new int[m];163 //标注vip桌子号164 for (int i = 0; i < m; i++) {165 cin >> vipTableMark[i];166 //cout << vipTableMark[i] << endl;167 table[vipTableMark[i] - 1].isVIP = 1;168 }169 170 int ordinaryCount = 0, vipCount = 0;171 int nextArriveOrdinary = 0, nextArriveVip = 0;172 //优化,可以跳过循环的时间,无更替,或者无客人的时候173 int jumpHour = 0, jumpMinute = 0, jumpSecond = 0, minServerTime = 46800;174 //标志,记录是否下次循环无更替175 bool jump = false;176 for (int i = 8; i <= 21;) {177 for (int j = 0; j <= 59;) {178 //每秒钟,遍历一次每张桌子179 for (int s = 0; s <= 59;) {180 string nowTime = turnIntoStr(i, j, s);181 //遍历之后要对于每位在等待的顾客,等待时间+1182 for (int k = ordinaryCount; k < ordinary.size(); k++) {183 if (ordinary[k].arriveTime < nowTime) {184 ordinary[k].waitTime += jumpHour * 3600 + jumpMinute * 60 + jumpSecond;185 }186 else break;187 }188 for (int k = vipCount; k < vip.size(); k++) {189 if (vip[k].arriveTime < nowTime) {190 vip[k].waitTime += jumpHour * 3600 + jumpMinute * 60 + jumpSecond;191 }192 else break;193 }194 //优化,可以不每分钟遍历一次,每次遍历记录最小的servertime值,下次直接跳转serverTime,相应的,servertime不是自减,而是减去跳转间隔195 for (int k = 0; k < table.size(); k++) {196 if (table[k].serveTime > 0) {197 table[k].serveTime -= jumpHour * 3600 + jumpMinute * 60 + jumpSecond;198 }199 if (table[k].serveTime == 0) {200 if (table[k].isVIP == 1) {201 //VIP桌优先接待已经到达的VIP客户,减少排队时间202 if (vipCount < vip.size() && vip[vipCount].arriveTime <= nowTime) {203 cout << vip[vipCount].arriveTime << " " << nowTime << " " << wtime(vip[vipCount].waitTime) << endl;204 table[k].serveNum++;205 table[k].serveTime = vip[vipCount].useTime > 7200 ? 7200 : vip[vipCount].useTime;//不能超过两个小时206 if (nextArriveVip == vipCount)nextArriveVip++;207 vipCount++;208 }209 else if (ordinaryCount < ordinary.size() && ordinary[ordinaryCount].arriveTime <= nowTime) {210 cout << ordinary[ordinaryCount].arriveTime << " " << nowTime << " " << wtime(ordinary[ordinaryCount].waitTime) << endl;211 table[k].serveNum++;212 table[k].serveTime = ordinary[ordinaryCount].useTime > 7200 ? 7200 : ordinary[ordinaryCount].useTime;213 if (ordinaryCount == nextArriveOrdinary)nextArriveOrdinary++;214 ordinaryCount++;215 }216 }217 else {218 //普通桌可以接受按时达到排队的VIP/非VIP客户219 if (ordinaryCount < ordinary.size() && vipCount < vip.size() && vip[vipCount].arriveTime <= nowTime && ordinary[ordinaryCount].arriveTime >= vip[vipCount].arriveTime) {220 cout << vip[vipCount].arriveTime << " " << nowTime << " " << wtime(vip[vipCount].waitTime) << endl;221 table[k].serveNum++;222 table[k].serveTime = vip[vipCount].useTime > 7200 ? 7200 : vip[vipCount].useTime;223 if (nextArriveVip == vipCount)nextArriveVip++;224 vipCount++;225 }226 else if (ordinaryCount < ordinary.size() && vipCount < vip.size() && ordinary[ordinaryCount].arriveTime <= nowTime && ordinary[ordinaryCount].arriveTime <= vip[vipCount].arriveTime) {227 cout << ordinary[ordinaryCount].arriveTime << " " << nowTime << " " << wtime(ordinary[ordinaryCount].waitTime) << endl;228 table[k].serveNum++;229 table[k].serveTime = ordinary[ordinaryCount].useTime > 7200 ? 7200 : ordinary[ordinaryCount].useTime;230 if (ordinaryCount == nextArriveOrdinary)nextArriveOrdinary++;231 ordinaryCount++;232 }233 }234 }235 if (table[k].serveTime > 0) minServerTime = minServerTime > table[k].serveTime ? table[k].serveTime : minServerTime;236 }237 238 //即此处要等待客人239 if ((nextArriveVip < vip.size() || nextArriveOrdinary < ordinary.size())) {240 string nextClient;241 //只剩vip客人242 if (nextArriveVip < vip.size() && nextArriveOrdinary >= ordinary.size()) {243 nextClient = vip[nextArriveVip].arriveTime;244 if (minServerTime > waitForNextClient(nowTime, nextClient))nextArriveVip++;245 }246 //只剩普通客人247 else if (nextArriveVip >= vip.size() && nextArriveOrdinary < ordinary.size()) {248 nextClient = ordinary[nextArriveOrdinary].arriveTime;249 if (minServerTime > waitForNextClient(nowTime, nextClient))nextArriveOrdinary++;250 }251 //队列里两种客人都还有252 else if (nextArriveVip < vip.size() && nextArriveOrdinary < ordinary.size()) {253 nextClient = ordinary[nextArriveOrdinary].arriveTime > vip[nextArriveVip].arriveTime ? vip[nextArriveVip].arriveTime : ordinary[nextArriveOrdinary].arriveTime;254 if (minServerTime > waitForNextClient(nowTime, nextClient) && ordinary[nextArriveOrdinary].arriveTime < vip[nextArriveVip].arriveTime)nextArriveOrdinary++;255 else if (minServerTime > waitForNextClient(nowTime, nextClient) && ordinary[nextArriveOrdinary].arriveTime >= vip[nextArriveVip].arriveTime)nextArriveVip++;256 }257 else {258 jump = true;259 }260 minServerTime = minServerTime > waitForNextClient(nowTime, nextClient) ? waitForNextClient(nowTime, nextClient) : minServerTime;261 }262 263 if (jump)break;264 265 jumpSecond = minServerTime % 60;266 jumpMinute = (minServerTime / 60) % 60;267 jumpHour = minServerTime / 3600;268 269 minServerTime = 46800;270 int st = s + jumpSecond;271 int jt = j + jumpMinute;272 int it = i + jumpHour;273 274 s = st % 60;275 j = (jt + st / 60) % 60;276 i = (jt + st / 60) / 60 + it;277 278 279 //营业时间到,终止营业280 if (turnIntoStr(i, j, s) >= "21:00:00") {281 jump = true;282 break;283 }284 }285 if (jump)break;286 }287 if (jump)break;288 }289 290 for (int k = 0; k < table.size(); k++) {291 if (k == 0) cout << table[k].serveNum;292 else cout << " " << table[k].serveNum;293 }294 cout << endl;295 296 system("pause");297 return 0;298 }
【PAT-A】解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。