今天下午 1:30 - 4:30,PAT 甲級考試腺占,也是今年秋季之前的最后一次考試機(jī)會了域帐。
我在離考試結(jié)束還有 22 分鐘時拿到了 100 分,出考場的時候老師問我多少分悴侵,要不要等證書瞧剖。我說 100 分,感受到了各位考生的眼神投過來可免。抓于。。
現(xiàn)在趁還沒忘完浇借,回顧一下這幾道題是怎么寫的捉撮。
03 月 19 日更新:發(fā)現(xiàn)考試平臺可以查看自己考試時提交的代碼,于是也摘下來咯妇垢〗碓猓考試時間緊,拿分是最重要的事闯估,代碼難免有很丑的地方灼舍,請各位看官包涵哈。
A 20分 20分鐘
只用了 20 分鐘涨薪,一次通過骑素。
很奇葩的題,有些地方我覺得有坑尤辱,但是沒管砂豌,竟然過了。給一個數(shù)字 D光督,然后讓你輸出這個數(shù)字第多少次的表示方法阳距,比如 D 是 8,第一次說成 "81"结借,就是 8 有 1 個筐摘,第二次 “8111”,8 有 1 個船老,1 有 1 個咖熟;第三次 “8113” 這樣子。
我上來就是用字符串處理的柳畔,字符串開到最大馍管,然后一點一點比,后一個數(shù)跟前一個不一樣就輸出前面的數(shù)字及個數(shù)薪韩。寫的時候突然想到如果 1 連續(xù)出現(xiàn)了 >= 10 次怎么辦确沸,輸出 “1xx” 嗎?沒管這個俘陷,交上去罗捎,沒試幾次,過了拉盾。桨菜。。
# include <cstdio>
# include <cstring>
char s[1000000];
char s0[1000000];
char d;
int N;
int main(){
int dt;
scanf("%d %d", &dt, &N);
d = '0' + dt;
s[0] = d; s[1] = '\0';
char lastc;
int lastn, idxs0;
for(int i = 2; i <= N; i ++){
lastc = s[0];
lastn = 1;
idxs0 = 0;
for(int j = 1; ; j ++){
if(s[j] != lastc){
if(s[j] == '\0'){
s0[idxs0 ++] = lastc;
s0[idxs0 ++] = lastn + '0';
s0[idxs0 ++] = '\0';
break;
}else{
s0[idxs0 ++] = lastc;
s0[idxs0 ++] = lastn + '0';
lastc = s[j];
lastn = 1;
}
}else{
lastn ++;
}
}
strcpy(s, s0);
}
printf("%s", s);
return 0;
}
B 25分 40分鐘
給許多個“考生 分?jǐn)?shù) 學(xué)凶狡”倒得,要通過它的要求計算出各個學(xué)校的 XXX(該學(xué)校學(xué)生的 頂級成績和 * 1.5 + 甲級成績 + 乙級成績 / 1.5) 和 Ns (考試人數(shù)),然后對各個學(xué)校排名次夭禽,XXX 一樣的同名次屎暇,這些的輸出順序再按照 Ns 和 學(xué)校名字典順序決定。
學(xué)校的各項分?jǐn)?shù)信息當(dāng)然用結(jié)構(gòu)體就可以了驻粟。很煩的就是學(xué)校名字符串怎么處理根悼,我為了查找校名快,用了很暴力的辦法蜀撑,把學(xué)校名和學(xué)校信息的 struct 對應(yīng)起來:
一個 map<str, int>挤巡, Key 是校名字符串,Value 是學(xué)校信息結(jié)構(gòu)體的 idx (剛開始想用索引表示酷麦,后來發(fā)現(xiàn)一旦排序就亂了矿卑,又在結(jié)構(gòu)體中加了一個字段 idx);
后來發(fā)現(xiàn)自己不會從 map 中按照 value 查找值沃饶,尷尬了母廷,只好又存了一個校名數(shù)組 schName[n][7]轻黑,存 idx 對應(yīng)的校名。很繁瑣很丑琴昆,但是為了一次就迅速通過氓鄙,我忍了。业舍。抖拦。
這道題我提交了約 4~5 次才通過,總是漏掉一些奇怪的細(xì)節(jié)條件舷暮。我看到提交列表里态罪,第一題的通過率是 0.2 左右,這道題則只有驚人的 0.07……還好我試了幾次就通過了下面,這時考試才過去 1 個小時复颈。
# include <cstdio>
# include <cstdlib>
# include <string>
# include <cstring>
# include <map>
using namespace std;
typedef map<string, int> str_int_map;
str_int_map indexmap;
struct schinfo{
int idx;
int scoreT, scoreA, scoreB;
int ns;
int TWS;
}schs[100000];
char schName[100000][7];
int N;
int indexm = 0;
int compar(const void* a, const void *b){
schinfo *aa = (schinfo*)a, *bb = (schinfo*)b;
if(aa->TWS != bb->TWS){
return bb->TWS - aa->TWS;
}else if(aa->ns != bb->ns){
return aa->ns - bb->ns;
}else{
return strcmp(schName[aa->idx], schName[bb->idx]);
}
}
int main(){
scanf("%d", &N);
char id[7], school[7];
string sch;
int score;
str_int_map::iterator iterf;
int idx;
for(int i = 0; i < N; i ++){
scanf("%s %d %s", id, &score, school);
for(int j = 0; school[j] != '\0'; j ++){
if(school[j] >= 'A' && school[j] <= 'Z'){
school[j] = school[j] - 'A' + 'a';
}
}
sch = school;
iterf = indexmap.find(sch);
if(iterf == indexmap.end()){ //not have
idx = indexm;
schs[idx].idx = idx;
indexmap[sch] = indexm ++;
strcpy(schName[idx], school);
}else{ //already in
idx = iterf->second;
}
schs[idx].ns ++;
if(id[0] == 'T'){
schs[idx].scoreT += score;
}else if(id[0] == 'A'){
schs[idx].scoreA += score;
}else{
schs[idx].scoreB += score;
}
}
for(int i = 0; i < indexm; i ++){
schs[i].TWS = schs[i].scoreT * 1.5 + schs[i].scoreA + schs[i].scoreB / 1.5; //ScoreB/1.5 + ScoreA + ScoreT*1.5
}
qsort(schs, indexm, sizeof(schinfo), compar);
printf("%d\n", indexm);
int rank = 0;
str_int_map::iterator iter;
for(int i = 0; i < indexm; i ++){
if(i == 0 || schs[i].TWS < schs[i - 1].TWS){ //new rank
rank = i + 1;
}
printf("%d %s %d %d\n", rank, schName[schs[i].idx], schs[i].TWS, schs[i].ns);
}
return 0;
}
C 25分 30分鐘
出考場的時候忘掉了這道題。過了一天才想起來沥割。
其實還是要動動腦子的券膀。剛看到這道題說 subset 和 clique 懵了一下,隱約記得《算法導(dǎo)論》上說過這個問題驯遇,好像是 NP 什么的芹彬,也沒寫過算法。結(jié)果一看題叉庐,只是讓判斷舒帮,沒有讓求。給一張圖和幾次查詢陡叠,要求對于每次查詢玩郊,給出這幾個 vertice 組成的 subset 是否是個 clique,是否是個 maximal clique枉阵。
A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. A maximal clique is a clique that cannot be extended by including one more adjacent vertex.
圖建好很簡單译红,然后就是對于每次查詢的子集,判斷是否兩兩連通兴溜,再判斷是否有某個子集外的節(jié)點與子集中的每一個頂點連通侦厚,就知道是否是最大的clique 了。
# include <cstdio>
bool graph[210][210];
int nv, ne;
int m;
int nset, set[210];
bool markver[210]; // if in set
int ans;
void printans(int answer){
if(answer == 0){ //not max
printf("Not Maximal\n");
}else if(answer == 1){
printf("Yes\n");
}else{
printf("Not a Clique\n");
}
}
int main(){
scanf("%d %d", &nv, &ne);
int a, b;
for(int i = 0; i < ne; i ++){
scanf("%d %d", &a, &b);
graph[a][b] = graph[b][a] = 1;
}
scanf("%d", &m);
for(int i = 0; i < m; i ++){ // m query
for(int j = 1; j <= nv; j ++){
markver[j] = false;
}
scanf("%d", &nset);
for(int j = 0; j < nset; j ++){
scanf("%d", set + j);
markver[set[j]] = true;
}
if(nset == 1){ //only one vertice in this subset
bool alone = true;
for(int j = 1; j <= nv; j ++){
if(graph[set[0]][j]) {alone = false; break;}
}
if(alone) ans = 1; else ans = 0;
}else{ // 2 or more vertices
bool isclique = true;
for(int j = 0; isclique && j < nset; j ++){ //every pair of vertices
for(int k = j + 1; k < nset; k ++){
if(! graph[set[j]][set[k]]){
isclique = false;
break;
}
}
}
if(! isclique){
ans = -1;
}else{ // is a clique, check if is max
bool ismax = true, alladj = true;
for(int k = 1; ismax && k <= nv; k ++){
if(!markver[k]){ // k is now not in this set
alladj = true;
for(int kk = 0; kk < nset; kk ++){
if(!graph[k][set[kk]]){
alladj = false;
break;
}
}
if(alladj){ //k is adj with every set[kk]
ismax = false;
}
}
}
if(! ismax) ans = 0; else ans = 1;
}
}
printans(ans);
}
return 0;
}
D 二叉樹 綜合
開始寫這道題的時候還有 80 分鐘左右吧拙徽,時間充足刨沦,我仍然很緊張,畢竟前面才 70 分膘怕,萬一寫不出來就還是挺難看的想诅。
這道題先給定一個前序遍歷序列。我看過這樣的題(雖然沒寫過),通過前序遍歷序列来破,根據(jù)左孩子小右孩子大篮灼,能直接分出來根節(jié)點的左右子樹,然后就是遞歸下去了徘禁。這次遞歸函數(shù)寫得比較好看诅诱,一遍就能跑對了。函數(shù)簽名大概是void build(node* pos, char lr, int lo, int hi)
晌坤,是把preorder[lo, hi)
這一部分的子樹放到 pos 的左孩子或者右孩子逢艘,用一個字符指示旦袋。函數(shù)里安上根節(jié)點(preorder[lo]
)骤菠,找到其左右字樹的分界線,有子樹的話就遞歸地掛那一部分疤孕。一棵樹完成商乎。
后面給了好多組查詢,給兩個 key a, b祭阀,查找 a 和 b 的最低公共祖先節(jié)點鹉戚。當(dāng)然,還要分 a 或者 b 不在這棵樹里的情況专控,另外輸出(這里寫了個 node *search(int key)
)抹凳。如果兩個 key 一個是另一個的祖先,也要識別出來伦腐。我本來想著把兩個節(jié)點各自往上走赢底,祖先存起來,然后兩組祖先對比著查找柏蘑,后來覺得太蠢了幸冻,萬一樹不平衡,祖先很長咳焚,查死你不償命洽损。
靈光一閃,想到之前寫樹的那篇文章里有學(xué)過 [dtime, ftime]
如果有包含關(guān)系革半,就存在祖先關(guān)系碑定。于是給結(jié)構(gòu)體增加了 dtime 和 ftime 兩個字段,先做了一遍 dfs又官。之后就特別爽了不傅,先看兩個點的[dtime, ftime]
數(shù)組是否包含就知道是否有祖先關(guān)系了。沒有的話赏胚,順著 a 往上找各個祖先访娶,直到該祖先的[dtime, ftime]
也包含了 b 的[dtime, ftime]
。線性的復(fù)雜度哦觉阅!
這時還有將近半個小時考試結(jié)束崖疤,我有一個 case 沒過秘车,99 分,排第 23 名(從名單的頁數(shù)來看是全國的名次)劫哼。自己試了幾個 case叮趴,發(fā)現(xiàn)如果這兩個節(jié)點一樣,我給錯判斷了权烧,應(yīng)該認(rèn)為 a 是 a 的祖先眯亦。加了幾處等號,過了般码。走人啊嗨 ~~~
這道題的代碼不丑妻率!遞歸我寫的很認(rèn)真的!
# include <cstdio>
struct node{
int data;
node *p, *lc, *rc;
int dtime, ftime; //discovered and finished time
};
int pre[100100];
node *root;
int m, n; //n = nkey, m = mquery
void insertAsRoot(int key){
root = new node;
root->lc = root->rc = root->p = NULL;
root->data = key;
}
node *insertAslc(int key, node *pos){
pos->lc = new node;
pos->lc->lc = pos->lc->rc = NULL;
pos->lc->p = pos;
pos->lc->data = key;
return pos->lc;
}
node *insertAsrc(int key, node *pos){
pos->rc = new node;
pos->rc->lc = pos->rc->rc = NULL;
pos->rc->p = pos;
pos->rc->data = key;
return pos->rc;
}
void build(node* pos, char lr, int lo, int hi){
node *x;
if(lr == 'l'){
x = insertAslc(pre[lo], pos);
}else{
x = insertAsrc(pre[lo], pos);
}
if(hi - lo == 1){
return;
}
int part = lo + 1;
for(; part < hi; part ++){
if(pre[part] > pre[lo]){
break;
}
}
if(part < hi){ //have right tree
build(x, 'r', part, hi);
}
if(part > lo + 1){ //have left tree
build(x, 'l', lo + 1, part);
}
}
node *search(int key, node *pos){
if(pos == NULL || pos->data == key){
return pos;
}
if(key < pos->data){
return search(key, pos->lc);
}else{
return search(key, pos->rc);
}
}
void dfs(node *pos, int &clk){
if(pos == NULL) return;
pos->dtime = clk ++;
dfs(pos->lc, clk);
dfs(pos->rc, clk);
pos->ftime = clk ++;
}
int main(){
scanf("%d %d", &m, &n);
for(int i = 0; i < n; i ++){
scanf("%d", pre + i);
}
insertAsRoot(pre[0]);
int part =1;
for(; part < n; part ++){
if(pre[part] > pre[0]){
break;
}
}
if(part < n){ //have right tree
build(root, 'r', part, n);
}
if(part > 1){ //have left tree
build(root, 'l', 1, part);
}
int clk = 0;
dfs(root, clk);
int a, b;
node *afound, *bfound;
for(int i = 0; i < m; i ++){ // m queries
scanf("%d %d", &a, &b);
afound = search(a, root);
bfound = search(b, root);
if(!afound && !bfound){
printf("ERROR: %d and %d are not found.\n", a, b);
}else if(!afound){
printf("ERROR: %d is not found.\n", a);
}else if(!bfound){
printf("ERROR: %d is not found.\n", b);
}else{ //look for their ancestors
if(afound->dtime <= bfound->dtime && bfound->ftime <= afound->ftime){ // a is ance of b
printf("%d is an ancestor of %d.\n", a, b);
}else if(bfound->dtime <= afound->dtime && afound->ftime <= bfound->ftime){ // b is ance of a
printf("%d is an ancestor of %d.\n", b, a);
}else{
node *ance = afound->p;
while(ance){
if(ance->dtime < bfound->dtime && ance->ftime > bfound->ftime){ //[dtime, ftime] being included
printf("LCA of %d and %d is %d.\n", a, b, ance->data);
break;
}
ance = ance ->p;
}
}
}
}
return 0;
}