PAT 甲级真题

真题"/>

PAT 甲级真题

1019. General Palindromic Number

　　题意：求数N在b进制下其序列是否为回文串，并输出其在b进制下的表示。

　　思路：模拟N在2进制下的表示求法，“除b倒取余”，之后判断是否回文。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int Base[30];
 5 int main()
 6 {
 7     int n, b;
 8     scanf("%d%d", &n, &b);
 9     int len = 0, tmp = n,yu=tmp%b;
10     while (tmp / b)
11     {
12         Base[len++] = yu;
13         tmp = tmp / b;
14         yu = tmp % b;
15     }
16     Base[len++] = yu;
17     bool flag = true;
18     for (int i = 0, j = len - 1; i <= j&&flag; i++, j--)
19     {
20         if (Base[i] != Base[j]) flag = false;
21     }
22     if (flag) printf("Yes\n");
23     else printf("No\n");
24     for (int i = len - 1; i >= 0; i--)
25     {
26         printf("%d", Base[i]);
27         if (i) printf(" ");
28     }
29     printf("\n");
30     return 0;
31 }

View Code

1020. Tree Traversals

　　题意：给出二叉树的后序遍历和中序遍历，求层次遍历。

　　思路：通过后序遍历和中序遍历建立二叉树，然后对二叉树进行BFS。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 const int maxn = 40;
 6 int postOrder[maxn];
 7 int inOrder[maxn];
 8 int L[maxn],R[maxn];
 9 int treeRoot;
10 queue<int>q;
11 int createBinTree(int pt_pl,int pt_pr,int pt_i,int n)
12 {
13     if (n == 0) return -1;
14     int k = pt_i,curRoot= postOrder[pt_pr];
15     while (curRoot!= inOrder[k])k++;//在中序中找到当前子树的根
16     L[curRoot] = createBinTree(pt_pl,pt_pl+(k- pt_i)-1,pt_i, k-pt_i);
17     R[curRoot] = createBinTree(pt_pl + (k - pt_i),pt_pr-1,k+1,n - (k-pt_i) - 1);
18     return curRoot;
19 }
20 void printLevelOrder(int root)
21 {
22     q.push(root);
23     while (!q.empty())
24     {
25         int u = q.front();
26         q.pop();
27         if (u == treeRoot) printf("%d", u);
28         else printf(" %d", u);
29         if (L[u] != -1) q.push(L[u]);
30         if (R[u] != -1) q.push(R[u]);
31     }
32     printf("\n");
33 }
34 
35 int main()
36 {
37     int n;
38     scanf("%d", &n);
39     for (int i = 0; i < n; i++) scanf("%d", postOrder + i);
40     for (int i = 0; i < n; i++) scanf("%d", inOrder + i);
41     treeRoot = postOrder[n-1];
42     createBinTree(0,n - 1, 0, n);
43     printLevelOrder(treeRoot);
44     return 0;
45 }

View Code

 1021. Deepest Root

　　题意：给出n个点和n-1条边。若是只有一个连通分量，且为无环图，则可将其看成一棵树，求拥有最大深度的树的所有根，并按字典序升序输出。否则输出连通块的数目。

　　思路：并查集求连通块；DFS判断是否有环(傻了，如果只有1个连通块，则因为边数只有n-1条，只能是无环图)；BFS求树的深度。可通过连续两次BFS求出树的最大直径。

  1 #include<iostream>
  2 #include<set>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 using namespace std;
  7 const int maxn = 10010;
  8 int pre[maxn],cnt_cpt;
  9 set<int>ans;
 10 int lvl[maxn];
 11 bool vis[maxn];
 12 struct edge
 13 {
 14     int to,next;
 15     edge(int tt=0,int nn=0):to(tt),next(nn){}
 16 };
 17 edge Edge[maxn << 1];
 18 int Head[maxn], totedge;
 19 void addedge(int from, int to)
 20 {
 21     Edge[totedge] = edge(to, Head[from]);
 22     Head[from] = totedge++;
 23     Edge[totedge] = edge(from, Head[to]);
 24     Head[to] = totedge++;
 25 
 26 }
 27 int max_deep;
 28 int Find(int x)
 29 {
 30     if (pre[x] == x) return x;
 31     else
 32     {
 33         int fa = pre[x];
 34         pre[x] = Find(fa);
 35         return pre[x];
 36     }
 37 }
 38 void Join(int u, int v)
 39 {
 40     int fu = Find(u), fv = Find(v);
 41     if (fu != fv)
 42     {
 43         if (fv > fu) fv ^= fu, fu ^= fv, fv ^= fu;
 44         pre[fu] = fv;
 45         cnt_cpt--;
 46     }
 47 }
 48 void BFS(int u)
 49 {
 50     vis[u] = true;
 51     queue<int>q;
 52     q.push(u);
 53     while (!q.empty())
 54     {
 55         int v = q.front();
 56         q.pop();
 57         for (int i = Head[v]; i != -1; i = Edge[i].next)
 58         {
 59             int t = Edge[i].to;
 60             if (!vis[t])
 61             {
 62                 vis[t] = true;
 63                 lvl[t] = lvl[v] + 1;
 64                 if (lvl[t] > max_deep) max_deep = lvl[t];
 65                 q.push(t);
 66             }
 67         }
 68     }
 69 }
 70 //bool DFS(int u,int pre)
 71 //{
 72 //    vis[u] = true;
 73 //    for (int i = Head[u]; i != -1; i = Edge[i].next)
 74 //    {
 75 //        int v = Edge[i].to;
 76 //        if (v == pre) continue;
 77 //        if (vis[v]) return true;
 78 //        else
 79 //        {
 80 //            bool flag = DFS(v, u);
 81 //            if (flag) return true;
 82 //        }
 83 //    }
 84 //    vis[u] = false;
 85 //    return false;
 86 //}
 87 int main()
 88 {
 89     int n;
 90     scanf("%d", &n);
 91     
 92     for (int i = 1; i <= n; i++) pre[i] = i;
 93     cnt_cpt = n;
 94     totedge = 0;
 95     memset(Head, -1, sizeof(Head));
 96 
 97     for (int i = 1; i < n; i++)
 98     {
 99         int u, v;
100         scanf("%d%d", &u, &v);
101         Join(u, v);
102         addedge(u, v);
103     }
104     if (cnt_cpt > 1)
105     {
106         printf("Error: %d components\n", cnt_cpt);
107     }
108     else
109     {
110         max_deep = 0;
111         BFS(1);
112         int next_root;
113         for (int i = 1; i <= n; i++)if (lvl[i] == max_deep) ans.insert(i), next_root=i;
114         max_deep = 0;
115         memset(lvl, 0, sizeof(lvl));
116         memset(vis, 0, sizeof(vis));
117         BFS(next_root);
118         for(int i=1;i<=n;i++)if (lvl[i] == max_deep) ans.insert(i);
119         int sz = ans.size();
120         set<int>::iterator it = ans.begin();
121         for (; it != ans.end(); it++)
122         {
123             printf("%d\n", *it);
124         }
125     }
126     return 0;
127 }

View Code

 1022. Digital Library

　　题意：给出n个图书信息：ID、title、author、key words、publisher、publish year.之后有m个询问，求指定title/author/key word/publisher/publish year的图书的ID。

　　思路：用map建立title、author、key word、publisher、publish year到ID的映射，用set存放被映射的ID。

　　一些技巧：sstream的使用、用fgets(str,size,stdin)或scanf("%[^\n]")读入一行带有空格的字符串(注意用getchar()吸收‘\n’).

 1 #include<iostream>
 2 #include<map>
 3 #include<set>
 4 #include<string>
 5 #include<sstream>
 6 #include<cstdio>
 7 using namespace std;
 8 
 9 map<string, set<string> >mp[5];
10 char tmp[90];
11 string id,t1,t2;
12 int main()
13 {
14     int n;
15     scanf("%d", &n);
16     for (int i = 0; i < n; i++)
17     {
18         scanf("%s", tmp);//ID,fgets(tmp,90,stdin);
19         id = tmp;
20         getchar();
21         scanf("%[^\n]", tmp);//title
22         mp[0][tmp].insert(id);
23         getchar();
24         scanf("%[^\n]", tmp);//author
25         mp[1][tmp].insert(id);
26         getchar();
27         scanf("%[^\n]", tmp);//key words
28         stringstream sss((t1=tmp));
29         while (sss >> t2) mp[2][t2].insert(id);
30         getchar();
31         scanf("%[^\n]", tmp);//publisher
32         mp[3][tmp].insert(id);
33         getchar();
34         scanf("%[^\n]", tmp);//year
35         mp[4][tmp].insert(id);
36     }
37     int m;
38     scanf("%d", &m);
39     for (int i = 1; i <= m; i++)
40     {
41         getchar();
42         scanf("%[^\n]", tmp);
43         printf("%s\n", tmp);
44         set<string>&st = mp[tmp[0] - '1'][tmp + 3];
45         if (st.size() == 0) printf("Not Found\n");
46         else
47         {
48             set<string>::iterator it = st.begin();
49             for (; it != st.end(); it++)
50             {
51                 printf("%s\n", (*it).c_str());
52             }
53         }
54     }
55     return 0;
56 }

View Code

 1023. Have Fun with Numbers

　　题意：将给出的一个大数*2，判断其是否可由原来的数通过排列得到。

　　思路：数组模拟大数*2.

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 char str[30],dst[30];
 6 int main()
 7 {
 8     scanf("%s", str + 1);
 9     int len = strlen(str + 1);
10     int tadd = 0;
11     for (int i = len; i >= 1; i--)
12     {
13         tadd  += 2*(str[i] - '0');
14         dst[i] = '0'+tadd % 10;
15         tadd /= 10;
16     }
17     if (tadd) dst[0] = '0'+tadd;
18     dst[len + 1] = '\0';
19     if (tadd) printf("No\n%s\n",dst);
20     else
21     {
22         bool flag = true;
23         for (int i = 0; i <= 9; i++)
24         {
25             int c1 = 0,c2 = 0;
26             for (int j = 1; j <= len; j++) if (str[j] == '0' + i)c1++;
27             for (int j = 1; j <= len; j++) if (dst[j] == '0' + i) c2++;
28             if (c1 != c2)
29             {
30                 printf("No\n");
31                 flag = false;
32                 break;
33             }
34         }
35         if (flag) printf("Yes\n");
36         printf("%s\n", dst + 1);
37     }
38     return 0;
39 }

View Code

 1024. Palindromic Number

　　题意：给出一个<=10^10的数，每次将其颠倒后与原数相加，若结果为回文数，则输出对应的数和颠倒的次数。

　　思路：用字符串数组模拟大数加法。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 char init[200], dst[200],ans[200];
 8 void Reverse()
 9 {
10     reverse_copy(init, init + strlen(init), dst);
11     return;
12 }
13 void Add()
14 {
15     int len = strlen(init);
16     int pos = len, tmp = 0;
17     for (int i = len - 1; i >= 0; --i)
18     {
19         tmp += init[i] - '0' + dst[i] - '0';
20         ans[pos--] = '0' + tmp % 10;
21         tmp /= 10;
22     }
23     int st, ed = len;
24     if (tmp) ans[pos] = '0' + tmp, st = 0;
25     else ans[pos] = '\0', st = 1;
26     ans[ed + 1] = '\0';
27     memcpy(init, ans + st, ed - st + 2);
28 }
29 bool isPar()
30 {
31     int len = strlen(init);
32     for (int i = len-1; i >=len/2; i--)
33     {
34         if (init[i] != init[len - i-1])
35         {
36             return false;
37         }
38     }
39     
40     return true;
41 }
42 int main()
43 {
44     long long n, k;
45     scanf("%s%lld", init, &k);
46     long long cur = 0;
47     while (!isPar())
48     {
49         if (cur == k) break;
50         cur++;
51         Reverse();
52         Add();
53     }
54     printf("%s\n%lld\n", init, cur);
55     return 0;
56 }

View Code

 1025. PAT Ranking

　　题意：有若干子测试，每个子测试中有ki个人，给出其编号和成绩。现在需要你给出最终的成绩排名，给出每个人的编号、最终排名、子测试序号、子测试排名。

　　思路：vector应用。用merge对多个vector合并；用assign来对vector赋值。

 1 #include<iostream>
 2 #include<vector>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8     string id;
 9     int score;
10     int loc_num;
11     int loc_rank;
12     node(string ii="",int ss=0,int ln=0,int lr=0):id(ii),score(ss),loc_num(ln),loc_rank(lr){}
13 };
14 vector<node>ans;
15 bool Cmp(node&a, node&b)
16 {
17     if (a.score == b.score) return a.id < b.id;
18     else return a.score > b.score;
19 }
20 char ID[20];
21 int main()
22 {
23     int n;
24     scanf("%d", &n);
25     int loc_num = 1;
26     while (n--)
27     {
28         int k;
29         scanf("%d", &k);
30         vector<node>tmp;
31         for (int i = 0; i < k; i++)
32         {
33             int score;
34             scanf("%s%d", ID, &score);
35             tmp.push_back(node(ID, score,loc_num));
36         }
37         sort(tmp.begin(), tmp.end(), Cmp);
38         vector<node>::iterator it = tmp.begin();
39         int pre = -1,cnt=0,prer;
40         for (; it != tmp.end(); it++)
41         {
42             if (pre==-1||it->score < pre) it->loc_rank =prer= ++cnt,pre=it->score;
43             else it->loc_rank = prer,cnt++;
44         }
45         vector<node>tans;
46         tans.resize(ans.size() + tmp.size());
47         merge(ans.begin(), ans.end(), tmp.begin(), tmp.end(), tans.begin(),Cmp);
48         ans.clear();
49         ans.assign(tans.begin(), tans.end());
50         loc_num++;
51     }
52     printf("%d\n", ans.size());
53     int prescore = -1, prer, cnt = 0;
54     vector<node>::iterator it = ans.begin();
55     for (; it != ans.end(); it++)
56     {
57         printf("%s", it->id.c_str());
58         if (prescore == -1 || it->score < prescore)
59         {
60             prer = ++cnt;
61             prescore = it->score;
62         }
63         else cnt++;
64         printf(" %d", prer);
65         printf(" %d %d\n", it->loc_num, it->loc_rank);
66     }
67     return 0;
68 }

View Code

 1026. Table Tennis

　　题意：有k个台球桌，其中有m个为VIP桌。该台球室营业时间为9:00:00到21:00:00。有若干pair来该台球室打球。如果台球桌已满人，否则使用编号最小的台球桌。这些人当中有VIP用户。如果在等待时有个台球桌刚好空出来，且为VIP桌，则VIP用户可率先使用，有多个VIP用户时按到达时间的顺序使用。给出该台球室按每个桌子的开始服务时间排序的使用情况（所服务pair的到来时间、开始服务时间、等待时间），并给出每个桌子服务pair数目。

　　思路：优先队列维护当前可使用的台球桌，对用户的到来时间进行排序。如果到来有桌子为空，则可立马使用；否则入等待队列；等待时若有桌子空出，则若其为VIP桌且等待队伍中有VIP用户，则由该VIP用户先用，否则由队伍的第一个人使用。

　　注意：对等待时间四舍五入；每个pair的使用时间最多2小时；不在营业时间到来的客户或者营业时间结束停止服务。

  1 #include<iostream>
  2 #include<vector>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 struct node
  8 {
  9     int ar_time;
 10     int pl_time;
 11     bool vip;
 12     node(int aa = 0, int pp = 0, bool vv = false) :ar_time(aa), pl_time(pp), vip(vv) {}
 13 };
 14 vector<node>customers;
 15 vector<node>waitVec;
 16 int tables[110];
 17 int viptab[110];
 18 struct tab
 19 {
 20     int endtime;
 21     int id;
 22     tab(int ee = 0, int ii = 0) :endtime(ee), id(ii) {}
 23 };
 24 vector<tab>pq;
 25 bool Cmp2(const tab&a, const tab&b)
 26 {
 27     if (a.endtime == b.endtime)
 28     {
 29         return a.id > b.id;
 30     }
 31     else return a.endtime > b.endtime;
 32 }
 33 bool Cmp(node&a, node&b)
 34 {
 35     return a.ar_time < b.ar_time;
 36 }
 37 char ar[10];
 38 int exChange()
 39 {
 40     return ar[7] - '0' + (ar[6] - '0') * 10 + (ar[4] - '0') * 60 + (ar[3] - '0') * 10 * 60 + (ar[1] - '0') * 3600 + (ar[0] - '0') * 10 * 3600;
 41 }
 42 void int2str(int time)
 43 {
 44     ar[0] = '0' + time / 3600 / 10;
 45     ar[1] = '0' + time / 3600 % 10;
 46     time -= (ar[1] - '0') * 3600 + (ar[0] - '0') * 10 * 3600;
 47     ar[3] = '0' + time / 60 / 10;
 48     ar[4] = '0' + time / 60 % 10;
 49     time -= (ar[4] - '0') * 60 + (ar[3] - '0') * 10 * 60;
 50     ar[6] = '0' + time / 10;
 51     ar[7] = '0' + time % 10;
 52     ar[2] = ar[5] = ':';
 53     ar[8] = '\0';
 54 }
 55 
 56 void run(int ttime)
 57 {
 58     tab ff = pq.front();
 59     while (ff.endtime < ttime&&waitVec.size())
 60     {
 61 
 62         int index = 0;
 63         node cur = waitVec[0];
 64         bool isvip_inwait = false;
 65         vector<node>::iterator it = waitVec.begin();
 66         for (; it != waitVec.end(); it++)
 67         {
 68             if (it->vip)
 69             {
 70                 index = it - waitVec.begin();
 71                 cur = waitVec[index];
 72                 isvip_inwait = true;
 73                 break;
 74             }
 75         }
 76         if (isvip_inwait)
 77         {
 78             vector<tab>::iterator itab = pq.begin();
 79             for (; itab != pq.end(); itab++)
 80             {
 81                 if (itab->endtime == ff.endtime)
 82                 {
 83                     if (viptab[itab->id])
 84                     {
 85                         int tt = ff.id;
 86                         ff.id =pq.begin()->id=itab->id;
 87                         itab->id = tt;
 88                         break;
 89                     }
 90                 }
 91             }
 92         }
 93         if(!viptab[ff.id])     index = 0,cur = waitVec[0];
 94 
 95         int2str(cur.ar_time);
 96         printf("%s", ar);
 97         if (ff.endtime >= cur.ar_time)int2str(ff.endtime);
 98         int waitTime = ((ff.endtime <= cur.ar_time) ? 0 : ff.endtime - cur.ar_time);
 99         printf(" %s %d\n", ar, (waitTime + 30) / 60);
100         waitVec.erase(waitVec.begin() + index);
101         pop_heap(pq.begin(), pq.end(), Cmp2);
102         pq.pop_back();
103         int endTime = ((ff.endtime <= cur.ar_time) ? cur.ar_time + cur.pl_time : ff.endtime + cur.pl_time);
104         pq.push_back(tab(endTime, ff.id));
105         push_heap(pq.begin(), pq.end(), Cmp2);
106         tables[ff.id]++;
107         ff = pq.front();
108     }
109 }
110 int main()
111 {
112     int n, Count = 0;
113     int st = 8 * 3600, ed = 21 * 3600;
114     scanf("%d", &n);
115     for (int i = 1; i <= n; i++)
116     {
117         int pl, vip;
118         scanf("%s%d%d", ar, &pl, &vip);
119         if (pl > 120) pl = 120;
120         pl = pl * 60;
121         int artime = exChange();
122         if (artime >= ed) continue;
123         customers.push_back(node(artime, pl, vip));
124         Count++;
125     }
126     sort(customers.begin(), customers.end(), Cmp);
127     int k, m;
128     scanf("%d%d", &k, &m);
129     for (int i = 1; i <= m; i++)
130     {
131         int id;
132         scanf("%d", &id);
133         viptab[id] = 1;
134     }
135 
136 
137     for (int i = 1; i <= k; i++)
138     {
139         pq.push_back(tab(st, i));
140     }
141     make_heap(pq.begin(), pq.end(), Cmp2);
142     for (int i = 0; i < Count;)
143     {
144         tab ff = pq.front();
145         if (waitVec.size() == 0 || customers[i].ar_time <= ff.endtime)
146         {
147             waitVec.push_back(customers[i]);
148             i++;
149         }
150         else
151         {
152             run(customers[i].ar_time);
153         }
154     }
155     run(ed);
156     for (int i = 1; i <= k; i++)
157     {
158         if (i> 1) printf(" ");
159         printf("%d", tables[i]);
160     }
161     printf("\n");
162     return 0;
163 }

View Code

 1027. Colors in Mars

　　题意：把给出的3个十进制数转为3个2为13进制数。

　　思路：对13整除和取余。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 char color[10];
 5 int main()
 6 {
 7     for (int i = 0; i < 3; i++)
 8     {
 9         int v;
10         scanf("%d", &v);
11         color[i * 2] = ((v / 13 <= 9) ? '0' + v / 13 : 'A' + v / 13 - 10);
12         color[i * 2 + 1] = ((v % 13 <= 9) ? '0' + v % 13 : 'A' + v % 13 - 10);
13     }
14     printf("#%s\n", color);
15     return 0;
16 }

View Code

 

转载于:.html