codeforces 902

题目链接

http://codeforces.com/contest/902

分题详解

A.Visiting a Friend

题目大意:Pig的房子的位置在0,他的朋友的房子的位置是m,现在有n个传送带,问Pig能否通过这些传送带到达他朋友的位置。
解题思路:排序之后,遍历一遍所有的传送带,如果最后可以到达的位置不小于m,那么它就可以到达m。

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 <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

struct Node{
int a, b;
bool operator < (const Node & node)const{
if (a == node.a){
return b < node.b;
}
return a < node.a;
}
Node(int aa, int bb) : a(aa), b(bb){}
};
vector<Node> v;
int main(){
int n,m;
cin >> n >> m;
int ta, tb;
for (int i = 0; i < n; ++i){
cin >> ta >> tb;
v.push_back(Node(ta, tb));
}
sort(v.begin(), v.end());
int x = 0;
bool ans = false;
for (int i = 0; i < n; ++i){
if (x >= m){
ans = true;
break;
}
if (x >= v[i].a){
x = max(x, v[i].b);
}
}
if (x >= m){
ans = true;
}
if (ans){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
return 0;
}

B.Coloring a Tree

题目大意:给你一颗树,问要把每个节点涂色,最少需要多少步。涂色中间的某个节点的话,当前节点下的子树都会被涂色。
解题思路:建好树之后,广度优先搜索检查每个节点的孩子节点是否是当前节点需要涂的颜色一致,不一致的话结果加1,考虑到节点比较多,深度优先搜索可能爆栈,另外节点1e4的话,用邻接表来保存边,当然vector也可以。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

int head[10100];
int color[10100];
int edge_cnt;
int u[20010];
int v[20010];
int pre[20010];
bool vis[10010];
void init(){
memset(vis, false, sizeof vis);
vis[1] = true;
memset(head, 0, sizeof head);
edge_cnt = 0;
}
void add_edge(int u_val, int v_val){
u[edge_cnt] = u_val;
v[edge_cnt] = v_val;
pre[edge_cnt] = head[u_val];
head[u_val] = edge_cnt;
++edge_cnt;
}
struct Node{
int x;
int c;
Node(int xx, int cc) : x(xx), c(cc){}
};

queue<Node> Q;

void bfs(int x){
vis[x] = true;
Q.push(Node(x,color[x]));
int ans = 1;
while (!Q.empty()){
Node tmp = Q.front();
Q.pop();
for (int i = head[tmp.x]; i != 0; i = pre[i]){
if (vis[v[i]] == false){
if(color[v[i]] != tmp.c){
++ans;
}
Q.push(Node(v[i], color[v[i]]));
vis[v[i]] = true;
}
}
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
init();
int tmp;
for (int i = 2;i <= n; ++i){
cin >> tmp;
add_edge(i, tmp);
add_edge(tmp, i);
}
for (int i = 1; i <= n; ++i){
cin >> color[i];
}
bfs(1);
return 0;
}

C.Hashing Trees

题目大意:给你一棵树的每层的节点的个数,问你这样的树是否只有1棵。
解题思路:如果当前层和下一层的节点数都大于1的话,这样的树就不只有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
62
63
64
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int data[100100];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i <= n; ++i){
cin >> data[i];
}
bool perfect = true;
for (int i = 1; i <= n; ++i){
if (data[i - 1] > 1 and data[i] > 1){
perfect = false;
break;
}
}
if (perfect){
cout << "perfect" << endl;
}else{
cout << "ambiguous" << endl;
int cnt = 0;
int pre = 0;
int flag = false;
for (int i = 0; i <= n; ++i){
for (int j = 0; j < data[i]; ++j){
if(flag){
cout << " ";
}else{
flag = true;
}
if (j and i and data[i] > 1 and data[i - 1] > 1){
cout << cnt - 1;
}else{
cout << cnt;
}
++pre;
}
cnt = pre;
}
cout << endl;
cnt = 0;
pre = 0;
flag = false;
for (int i = 0; i <= n; ++i){
for (int j = 0; j < data[i]; ++j){
if(flag){
cout << " ";
}else{
flag = true;
}
cout << cnt;
++pre;
}
cnt = pre;
}
cout << endl;
}
return 0;
}

总结

C题,perfect打成了prefectcnt=pre写成了++cnt,结果错了两次,写题太不细心了,另外英语有点问题,emmmmmmmmmm。D题还没有思路。