0%

PTA题解

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;
}
Have fun.