题目库链接：团体程序设计天梯赛-练习集
LAST：PTA天梯练习赛 刷题笔记1；
OP
\
L2-013 红色警报 (25 分)
bfs
思路
这道题主要部分就是bfs计数，检验新集合与旧集合是不是元素数少1，只不过需要注意的细节有些多；
我将每一个连通块内编号最小的城市作为该连通块的代表，在该位上存储该块的元素数；
一个城市沦陷后，判断该城所在的连通块元素数量变化情况；
需要注意的是，如果该城即为该连通块的代表，则需要另外选择一个代表对该连通块进行广搜计数；
如果由于城市沦陷导致一些城市失联，则需要对失联的城市重新bfs；
代码
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>rd[502];
int gt[502];
int c[502];
void bfs(int x)
{
c[x]=0;
queue<int>que;
{
que.push(x);
gt[x]=x;
c[x]++;
}
while(!que.empty())
{
int now=que.front();
que.pop();
for(int i:rd[now])
if(gt[i]==-1)
{
que.push(i);
c[x]++;
gt[i]=x;
}
}
}
int main()
{
int n,m,a,b,part=0;
cin>>n>>m;
while(m--)
{
cin>>a>>b;
rd[a].push_back(b);
rd[b].push_back(a);
}
for(int i=0;i<n;i++)gt[i]=-1;
for(int i=0;i<n;i++)
if(gt[i]==-1)
{
bfs(i);
}
cin>>m;
int co=m;
while(m--){
cin>>a;
b=n;
int area=gt[a],car=c[area];
gt[a]=-2;
{
for(int i=0;i<n;i++)
{
if(gt[i]==area&&i!=a)gt[i]=-1;
if(gt[i]==-1&&i!=a)b=min(b,i);
}
if(a==area)area=b;
c[area]=0;
if(area>=0)bfs(area);
if(c[area]<car-1)
{
printf("Red Alert: City %d is lost!\n",a);
for(int i=0;i<n;i++)
if(gt[i]==-1)
{
bfs(i);
}
}
else printf("City %d is lost.\n",a);
}
}
if(co>=n)printf("Game Over.");
return 0;
}
|
L2-014 列车调度 (25 分)
贪心
思路
这个题我常做常忘，这次最后还是参考了这位大佬的题解;
本质是求给定序列最少有多少个递增序列（可不连续）；
首先想到的是创建足够多个栈，对于每一个元素，将其压入栈顶元素大于该元素并且栈顶元素最小的栈，如果不存在满足条件的栈，则将其压入新栈；
如此，时间复杂度则到了O(n2)，不现实；
在上面的过程中，我们可以发现，对于每个栈，只有栈顶元素是会被用到的，我们便可以只存储栈顶元素；
如果将栈顶元素放入一个set，便可以使用upper_bound十分快速地找到满足条件的set元素（所代表的栈）并将该元素替换为新值；
同理，如果不存在满足条件的set元素，将新值加入set即可；
时间复杂度便被降到了O(nlogn)；
因为每个车厢的编号是无重复的，所以不需要考虑误去重的问题；
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int>st;
int main()
{
int n,i,g;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>g;
auto po=st.upper_bound(g);
if(po!=st.end())
{
st.erase(po);
}
st.insert(g);
}
cout<<st.size();
return 0;
}
|
L2-015 互评成绩 (25 分)
排序？
思路
按要求算出每个同学成绩后排序，按要求输出即可；
注意：题目中要求的“非降序”，不是按输入顺序，而是按升序
所以代码中的pair数组用double数组即可
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,k,m;
cin>>n>>k>>m;
pair<double,int> sc[10004];
for(int i=1;i<=n;i++)
{
int g[20]={0};
for(int j=1;j<=k;j++)
{
cin>>g[j];
}
sort(g+1,g+k+1);
for(int j=2;j<=k-1;j++)
{
sc[i].first+=g[j];
}
sc[i].first/=k-2;
sc[i].second=i;
}
sort(sc+1,sc+n+1);
for(int i=m-1;i>=0;i--)
printf("%.3lf%s",sc[n-i].first,i?" ":"\0");
return 0;
}
|
L2-016 愿天下有情人都是失散多年的兄妹 (25 分)
dfs
思路
遇到这个题首先想到的是并查集，但是每人有父亲与母亲两个上级节点，同时又没有保证只有一个下级节点，所以并查集会非常麻烦；
于是这道题就可以用定深的dfs来解决了；
对第一个人dfs时，将其范围内所有亲友用map标记，对第二个人dfs时，检查范围内有无亲友被标记即可；
这道题的数据非常狠，包括但不限于询问某人的父母与其他同辈是否可婚；
4号测试组的数据怀疑有一些问题，具体描述如下：
默认性别为0时，38行可被注释掉，但是34行不可以，大致想了一下，没想到可能造成这种情况的测试组，也有可能是我想得不够全面，欢迎讨论；
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct
{
int s;
int f[2];
int fok;
}p[100005];
map<int,int>mp;
bool dfs(int x,int n,int o)
{
int f=1;
if(mp[x]){f=0;}
if(o)mp[x]++;
if(n<=4&&p[x].fok)
{
for(int i=0;i<=1;i++)
if(p[x].f[i]!=-1)f*=dfs(p[x].f[i],n+1,o);
}
return f;
}
int main()
{
int n,a,b,g;
char c;
cin>>n;
while(n--)
{
scanf("%d %c",&g,&c);
if(c=='M')p[g].s=1;
else p[g].s=0;
p[g].fok=1;
scanf("%d %d",&p[g].f[0],&p[g].f[1]);
if(p[g].f[0]!=-1)p[p[g].f[0]].s=1;
if(p[g].f[1]!=-1)p[p[g].f[1]].s=0;
}
cin>>n;
while(n--)
{
cin>>a>>b;
if(p[a].s==p[b].s)
{
printf("Never Mind\n");
}
else
{
mp.clear();
dfs(a,1,1);
if(dfs(b,1,0))printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
|
L2-017 人以群分 (25 分)
贪心？
思路
首要目的是使两群人人数差尽量小，如果总人数为偶数，则对半分，若总人数为奇数，则两边人数差一；
其次是是两侧分数之和的差尽量大，则按分数排序，一侧取较大的一段，另一侧取较小端即可；
对于总人数为奇数的情况，显然，将中位数分至较大端能使两端分数差更大；
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,a=0,b=0,g[100005],i;
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&g[i]);
sort(g+1,g+1+n);
if(n&1)
{
for(i=1;i<=n/2;i++)
a+=g[i],b+=g[n+1-i];
printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n/2+1,n/2,b-a+g[n/2+1]);
}
else
{
for(i=1;i<=n/2;i++)
a+=g[i],b+=g[n+1-i];
printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n/2,n/2,b-a);
}
return 0;
}
|
L2-018 多项式A除以B (25 分)
大除法
有一些大佬的做法还是不太清楚，mark一下，以后看here&here
思路
用数组模拟初中数学的大乘法即可；
百度百科_大除法
补充一点数据范围：
设最高幂次P；
五个样例中，有三个样例满足 P<=100；
有四个样例满足 P<=1000；
所有样例满足 P<=10000；
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
double a[10004],b[10004];
double c[10004]={0};
int n,g1,m,i,l,ma=-1,mb=-1;
double g2;
cin>>n;
while(n--)cin>>g1>>g2,a[g1]=g2,ma=max(ma,g1);
cin>>n;
while(n--)cin>>g1>>g2,b[g1]=g2,mb=max(mb,g1);
int top=ma;
while(top>=mb)
{
c[top-mb]=a[top]/b[mb];
for(i=0;i<=top;i++)
{
a[top-i]-=b[mb-i]*c[top-mb];
if(i==mb)break;
}
top--;
}
int cc=0,ca=0;
for(i=0;i<=ma-mb;i++)if(fabs(c[i])>=0.1)cc++;else c[i]=0;
for(i=0;i<mb;i++)if(fabs(a[i])>=0.1)ca++;else a[i]=0;
printf("%d",cc);
if(cc){for(i=ma-mb;i>=0;i--)if(fabs(c[i])>=0.1)printf(" %d %.1lf",i,c[i]);}
else printf(" 0 0.0");
printf("\n%d",ca);
if(ca){for(i=mb;i>=0;i--)if(fabs(a[i])>=0.1)printf(" %d %.1lf",i,a[i]);}
else printf(" 0 0.0");
return 0;
}
|
L2-019 悄悄关注 (25 分)
ZZU视频刷完啦~
思路
分别存下关注列表中的每个人和点赞数，为关注列表中的每个人分配哈希值（并无必要，标记即可），遍历点赞的人，筛选满足条件的输出即可；
代码
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;
typedef long long ll;
# define double long double
const int N = 2e5;
const int M = 20;
map<string,int>hh,ct;
map<string,int>::iterator it;
int main()
{
int n,chh=1,intg;
string g;
cin>>n;
while(n--)
{
cin>>g;
hh[g]=chh++;
}
cin>>n;
double cal=0;
for(int i=1;i<=n;i++)
{
cin>>g>>intg;
ct[g]=intg;
cal+=intg;
}
cal/=n;
int f=0;
for(it=ct.begin();it!=ct.end();it++)
{
if(it->second>=cal&&!hh[it->first])
{
cout<<it->first;
printf("\n");
f++;
}
}
if(!f)printf("Bing Mei You");
return 0;
}
|
L2-020 功夫传人 (25 分)
思路
记录树状关系，进行dfs，统计得道者的武力值即可；
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5;
const int M = 1e9 + 7;
double k[N + 5];
double val[N + 5];
double dk;
vector<int> rod[N + 5];
void dfs(int x)
{
val[x] *= k[x];
for (int i = 0; i < rod[x].size(); i++)
{
val[rod[x][i]] = val[x] * dk;
dfs(rod[x][i]);
}
}
int main()
{
int n, m, g;
double gd;
cin >> n >> val[0] >> dk;
dk /= 100.0;
dk = 1 - dk;
for (int i = 0; i < n; i++)
{
scanf("%d", &m);
if (m)
{
k[i] = 1;
while (m--)
{
scanf("%d", &g);
rod[i].push_back(g);
}
}
else
{
cin >> k[i];
}
}
dfs(0);
double ans = 0;
for (int i = 0; i < n; i++)
{
if (k[i] != 1)
ans += val[i];
}
ans = floor(ans);
printf("%.0lf", ans);
return 0;
}
|
L2-021 点赞狂魔 (25 分)
思路
对每个人的点赞标签去重（set / map / 排序去重）后，记录并排序；
按要求输出即可；
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3;
const int M = 1e9 + 7;
map<int, int> gt;
string g[102];
pair<pair<int, double>, int> pr[102];
int main()
{
int n, gint, m, chh = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> g[i];
scanf("%d", &m);
gt.clear();
for (int j = 1; j <= m; j++)
{
cin >> gint;
gt[gint]++;
}
pr[i] = {{gt.size(), m * 1.0 / gt.size()}, i};
}
sort(pr + 1, pr + 1 + n,
[&](pair<pair<int, double>, int> &a, pair<pair<int, double>, int> &b)
{
if (a.first.first == b.first.first)
return a.first.second < b.first.second;
else
return a.first.first > b.first.first;
});
int f = 0;
for (int i = 1; i <= n && i <= 3; i++)
{
if (f)
printf(" ");
cout << g[pr[i].second];
f++;
}
while (f < 3)
{
printf(" -");
f++;
}
return 0;
}
|
ED
\