天梯训练赛5 6 7

小字辈

原题链接

题目大意:

给出一个家族每个家庭成员的父或母, 其中第 i 个编号对应第 i 位成员的父/母 。

输出最小的辈分,以及顺序输出最小辈分成员的编号。

输入样例:

9
2 6 5 5 -1 5 6 4 7

输出样例:

4
1 9

思路:

用vector存下每个人的kid。

然后找到老祖宗,从上往下bfs即可,同时记录下每个人的辈分。

AC代码:

 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
#include<bits/stdc++.h>
using namespace std;
vector<int>kid[100000+10];
int r[100000+10];//记录每个人的辈分
int b[100000+10];//记录最小辈分成员
struct node
{
	int id;
	int step;
}cur,nex;
void bfs(int st)
{
	queue<node>que;
	cur.id=st;
	cur.step=1;
	que.push(cur);
	while(!que.empty())
	{	cur=que.front();
		que.pop();
		for(int i=0;i<kid[cur.id].size();i++)
		{	
			nex.id=kid[cur.id][i];
			nex.step=cur.step+1;
			que.push(nex);
			r[nex.id]=r[cur.id]+1;
		}
	}
	cout<<cur.step<<endl;
	
}
int main()
{
	int n,st;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		if(x==-1)
		{
			r[i]=1;
			st=i;
		}
		else 
		kid[x].push_back(i);
	}
	bfs(st);
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(r[i]==cur.step){
			b[cnt++]=i;
		}
	}
	for(int i=0;i<cnt;i++)
	{
		if(i!=cnt-1){
			cout<<b[i]<<" ";
		}
		else{
			cout<<b[i]<<endl;
		}
	}
	
}

功夫传人

原题链接

思路:

同上一题类似,从上往下的bfs即可。

AC代码:

 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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
	int id;
	double bs;
}fs[100000+10];
vector<int>g[100000+10];
int b[100000+10];
map<int,int>mp;//标记得道者
struct p
{
	int step;
	int id;
}cur,nex;
void bfs()
{
	cur.id=0;
	cur.step=0;
	queue<p>que;
	que.push(cur);
	while(!que.empty())
	{
		cur=que.front();
		que.pop();
		if(mp[cur.id]) b[cur.id]=cur.step;//得道者得辈分
		//cout<<cur.id<<" "<<cur.step<<endl;
		for(int i=0;i<g[cur.id].size();i++)
		{
			nex.id=g[cur.id][i];
			nex.step=cur.step+1;
			que.push(nex);
		}
	}
}
int main()
{
	int n;
	double z,r;
	cin>>n>>z>>r;
	int cnt=0;
	for(int i=0;i<n;i++)
	{	
		int x;
		int k;
		cin>>k;
		if(k==0)  
		{
			fs[cnt].id=i;
			cin>>fs[cnt].bs;
			cnt++;
			mp[i]=1;
		}
		else
		{
			while(k--)
			{
				cin>>x;
				g[i].push_back(x);
			}
		}
	}
	bfs();
	double ans=0;
	r=1-r/100;
	for(int i=0;i<cnt;i++)
	{	//cout<<fs[i].id<<" "<<fs[i].bs<<" "<<b[fs[i].id]<<endl;
		ans+=z*pow(r,b[fs[i].id])*fs[i].bs;
	}
	printf("%d",(int)ans);

球队食物链

原题链接

题目大意:

给出n个球队n*n的对战情况表,求“食物链”为一个1至N的排列{ T1 T2 ⋯ TN },满足:球队T1战胜过球队T2,球队T2战胜过球队T3,⋯,球队T(N−1)战胜过球队TN,球队TN战胜过球队T1。若存在多条“食物链”,请找出字典序最小的。

输入样例1:

5
-LWDW
W-LDW
WW-LW
DWW-W
DDLW-

输出样例1:

1 3 5 4 2

输入样例2:

1
2
3
4
5
6
5
-WDDW
D-DWL
DD-DW
DDW-D
DDDD-

输出样例2:

No Solution

思路:

1.首先注意题目说的是每个球队之间会踢两场,所以题目表中L也要记录胜场。

2.注意到如果存在这样一条食物链,那么其实是个环,也就是说1号球队一定在其中,满足字典序最小的一定也是1号球队开始的,所以只要以1号球队为起点做一次dfs即可。

3.剪枝:把赢过1号球队的队伍先做个标记。在dfs访问一个节点时判断一下剩下来没有访问的队伍中还有没有赢过1队的,没有直接return。(这题的精髓,没有会超时)

AC代码:

 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>
#define ll long long
using namespace std;
int vis[25],r[25],flag,cnt,n,num;
int g[25][25];
void dfs(int x,int cnt)
{	if(flag) return;
	if(!flag) r[cnt]=x;
	if(cnt==n)
	{	
			if(g[x][1]==1)
			{
				flag=1;
				return;
			}
	}
	int f = 1;
    for(int i = 1; i <=n; i ++)
    {
        if(!vis[i] && g[i][1]) f = 0;
    }//精髓剪枝
    if(f)return;
	for(int i=1;i<=n;i++)
	{	if(vis[i]||!g[x][i]) continue;
		vis[i]=1;
		dfs(i,cnt+1);
		vis[i]=0;
	}
}
int main()
{	

	cin>>n;
	getchar();
	char ch;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf(" %c",&ch);
			if(ch=='W')
			g[i][j]=1;
			if(ch=='L')
			g[j][i]=1;
		}
	}
		flag=0;
		memset(vis,0,sizeof(vis));
		memset(r,0,sizeof(r));
		vis[1]=1;
		dfs(1,1);
		if(flag) 
		{
			for(int i=1;i<=n;i++)
			{
				if(i!=n)
				cout<<r[i]<<" ";
				else 
				cout<<r[i];
			}
		}
		else puts("No Solution");
}

关于堆的判断

原题链接

题目大意:

给定一个二叉堆,判断根节点,兄弟节点,父子节点

思路:

主要利用二叉堆父亲的编号=(儿子的编号-1)/2这个性质

注意数据中会有负数

输入样例:

5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10

输出样例:

F
T
F
T

AC代码

 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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1005;
int heap[maxn],sz=0;
map<int,int>num;
void push(int x)
{
	int i=sz++;
    while(i>0)
    {
      int p=(i-1)/2;//父亲节点
		if(head[p]<=x) break;
		head[i]=head[p];//父亲下移,儿子上移
		i=p;
    }
    heap[i]=x;
}
int main()
{
	int n,m;
	cin>>n>>m;
	getchar();
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		push(x);
		
	}
	getchar();
	for(int i=0;i<n;i++)
	{
		num[heap[i]]=i;//num存储每个数字在二叉堆里的编号
	}
	while(m--)
	{
		int a=0,b=0,flag=0,f=0;
		int cnt=0;
		int ss[10]={0};
		string s;
		getline(cin,s);
		s+=" ";//防止末尾的数字读不出来
		for(int i=0;i<s.size();i++)
		{	
			if((s[i]-'0')>=0&&(s[i]-'0')<=9)
			{	
				a=a*10+(s[i]-'0');
				f=1;
			}
			if(s[i]=='-') flag=1;//标记负数
			if(s[i]==' '&&f)
			{	if(flag) ss[cnt++]=-a;
				else ss[cnt++]=a;
				flag=0;
				f=0;
				a=0;
			}
		}
		a=ss[0],b=ss[1];
		if(s.find("root")!=string::npos) 
		{
			if(num[a]==0)  puts("T");
			else puts("F");
		 } 
		 else if(s.find("sibling")!=string::npos) 
		{
			if((num[b]-1)/2==(num[a]-1)/2)  puts("T");
			else puts("F");
		 } 
		 else if(s.find("parent")!=string::npos) 
		{
			if(num[a]==(num[b]-1)/2)  puts("T");
			else puts("F");
		 } 
		 else if(s.find("child")!=string::npos) 
		{
			if(num[b]==(num[a]-1)/2)  puts("T");
			else puts("F");
		 } 
	}
	
}

喊山

原题链接

题目大意:

一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头,本题请你找出这个信号最远能传达到的地方。

若这样的山头不只一个,则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头,则输出0。

输入样例:

7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7

输出样例:

2
6
4
0

思路:

1.注意此题虽然是求最远距离,但是首先要保证这个距离是两点之间的最短距离。例如样例中虽然可以1->2->3,但是由于1也可直接传到3,所以1到3的距离是1并不是2.

2.对于每个询问的点标为起点,bfs,并标记这些点距离起点的距离,距离相等且序号更小时更新。

AC代码

 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>
#define ll long long
using namespace std;
vector<int>g[100000+10];
int vis[100000+10];
int dis[10000+10];
void bfs(int x)
{	int d=-1,pos;
	queue<int>que;
	que.push(x);
	dis[x]=0;
	while(!que.empty())
	{	x=que.front();
		que.pop();
		if(dis[x]>d)
		{
			d=dis[x];
			pos=x;
		}
		else if(dis[x]==d&&x<pos)//距离相等更新序号小的
		pos=x;
		for(int i=0;i<g[x].size();i++)
		{
			if(vis[g[x][i]])  continue;
			que.push(g[x][i]);
			dis[g[x][i]]=dis[x]+1;
			vis[g[x][i]]=1;
			
		}
	}
	cout<<pos<<endl;
}
int main()
{
	int n,m,k;
	cin>>n>>m>>k;
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	while(k--)
	{	memset(vis,0,sizeof(vis));
		memset(dis,0,sizeof(dis));
		int x;
		cin>>x;
		vis[x]=1;
		if(g[x].empty())//没有相邻的山头直接输出0
		{
			puts("0");
			continue;
		}
		bfs(x);
	}
}