天梯训练赛1 3 4

家庭房产

题目链接

题目大意:

给出n个人的信息:编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积。

统计家庭个数,并按下列格式输出每个家庭的信息:

家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积

其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出,若有并列,则按成员编号的升序输出。

输入样例:

10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100

输出样例:

3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

思路:

很显然的一道并查集。只不过在数据处理上可能会有点麻烦。

首先定义两个结构体,node1存储题目中给出的n个人的信息,node2存储各个家庭的信息。

考虑到要输出家庭中成员的最小编号,在使用并查集的时候不妨让小的去当根,即最小编号是每个家庭块的祖先。

接下来就是耐心的统计了。

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
 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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 10010
int par[MAX_N];
map<int,int>mp,vis;
struct node1
{	int fa,ma,k;
	int kid[10];
	int num;//自己的编号
	int nhouse;//房产数
	int phouse;//房产面积
}man[10100];
struct node2
{	int m;//家庭中最小编号
	int people;//家庭人数
	double nhouse;
	double phouse;	
}family[10100];
bool cmp(node2 f1,node2 f2)
{
	if(f1.phouse>f2.phouse) return true;
	else if(f1.phouse==f2.phouse) return f1.m<f2.m;
}
int find(int x)
{
	if(par[x]==x) return x;
	else return(par[x]=find(par[x]));
}
void unite(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y) return;
	else if(x>y) par[x]=y;//让编号小的去当祖先
	else par[y]=x; 
}
int main()
{	
	int n,id=0;
	cin>>n;
	for(int i=1;i<=9999;i++)
	par[i]=i;
	for(int i=1;i<=n;i++)
	{
		int fa,ma,kid,k;
		cin>>man[i].num>>man[i].fa>>man[i].ma>>man[i].k;
		if(man[i].fa!=-1)unite(man[i].num,man[i].fa);
		if(man[i].ma!=-1)unite(man[i].num,man[i].ma);
		for(int j=1;j<=man[i].k;j++)
		{
			cin>>man[i].kid[j];
			if(man[i].kid[j]!=-1)
			unite(man[i].kid[j],man[i].num);
		}
		cin>>man[i].nhouse>>man[i].phouse;
	}
	for(int i=1;i<=n;i++)
	{	
		int minn=find(man[i].num);//
		int t=mp[minn];
		if(t==0) //防止同一个家庭重复统计
		{
			mp[minn]=++id;//给每个家庭编号
			family[id].m=minn;
			if(!vis[man[i].num])
			{
				family[id].people++;
				vis[man[i].num]=1;
			}
			if(man[i].fa!=-1&&vis[man[i].fa]==0)
			{
				family[id].people++;
				vis[man[i].fa]=1;
			}
			if(man[i].ma!=-1&&vis[man[i].ma]==0)
			{
				family[id].people++;
				vis[man[i].ma]=1;
			}
			for(int j=1;j<=man[i].k;j++)
			{
				if(man[i].kid[j]!=-1&&vis[man[i].kid[j]]==0)
				{
				family[id].people++;
				vis[man[i].kid[j]]=1;
				}
			}
			family[id].nhouse+=man[i].nhouse;
			family[id].phouse+=man[i].phouse;
		}
		else
		{	if(!vis[man[i].num])
			{
				family[t].people++;
				vis[man[i].num]=1;
			
			}
			if(man[i].fa!=-1&&vis[man[i].fa]==0)
			{
				family[t].people++;
				vis[man[i].fa]=1;

			}
			if(man[i].ma!=-1&&vis[man[i].ma]==0)
			{
				family[t].people++;
				vis[man[i].ma]=1;

			}
			for(int j=1;j<=man[i].k;j++)
			{
				if(man[i].kid[j]!=-1&&vis[man[i].kid[j]]==0)
				{	
				family[t].people++;
				vis[man[i].kid[j]]=1;
				}
			}
			family[t].nhouse+=man[i].nhouse;
			family[t].phouse+=man[i].phouse;
			
		}
		
	}
	for(int i=1;i<=id;i++)
	{		if(family[i].people>0)
			{
				family[i].nhouse/=family[i].people;
				family[i].phouse/=family[i].people;
			}
	
	}
	if(id>1)
	sort(family+1,family+id+1,cmp);//按题目意思排序
	cout<<id<<endl;
	for(int i=1;i<=id;i++)
	printf("%04d %d %.3f %.3f\n",family[i].m,family[i].people,family[i].nhouse,family[i].phouse);
}

整除光棍

原题链接

题目大意:

给你一个不以5结尾的奇数x ,求形如1,11,111,1111这样形式的数能整除x的最小解。

输出 第一个数字s,表示x乘以s是一个光棍,第二个数字n是这个光棍的位数。

输入样例:

31

输出样例:

3584229390681 15

思路:

肯定是一道大数题。我们要1,11,111依次枚举过去找出最优解。

高精度除法。

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
#include<bits/stdc++.h>
using namespace std;
int ans[1000];
int main()
{	
	int x;
	cin>>x;
	int sum=1,cnt=1;//cnt表示光棍位数
	while(sum!=0)
	{
		if(sum<x) ans[cnt]=0;//除不下添0
		else
		{
			ans[cnt]=sum/x;//记录商
			sum=sum%x;
		 }
		 if(sum==0) break;  
		 sum=sum*10+1;
		 cnt++;
	}
	int flag=0;
	for(int i=1;i<=cnt;i++)
	{
		if(ans[i])
		flag=1;//去掉前缀0
		if(flag) cout<<ans[i];
	}
	cout<<" "<<cnt;
	
}

部落

原题链接

题目大意:

给出若干个部落,认为朋友的朋友都算在一个部落里。求这个社区的总人数以及互不相交的部落个数。

再给出若干个查询,询问两人是否在同一部落。

输入样例:

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

输出样例:

10 2
Y
N

思路:

又是一道并查集。

可以用set去重的特性直接来统计社区的总人数,然后遍历set去统计部落个数即可。

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
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 50010
int par[MAX_N];
int high[MAX_N];//树的高度
void init(int n)
{
	for(int i=0;i<n;i++)
	{
		par[i]=i;
		high[i]=0;
	}
} 
int find(int x)
{
	if(par[x]==x)
	return x;
	else
	return par[x]=find(par[x]);
}
void unite(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(high[x]<high[y])
	par[x]=y;
	else 
	{
		par[y]=x;
		if(high[x]==high[y]) high[x]++;
	}
}
bool same(int x,int y)
{
	return find(x)==find(y);	
}
set<int>s;
int main()
{
	int n;
	cin>>n;
	init(10000+10);
	while(n--)
	{
		int k;
		cin>>k;
		int x;
		cin>>x;
		s.insert(x);
		k--;
		for(int i=1;i<=k;i++)
		{	int y;
			cin>>y;
			s.insert(y);
			unite(x,y);
		}
	}
	set<int>::iterator it;
	int sum=0,len=s.size();
	for(it=s.begin ();it!=s.end ();it++)
    {
        if(par[*it]==*it) sum++;
    }
    cout<<len<<" "<<sum<<endl;
	int q;
	cin>>q;
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(same(a,b)) puts("Y");
		else puts("N");
	}
	
}

深入虎穴

原题链接

题目大意:

一扇门可以通往若干扇门,找到距离入口最远的那扇门。(不存在两条路通向同一扇门)

有个易坑点:入口没有确定。不是每次入口为1。因为不会有门通向入口,所以输入数据中没有出现过的那扇门就是入口了。

然后bfs或者dfs均可。

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>
using namespace std;
int vis[100000+10],maxx=0;
vector<int>g[100000+10];
struct node
{
	int step;
	int pos;
}cur,nex;
void bfs(int s)
{	cur.pos=s;
	cur.step=0;
	queue<node>que;
	que.push(cur);
	while(!que.empty())
	{
		cur=que.front();
		que.pop();
		
		for(int i=0;i<g[cur.pos].size();i++)
		{
			nex.pos=g[cur.pos][i];
			nex.step=cur.step+1;
			que.push(nex);
			
		}
	}
	cout<<cur.pos<<endl;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int k;
		cin>>k;
		while(k--)
		{
			int num;
			cin>>num;
			vis[num]=1;
			g[i].push_back(num);
		}
	}
	int st;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			st=i;
			break;
		}
	}//找入口
	
	bfs(st);
}

彩虹瓶

原题链接

思路:

题目模拟的过程其实就是一种数据结构:stack。

stack和queue类似,区别就是先进后出,后进先出。

那么按题意模拟即可。

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
#include<bits/stdc++.h>
using namespace std;
int a[1500],vis[1500];
int main()
{
	int n,m,k;
	cin>>n>>m>>k;
	while(k--)
	{	int flag=1;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		int num=1,now=1;
		stack<int>s;
		while(num!=n)
		{	
			if(a[now]==num)//刚好可以直接放的情况
			{
				num++;
				now++;
				continue;
			}
			else if(!s.empty()&&s.top()==num)//货架顶部刚好是的情况
				{
					s.pop();
					num++;
				}
			else if(s.size()<m)//暂时先不能放的情况,如果货架还有空间的话push
				{	vis[a[now]]=1;
					s.push(a[now++]);
				}		
			else  
				{
				flag=0;
				break;
				}
			
		}
		if(flag) puts("YES");
		else puts("NO");
	}
}