PTA天梯练习赛 刷题笔记1（L2 001-012）

题目库链接：团体程序设计天梯赛-练习集
NEXT：PTA天梯练习赛 刷题笔记2；

OP

\

L2-001 紧急救援 (25 分)

dijkstra（迪杰斯特拉）算法
大佬说SPFA也可以做，mark一下，接下来学

思路

可以参考这里来了解迪杰斯特拉的基本原理；

此题的主要特定是最短路可能有多种规划路线，而最优解只有一个，即需要同时处理距离和人数两个维度的信息；

主要思想是将所有点分为已达点与未达点两个集合（代码中用一个数组进行01标记），最开始时，已达点集合仅有出发点，未达点集合包含其余所有点；

主要过程是每一次循环遍历所有未达点，对于每一个未达点 pj ，如果可以通过一条道路（长度 ki ）连接至已达点 pi ，则记录由此未达点到达初始点的最短距离（设 pi 点到起始点的最短距离 li，lj=min(li+ki)l_j=min(l_i+k_i)），并记录所有能使 lj 取最小值的 i ，作为到达此点的方案数；

在所有未达点中选择距离初始点最短的点，将其加入已达点集合，并在所有可行方案（ i ）中选择积累人数最多的点作为最终与其连接的点，新点的累计人数即为与其连接点的累积人数和新点原有人数的和；

如此循环，直到目标点已达；

最后按顺序找出整个路径上的各个点并输出即可。

详见代码注释
进行人数存储的部分可优化，即smp变量不必要
时间复杂度O(n3)

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
struct 
{
	vector<int>fr;//存储其上游的点，即from i
	int strd=100000000;//存储距离初始点的距离，默认无穷大
	int p=0;//存储此点的人数
	int smp=0;//存储从初始点到此点的累计人数
}cty[502];

int main()
{
	int n,m,f,t,a,b,l;//n为城市数，m为道路数，abl为接收道路用变量
	int r[502][502]={0},rch[502]={0};//r即road，存储道路，长度为0即无路，此处可优化
									//rch数组存储已达点及方案数，0为未达
	cin>>n>>m>>f>>t;
	cty[f].fr.push_back(f);//初始化处理开始点
	rch[f]=1;
	cty[f].strd=0;
	for(int i=0;i<n;i++)
	{
		cin>>cty[i].p;
		cty[i].smp=cty[i].p;
	}//接收城市救援人数
	for(int i=0;i<m;i++)//接收路，对称加入存储
	{
		cin>>a>>b>>l;
		if(r[a][b])r[a][b]=min(r[a][b],l);
		else r[a][b]=l;
		if(r[b][a])r[b][a]=min(r[b][a],l);
		else r[b][a]=l;
	}
	while(!rch[t])//如果目标点未达，则持续循环
	{
		int mnr=100000000-8,mnm=-1;//mnr存储未达点距离初始点的距离最小值
									//mnm存储满足mnr点的编号
		for(int i=0;i<n;i++)
		{
			if(!rch[i])//如果未达
			{
				cty[i].fr.clear();//初始化
				cty[i].strd=100000000;
				for(int j=0;j<n;j++)
				{
					if(rch[j]&&r[i][j])//遍历每一条通往可达点的道路
					{
						if(cty[j].strd+r[i][j]<cty[i].strd)//更小值
						{
							cty[i].strd=cty[j].strd+r[i][j];//更新最小值
							cty[i].fr.clear();//情况方案
							cty[i].fr.push_back(j);//j加入方案
						}
						else if(cty[j].strd+r[i][j]==cty[i].strd)//与最小值相等的值
						{
							cty[i].fr.push_back(j);//j加入方案
						}
					}
				}
				if(cty[i].strd<mnr)//更新此次循环的最小距离
				{
					mnr=cty[i].strd;
					mnm=i;
				}
			}
		}
		int mxp=0,mxm=-1;//mxp记录最多积累人数，mxm记录mxp对应的城市编号
		for(int j:cty[mnm].fr)
		{
			rch[mnm]+=rch[j];//到达新点的最终方案数为每一个可行方案对应的点方案数之和
			if(cty[j].smp>mxp)//更新
			{
				mxp=cty[j].smp;
				mxm=j;
			}
		}
		cty[mnm].fr.clear();//清空方案
		cty[mnm].fr.push_back(mxm);//并将积累人数最多的方案定为最终方案
		cty[mnm].smp+=cty[mxm].smp;//更新积累人数
		//printf("%d %d\n",mnm,rch[mnm]);
	}
	printf("%d %d\n",rch[t],cty[t].smp);//输出方案数和最优方案人数
	stack<int>stk;//栈存储路径结点
	int now=t;
	stk.push(t);
	stk.push(cty[now].fr[0]);
	now=cty[now].fr[0];
	//printf("*%d",stk.top());
	while(stk.top()!=f)
	{
		stk.push(cty[now].fr[0]);
		now=cty[now].fr[0];
		//printf("*%d",stk.top());
	}
	printf("%d",stk.top());//输出开始
	stk.pop();
	while(stk.size())
	{
		printf(" %d",stk.top());
		stk.pop();
	}
    return 0;
}

L2-002 链表去重 (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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
struct 
{
	int num;
	int nxt;
}vtr[100005];

int main()
{
	int f1,n,g,f2=-1;
	cin>>f1>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>g;
		cin>>vtr[g].num>>vtr[g].nxt;
	}//接收结束
	int now=f1,a[10004]={0},lst=0,now2;//a用来桶去重，now为正在处理的节点，lst为上一个节点，now2为另一个链表的末尾
	while(now!=-1)//未到f1的结尾则继续循环
	{
		if(a[abs(vtr[now].num)])
		{
			vtr[lst].nxt=vtr[now].nxt;
			if(f2==-1)f2=now,now2=now,now=vtr[now].nxt,vtr[now2].nxt=-1;//若另一链表未被建立
			else
			{
				vtr[now2].nxt=now;
				now2=now;
				now=vtr[now].nxt;
				vtr[now2].nxt=-1;
			}
			
		}
		else
		{
			a[abs(vtr[now].num)]=1;
			lst=now;
			now=vtr[now].nxt;
		}
	}
	now=f1;
	while(now!=-1)
	{
		printf("%05d %d ",now,vtr[now].num);
        if(vtr[now].nxt==-1)printf("%d\n",-1);
        else printf("%05d\n",vtr[now].nxt);//注意要求保留位数
		now=vtr[now].nxt;
	}
	now=f2;
	while(now!=-1)
	{
		printf("%05d %d ",now,vtr[now].num);
        if(vtr[now].nxt==-1)printf("%d\n",-1);
        else printf("%05d\n",vtr[now].nxt);
		now=vtr[now].nxt;
	}
    return 0;
}

L2-003 月饼 (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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
struct mooncake
{
	double w;
	double m;
}mnk[1003];

bool cmp(const mooncake a,const mooncake b)
{
	return 1.0*a.m/a.w>1.0*b.m/b.w;
}
//money per weight 按单价降序排序
int main()
{
	int t;
    double n;
	cin>>t>>n;
	for(int i=1;i<=t;i++)cin>>mnk[i].w;
	for(int i=1;i<=t;i++)cin>>mnk[i].m;
	sort(mnk+1,mnk+t+1,cmp);
	double s=0;
	for(int i=1;i<=t&&n;i++)
	{
		if(n>=mnk[i].w)
		{
			n-=mnk[i].w;
			s+=mnk[i].m;
		}
		else
		{
			s+=1.0*n*mnk[i].m/mnk[i].w;
			n=0;
		}
	}
	printf("%.2lf",s);
    return 0;
}

L2-004 这是二叉搜索树吗？ (25 分)

树的前序遍历

思路

对于题目中描述的二叉搜索树，满足以下性质：
对于一棵树前序遍历 [ l , r ] ，第一个元素必为根节点；
设从第二个节点开始，第一个大于等于根节点的节点编号为mk，max[l,mk−1]<root,min[mk,r]<=rootmax [ l , mk - 1 ]<root,min[ mk , r ]<=root；

镜像树类似；

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
queue<int>que;
int a[1003];
bool ju(int l,int r,int dir)//dir=1即为正向树，dir=0即为镜像树
{
	int i,root=a[l],ans=1,mk=r+1,mi=root,mx=root-1;
	//root存储子树根节点的值，mk为右子树的根节点
	//mi为目标子树的最小值，mx为目标字数的最大值
	/*if(l==r)			//防呆代码，实际上用不到
	{
		que.push(a[l]);
		return 1;
	}
	else if(l>r)
	{
		return 1;
	}*/
	if(dir)
	{
		for(i=l+1;i<=r;i++)
		{
			if(a[i]>=root)mk=min(mk,i);
			if(mk==r+1)mx=max(mx,a[i]);//mk==r+1说明此处仍为左子树
			else mi=min(mi,a[i]);
		}
		if(mk!=l+1&&mx>=root||mk!=r+1&&mi<root)//对于mk的判据可以删除
		{
			//printf("%d %d %d %d %d\n",l,r,mi,mx,mk);
			return 0;
		}
	}
	else
	{
		for(i=l+1;i<=r;i++)
		{
			if(a[i]<root)mk=min(mk,i);
			if(mk==r+1)mi=min(mi,a[i]);
			else mx=max(mx,a[i]);
		}
		if(mk!=r+1&&mx>=root||mk!=l+1&&mi<root)
		{
			//printf("%d %d %d %d %d\n",l,r,mi,mx,mk);
			return 0;
		}
	}
	if(mk!=l+1)//若左子树存在
	{
		ans*=ju(l+1,mk-1,dir);
	}
	if(mk!=r+1)//若右子树存在
	{
		ans*=ju(mk,r,dir);
	}
	que.push(root);//根节点入栈，栈内即为后序遍历
	return ans;
}
int main()
{
	int n,i,f=1;
	cin>>n;
	for(i=1;i<=n&&f;i++)cin>>a[i];
	{
		if(a[1]>a[2])f=ju(1,n,1);//正向树
		else f=ju(1,n,0);//镜像树
		if(f)
		{
			printf("YES\n",que.size());
			while(!que.empty())
			{
				printf("%d",que.front());
				if(que.size()!=1)printf(" ");
				que.pop();
			}
		}
		else printf("NO");
	}
    return 0;
}

L2-005 集合相似度 (25 分)

双指针

思路

之前写过一篇题解，和这个题很像，详见关于 相似的数集 的思路+时间复杂度分析+代码;

排序后双指针去重即可，时间复杂度 O(KN)；

经测试，用map桶计数来查总数会TLE；

代码

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;
const ll M=1e9+7;

int main()
{
	int t,n,i,j;
	int a[51][2003]={0};
	cin>>t;
	for(i=1;i<=t;i++)
	{
		cin>>a[i][0];//a[i][0]存第 i 个数集的元素数
		for(j=1;j<=a[i][0];j++)
		{
			scanf("%d",&a[i][j]);
		}
		sort(a[i]+1,a[i]+a[i][0]+1);
	}
	cin>>n;
	int x,y,cc,ca;
	while(n--)
	{
		cc=0;
		cin>>x>>y;
		ca=a[x][0]+a[y][0];
		i=j=1;
		while(i<=a[x][0]&&j<=a[y][0])
		{
			while(a[x][i+1]==a[x][i])i++,ca--;
			while(a[y][j+1]==a[y][j])j++,ca--;
			if(a[x][i]<a[y][j])i++;
			else if(a[x][i]>a[y][j])j++;
			else cc++,i++,j++,ca--;
		}
		printf("%.2lf%%\n",100.0*cc/ca);
	}
    return 0;
}

L2-006 树的遍历 (25 分)

树的遍历

思路

思路与代码可以移步我之前的题解 关于 树的遍历 一题的思路+代码（树的后序与中序遍历输出层序遍历）（递归）；

补充：这个方法太麻烦了，下面的 L2-011 玩转二叉树 用的方法简单些

代码

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;
typedef long long ll;

vector<int> son[31];//son[x]代表x的子节点

int n,i,j;
int mid[31],lst[31],rot=0;//rot存总根

void maketr(int l,int r,int fa)//fa存该树的根的父节点
{
    if(l==r)//叶子
    {
        son[fa].push_back(mid[l]);
        return;
    }
    else if(l>r)return;//非法
    int root=0,rm=0;//root存该子树的根，rm存该根在中序遍历中的位置
    for(i=l;i<=r;i++)//对于该子树的每一个节点
    {
        for(j=1;j<=n;j++)//在后序遍历中位置最靠后的一个
        {
            if(mid[i]==lst[j])
            {
                if(j>root){root=j,rm=i;}
                //printf("*");
                break;
            }
        }
    }
    if(!rot)rot=lst[root];//如果总根未确定，该根即为总根
    //printf("%d\n",root);
    son[fa].push_back(lst[root]);//将此树的根连接至其父节点
    maketr(l,rm-1,lst[root]);//递归左子树
    maketr(rm+1,r,lst[root]);//递归右子树
    return;
}
queue<int> que;//bfs队列
void bfs(int x)
{
    //printf("*");
	int pf=0;
    for(i=0;i<son[x].size();i++)que.push(son[x][i]);
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
		if(!pf)pf=1;
		else printf(" ");
        printf("%d",now);
        for(i=0;i<son[now].size();i++)que.push(son[now][i]);//树无自环、重边与回路，不需要考虑重复加入的问题
    }
}
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)scanf("%d",&lst[i]);
    for(i=1;i<=n;i++)scanf("%d",&mid[i]);
    maketr(1,n,0);//建树
    bfs(0);//bfs输出
    return 0;
}

L2-007 家庭房产 (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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
struct 
{
	int t,s;//t为以其为根的套数，s为以其为根的面积
	int p;//p为以其为根的家族人数
	int f;//f标记其上级节点
}ppo[10000];//ppo节点存人
struct fmy
{
	double tpp,spp;
	int p;
	int mn;
}fm[10000];//fm节点存家庭
int find(int x)
{
	if(ppo[x].f==x)return x;
	ppo[x].f=find(ppo[x].f);
	return ppo[x].f;
}
bool cmp(const fmy a,const fmy b)
{
	if(fabs(a.spp-b.spp)<=0.00001)
	{
		return a.mn<b.mn;
	}
	return a.spp>b.spp;
}
int main()
{
	int n,i,x,g,m,c=0,get[10000]={0};//get防止成员被重复计数
	cin>>n;
	for(i=0;i<=9999;i++)ppo[i].f=i;//初始化并查集
	while(n--)
	{
		cin>>x;
		int fx,fg;
		if(!get[x])ppo[find(x)].p++,get[x]=1;//若未计数x，则计数x
		m=2;
		while(m--)
		{
			cin>>g;
			if(g==-1)continue;
			if(!get[g])ppo[find(g)].p++,get[g]=1;
			fx=find(x),fg=find(g);
			if(fg>fx)//选出x与g中较小的根，并合并
			{
				ppo[fg].f=fx;
				ppo[fx].p+=ppo[fg].p;
				ppo[fx].s+=ppo[fg].s;
				ppo[fx].t+=ppo[fg].t;
			}
			else if(fg<fx)
			{
				ppo[fx].f=fg;
				ppo[fg].p+=ppo[fx].p;
				ppo[fg].s+=ppo[fx].s;
				ppo[fg].t+=ppo[fx].t;
			}//若x与g相等，则说明已在同一家庭，不处理
		}
		cin>>m;
		while(m--)
		{
			cin>>g;
			if(g==-1)continue;
			if(!get[g])ppo[find(g)].p++,get[g]=1;
			fx=find(x),fg=find(g);
			if(fg>fx)
			{
				ppo[fg].f=fx;
				ppo[fx].p+=ppo[fg].p;
				ppo[fx].s+=ppo[fg].s;
				ppo[fx].t+=ppo[fg].t;
			}
			else if(fg<fx)
			{
				ppo[fx].f=fg;
				ppo[fg].p+=ppo[fx].p;
				ppo[fg].s+=ppo[fx].s;
				ppo[fg].t+=ppo[fx].t;
			}
		}
		fx=find(x);
		cin>>g;//新增x的套数与面积
		ppo[fx].t+=g;
		cin>>g;
		ppo[fx].s+=g;
	}
	for(i=0;i<=9999;i++)
	{
		if(find(i)==i&&ppo[i].p)//寻找家庭的根
		{
			fm[c].tpp=ppo[i].t*1.0/ppo[i].p;//写入fm节点
			fm[c].spp=ppo[i].s*1.0/ppo[i].p;
			fm[c].p=ppo[i].p;
			fm[c].mn=i;
			c++;
		}
	}
    printf("%d\n",c);
	sort(fm,fm+c,cmp);//排序
	for(i=0;i<c;i++)
	{
		printf("%04d %d %.3lf %.3lf\n",fm[i].mn,fm[i].p,fm[i].tpp,fm[i].spp);
	}
    return 0;
}

L2-008 最长对称子串 (25 分)

哈希字符串

思路

从两个方向进行字符串哈希，枚举所有区间，并比对；

代码中 ri[ i ] 存储的即为字符串前i位的哈希值；
le[ i ] 存储字符串后i位的哈希值；

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7,P=131;
ll qm(ll a,ll b)
{
	ll ans=1;
	for(;b;b>>=1)
	{
		if(b&1)ans=ans*a%M;
		a=a*a%M;
	}
	return ans;
}
void makehashr(string &g,ll *r,int len)
{
	for(int i=1;i<=len+1;i++)
	{
		r[i]=r[i-1]*P+g[i];
		r[i]%=M;
	}
}
void makehashl(string &g,ll *r,int len)
{
	for(int i=1;i<=len+1;i++)
	{
		r[i]=r[i-1]*P+g[len+1-i];
		r[i]%=M;
	}
}
ll gethash1(ll *p,int l,int r)
{
	return (p[r]+M-(p[l-1]*qm(P,r-l+1))%M)%M;
}
int main()
{
	string g;
	ll ri[1003]={0},le[1003]={0};
	getline(cin,g);
	g="a"+g;
	g[0]=0;
	int len=strlen(&g[1]);
	makehashr(g,ri,len);
	makehashl(g,le,len);
	//printf("%d\n",len);
	int mi=1;
	//for(int i=0;i<=len+1;i++)printf("%d %d %d %d\n",ri[i],le[i],g[i],g[len+1-i]);
	for(int i=1;i<=len;i++)
	for(int j=i+mi;j<=len;j++)
	{
		//printf("%d %d %d %d\n",i,j,gethash1(ri,i,j),gethash1(le,len-j+1,len-i+1));
		if(gethash1(ri,i,j)==gethash1(le,len-j+1,len-i+1))mi=max(mi,j-i+1);
	}
	cout<<mi;
    return 0;
}

L2-009 抢红包 (25 分)

结构体排序

思路

第一反应是用map存盈亏情况，结果发现还需要依照若干依据排序，就结构体啦；

处理好cmp函数即可；

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct pp{
    int w;
    int c;
    int i;
}p[10004];
bool cmp(const pp a,const pp b)
{
    if(a.w==b.w)
    {
        if(a.c==b.c)
        {
            return a.i<b.i;
        }
        return a.c>b.c;
    }
    return a.w>b.w;
}
int main()
{
    int n,t,g1,g2,i;
    cin>>t;
    for(i=1;i<=t;i++)
    {
        p[i].i=i;
        int s=0;
        cin>>n;
        while(n--)
        {
            cin>>g2>>g1;
            s+=g1;
            p[g2].w+=g1;
            p[g2].c++;
        }
        p[i].w-=s;
    }
    sort(p+1,p+t+1,cmp);
    for(i=1;i<=t;i++)
    {
        printf("%d %.2lf\n",p[i].i,p[i].w*1.0/100);
    }
    return 0;
}

L2-010 排座位 (25 分)

并查集

思路

依照题意，只需要使用并查集来存储朋友关系即可，敌人关系用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;
map<int,int>fr[102];
int fa[102];
int find(int x)
{
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    int n,m,k,a,b,o;
    int i;
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)fa[i]=i;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>o;
        if(o==1)
        {
            fa[find(a)]=find(b);
            fr[a][b]=1;
            fr[b][a]=1;
        }
        else
        {
            fr[a][b]=-1;
            fr[b][a]=-1;
        }
    }
    for(i=1;i<=k;i++)
    {
        cin>>a>>b;
        if(fr[a][b]==-1)
        {
            int j;
            for(j=1;j<=n;j++)
                if(find(a)==find(j)&&find(b)==find(j))break;//如果ab朋友网中有相同的j
            if(j==n+1)printf("No way\n");
            else printf("OK but...\n");
        }
        else if(fr[a][b]==1||find(a)==find(b))printf("No problem\n");
        else if(fr[a][b]==0)printf("OK\n");
    }
    return 0;
}

L2-011 玩转二叉树 (25 分)

树的遍历

思路

看到这道题就想起来前面的 树的遍历 一题，那个题的大体想法是用一个队列按层序线性存树，非常麻烦，需要单独dfs，此处要求输出镜像树，那么把每一层分别用栈存即可；

同理，对于上题，每层用队列分别存储即可；

对于任意子树的中序遍历，有，在前序遍历中位置最靠前的节点为该子树的根；

已知的数据特性：
——n!=0；
——节点编号<=999，不保证节点编号<=n；

段错误了好久，都因为是想当然…

代码

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 m[41],inf[1000];//m存储中序遍历，inf存储节点在前序遍历的位置
stack<int>stk[40];//层序遍历栈
void bdtr(int l,int r,int c)//中序遍历数组区间[l,r]，层数c
{
    //printf("*");
    int mi=40,mk=-1;
    for(int i=l;i<=r;i++)//找最前
    {
        if(inf[m[i]]<mi)mi=inf[m[i]],mk=i;
    }
    //if(mk!=-1)//防呆设计，无必要
    {
        stk[c].push(m[mk]);
        if(mk>l)bdtr(l,mk-1,c+1);
        if(mk<r)bdtr(mk+1,r,c+1);
    }
}
int main()
{
    int n,g;
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&m[i]);
    for(int i=1;i<=n;i++)scanf("%d",&g),inf[g]=i;
    bdtr(1,n,0);
    if(stk[0].size())printf("%d",stk[0].top()),stk[0].pop();
    for(int i=1;i<=39;i++)
    {
        if(stk[i].empty())break;
        while(stk[i].size())
        {
            printf(" %d",stk[i].top());
            stk[i].pop();
        }
    }
    return 0;
}

L2-012 关于堆的判断（25分）

堆，字符串

思路

关于堆的基本原理，可以参考这里；

堆的特性决定了节点 i 的父节点是 i/2，左子节点是 i*2，右子节点是 i*2+1，由此我们就可以快速判断节点间相互关系；

之后建堆，处理字符串即可；

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int hp[1003];
int c=1;
map<int,int>mp;//mp存节点键值对节点编号的映射
void bdhp(int x)
{
    int now=c;
    c++;
    hp[now]=x;//x加入堆尾
    while(now>1&&hp[now]<hp[now/2])//小根堆，上移
    {
        swap(hp[now],hp[now>>1]);
        now>>=1;
    }
}

int main()
{
    int n,m,ge,i,a,b;
    string g;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&ge);
        bdhp(ge);
    }
    for(i=1;i<c;i++)mp[hp[i]]=i;//构建映射
    while(m--)
    {
        cin>>a;
        cin>>g;
        if(g=="and")
        {
            cin>>b;
            printf("%c\n",mp[a]/2==mp[b]/2?'T':'F');
            cin>>g;
            cin>>g;
        }
        else
        {
            cin>>g;
            cin>>g;
            if(g=="root")printf("%c\n",mp[a]==1?'T':'F');
            else if(g=="parent")
            {
                cin>>g;
                cin>>b;
                printf("%c\n",mp[b]/2==mp[a]?'T':'F');
            }
            else if(g=="child")
            {
                cin>>g;
                cin>>b;
                printf("%c\n",mp[a]/2==mp[b]?'T':'F');
            }
        }
    }
    return 0;
}

ED

\

算法竞赛 > 比赛与题集
PTA天梯练习赛 刷题笔记1（L2 001-012）
https://tanyuu.github.io/2021.01-06/PTA天梯练习赛 刷题笔记1（L2 001-012）/
作者
F Juny
发布于
2021年4月17日
许可协议