原题链接
给出一个家族每个家庭成员的父或母, 其中第 i 个编号对应第 i 位成员的父/母 。
输出最小的辈分,以及顺序输出最小辈分成员的编号。
9
2 6 5 5 -1 5 6 4 7
4
1 9
用vector存下每个人的kid。
然后找到老祖宗,从上往下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
|
#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即可。
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。若存在多条“食物链”,请找出字典序最小的。
5
-LWDW
W-LDW
WW-LW
DWW-W
DDLW-
1 3 5 4 2
1
2
3
4
5
6
|
5
-WDDW
D-DWL
DD-DW
DDW-D
DDDD-
|
No Solution
1.首先注意题目说的是每个球队之间会踢两场,所以题目表中L也要记录胜场。
2.注意到如果存在这样一条食物链,那么其实是个环,也就是说1号球队一定在其中,满足字典序最小的一定也是1号球队开始的,所以只要以1号球队为起点做一次dfs即可。
3.剪枝:把赢过1号球队的队伍先做个标记。在dfs访问一个节点时判断一下剩下来没有访问的队伍中还有没有赢过1队的,没有直接return。(这题的精髓,没有会超时)
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
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,并标记这些点距离起点的距离,距离相等且序号更小时更新。
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);
}
}
|