北屿

北屿小智障

0%

PTA题解

Posted on Edited on In

L2-012 关于堆的判断(offline)

Desc

给一个小根堆判断一个或两个节点的关系

Solu

建堆，判断问题的类型

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;

const int N = 1050;

int n, m, rt;

int a[N];
int d[N];
map<int, int> mp;

void insert(int o, int x) {
    d[o] = x;
    while(o>1) {
        if(d[o] < d[o>>1]) { swap(d[o], d[o>>1]); o>>=1; }
        else break;
    }
}

void build() {
    for(int i=1; i<=n; i++) {
        insert(i, a[i]);
    }
    for(int i=1; i<=n; i++) mp[d[i]]=i;
}



int main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    build();
    
    for(int i=1; i<=m; i++) {
        string s; int x, y; int flag = 0;
        cin >> x >> s;
        if(s=="and") { // s="and" siblings
            cin >> y >> s >> s;
            if(d[mp[x]^1]==y) flag = 1;
        } else {
            cin >> s;
            if(s=="a") { // child
                cin >> s >> s >> y;
                if(d[mp[x]>>1] == y) flag = 1;
            } else {
                cin >> s;
                if(s == "root") { // root
                    if(d[1]==x) flag = 1;
                } else {
                    cin >> s >> y;
                    if(d[mp[y]>>1]==x) flag = 1;
                }
            }
        }
        if(flag) cout << "T" << endl;
        else cout << "F" << endl;
    }
    return 0;
}

L2-021 点赞狂魔

Desc

输出点赞类别最多的三位，如果相同输出点赞平均值最小的

Solu

用map判断之前是否点赞过，注意数据范围，学会计算算法复杂度

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

const int N = 105;


struct person {
    string name;
    int weight; double avg;
} p[N];

map<int, int> mp;

int cmp(const person &a, const person &b) {
    return a.weight > b.weight || (a.weight==b.weight && a.avg < b.avg);
}

int main() {
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) {
        int k, cnt=0;
        string name;
        cin >> name >> k;
        mp.clear();
        for(int j=1; j<=k; j++) {
            int x;
            cin >> x;
            if(!mp[x]) cnt++;
            mp[x]=1;
        }
        p[i].name = name, p[i].weight = cnt, p[i].avg = 1.0 * k / cnt;
    }
    sort(p+1, p+n+1, cmp);
    for(int i=1; i<=3; i++) {
        if(i<=n) {
            cout << p[i].name;
        } else {
            cout << "-";
        }
        if(i!=3) cout << " ";
    }
    return 0;
}

L2-025 分而治之

Desc

给一个图，判断去掉几个节点之后是否还有连通块

Solu

并查集重建即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

const int N = 10050;

int n, m, k;
int ex[N], ey[N], f[N];
bool b[N];

int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }

void merge(int x, int y) {
    x=find(x), y=find(y);
    f[x]=y;
}

int main() {
    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        cin >> ex[i] >> ey[i];
    }
    cin >> k;
    for(int i=1; i<=k; i++) {
        memset(b, 0, sizeof(b));
        int np;
        cin >> np;
        for(int j=1; j<=np; j++) {
            int x; cin >> x; b[x]=1;
        }
        
        for(int j=1; j<=n; j++) f[j]=j;
        for(int j=1; j<=n; j++) {
            if(b[ex[j]] || b[ey[j]]) continue;
            merge(ex[j], ey[j]);
        }
        int flag=1;
        for(int j=1; j<=n; j++) if(f[j]!=j) flag=0;
        if(flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

L2-027 名人堂与代金券

Desc

输出排名前K的学生，可能存在相同排名

Solu

按照题意做即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

const int N = 10050;

int n, g, k, tot;

struct person {
    string mail;
    int score;
}p[N];

int cmp(const person &a, const person &b) {
    return a.score>b.score || (a.score == b.score && a.mail < b.mail);
}

int main() {
    cin >> n >> g >> k;
    for(int i=1; i<=n; i++) {
        cin >> p[i].mail >> p[i].score;
        if(p[i].score >= g) tot+=50;
        else if(p[i].score >= 60) tot+=20;
    }
    sort(p+1, p+n+1, cmp);
    int pm=1;
    cout << tot << endl;
    for(int i=1; i<=n; i++) {
        if(i>1 && p[i].score != p[i-1].score) pm=i;
        if(pm > k) break;
        cout << pm << " " << p[i].mail << " " << p[i].score << endl;
    }
    return 0;
}

L2-030 冰岛人

Desc

判断两个人共同祖先是否在5代以内

Solu

这题真给我整吐了，坑也太多了
感觉有一个地方没交代清楚的就是维京人一定是祖先，但是f结尾的也可能是祖先啊，题目样例就是这样，这个影响是测试的2
另外测试的36挂掉应该是没考虑两个人的共同祖先可能会在任一人的5代共同祖先之内，这种情况也算进去了
5代=自己1代，往上4代；五代以内=自己1代，往上3代，其实找了3个fa

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

const int N = 100050;

struct person {
    string famn, firn, fan;
    int gender, fa;
} p[N];

int n, m;
map<string, int> mp;

int main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> p[i].firn >> p[i].famn;
        char lst = p[i].famn[p[i].famn.length()-1];
        if(lst == 'm') {
            p[i].gender = 1;
            p[i].fan = p[i].famn.substr(0, p[i].famn.length()-1);
        } else if(lst == 'f') {
            p[i].gender = 0;
            p[i].fan = p[i].famn.substr(0, p[i].famn.length()-1);
        } else if(lst == 'n') {
            p[i].gender = 1;
            p[i].fan = p[i].famn.substr(0, p[i].famn.length()-4);
        } else if(lst == 'r') {
            p[i].gender = 0;
            p[i].fan = p[i].famn.substr(0, p[i].famn.length()-7);
        }
        mp[p[i].firn]=i;
    }
    for(int i=1; i<=n; i++) {
        char lst = p[i].famn[p[i].famn.length()-1]; // important
        if(lst !='m' && lst !='f' && mp[p[i].fan]) p[i].fa = mp[p[i].fan];
        else p[i].fa = 0;
    }
    
//  for(int i=1; i<=n; i++) cout << p[i].fa << " "; cout << endl;
    
    cin >> m;
    for(int i=1; i<=m; i++) {
        string fmn1, fn1, fmn2, fn2;
        cin >> fn1 >> fmn1 >> fn2 >> fmn2;
        int id1=mp[fn1], id2=mp[fn2];
        if(!id1 || !id2) cout << "NA" << endl;
        else if(p[id1].gender == p[id2].gender) cout << "Whatever" << endl;
        else {
            int fx, fy, i, j, flag = 0;
            for(fx=id1, i=1; fx ; fx=p[fx].fa, i++) {
                for(fy=id2, j=1; fy ; fy=p[fy].fa, j++) {
                    if(i>=5 && j>=5) break; // important
                    if(fx == fy && (i<5 || j<5)) flag=1;
                }
            }
            
            if(flag) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
    }
    return 0;
}

L2-035 完全二叉树的层序遍历(offline)

Desc

给一个完全二叉树的后序遍历，求层序遍历

Solu

很有意思的题，用完全二叉树的后序遍历建树，顺序输出即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

const int N = 10050;

int n, rt;
int a[N], tr[N];

int nxt(int x) {
    if(x*2+1<=n && !tr[x*2+1]) return x*2+1;
    while(x>=1) {
        if(x*2<=n && !tr[x*2]) return x*2;
        x/=2;
    }
    return x;
}

int main() {
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    rt=1;
    for(int i=n; i>=1; i--) {
        tr[rt]=a[i];
//      cout << rt << " " << a[i] << endl;
        rt=nxt(rt);
    }
    for(int i=1; i<=n; i++) cout << tr[i] << " \n"[i==n];
    return 0;
}
Related Posts
Have fun.