# Codeforces Round #484 (Div. 2)（模拟+bfs）

## A. Row（模拟）

• time limit per test：1 second
• memory limit per test：256 megabytes

You're given a row with nn chairs. We call a seating of people "maximal" if the two following conditions hold:

1. There are no neighbors adjacent to anyone seated.
2. It's impossible to seat one more person without violating the first rule.

The seating is given as a string consisting of zeros and ones (0 means that the corresponding seat is empty, 1 — occupied). The goal is to determine whether this seating is "maximal".

Note that the first and last seats are not adjacent (if n≠2).

### Input

The first line contains a single integer nn (1≤n≤1000) — the number of chairs.

The next line contains a string of nn characters, each of them is either zero or one, describing the seating.

### Output

Output "Yes" (without quotation marks) if the seating is "maximal". Otherwise print "No".

You are allowed to print letters in whatever case you'd like (uppercase or lowercase).

### Examples

3
101
Yes
4
1011
No
5
10001
No

### Note

In sample case one the given seating is maximal.

In sample case two the person at chair three has a neighbour to the right.

In sample case three it is possible to seat yet another person into chair three.

### 链接

http://codeforces.com/contest/982/problem/A

### 题意

• 没有两个相邻的人坐在一起
• 符合上面规则后，椅子上不能再坐人

### 代码

• Accepted
• 30 ms
• 0 KB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1010;
char s[maxn];

int main()
{
int n;
scanf("%d", &n);
scanf("%s", s);
bool flag = false;
if (n == 1 && s[0] == '0')
flag = true;
else if ((s[0] == '0' && s[1] == '0') || (s[n-1] == '0' && s[n-2] == '0'))
flag = true;
else
{
for (int i = 0; i < n - 1; ++i)
if (s[i] == '1' && s[i+1] == '1')
{
flag = true;
break;
}
for (int i = 0; i < n - 2; ++i)
if (s[i] == '0' && s[i+1] == '0' && s[i+2] == '0')
{
flag = true;
break;
}
}
if (flag)
printf("NO\n");
else
printf("YES\n");
return 0;
}

## B. Bus of Characters（栈）

• time limit per test：2 seconds
• memory limit per test：256 megabytes

In the Bus of Characters there are nn rows of seat, each having 2 seats. The width of both seats in the ii-th row is wiwicentimeters. All integers wiwi are distinct.

Initially the bus is empty. On each of 2n stops one passenger enters the bus. There are two types of passengers:

• an introvert always chooses a row where both seats are empty. Among these rows he chooses the one with the smallest seats width and takes one of the seats in it;
• an extrovert always chooses a row where exactly one seat is occupied (by an introvert). Among these rows he chooses the one with the largest seats width and takes the vacant place in it.

You are given the seats width in each row and the order the passengers enter the bus. Determine which row each passenger will take.

### Input

The first line contains a single integer nn (1≤n≤200000) — the number of rows in the bus.

The second line contains the sequence of integers w1,w2,…,wn($1≤w_i≤10^9$), where wiwi is the width of each of the seats in the ii-th row. It is guaranteed that all wiwi are distinct.

The third line contains a string of length 2n, consisting of digits '0' and '1' — the description of the order the passengers enter the bus. If the j-th character is '0', then the passenger that enters the bus on the j-th stop is an introvert. If the j-th character is '1', the the passenger that enters the bus on the jj-th stop is an extrovert. It is guaranteed that the number of extroverts equals the number of introverts (i. e. both numbers equal nn), and for each extrovert there always is a suitable row.

### Output

Print 2n2n integers — the rows the passengers will take. The order of passengers should be the same as in input.

### Examples

2
3 1
0011
2 1 1 2 
6
10 8 9 11 13 5
010010011101
6 6 2 3 3 1 4 4 1 2 5 5 

### Note

In the first example the first passenger (introvert) chooses the row 2, because it has the seats with smallest width. The second passenger (introvert) chooses the row 1, because it is the only empty row now. The third passenger (extrovert) chooses the row 1, because it has exactly one occupied seat and the seat width is the largest among such rows. The fourth passenger (extrovert) chooses the row 2, because it is the only row with an empty place.

### 链接

http://codeforces.com/contest/982/problem/B

### 代码

• Accepted
• 187 ms
• 3700 KB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int maxn = 200010;

struct Seat
{
int id;
int weight;
}seat[maxn];

char s[maxn * 2];

bool cmp(Seat a, Seat b)
{
return a.weight < b.weight;
}

stack <Seat> st;

int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &seat[i].weight);
seat[i].id = i;
}
scanf("%s", s + 1);
sort(seat + 1, seat + n + 1, cmp);
int k = 1;
for (int i = 1; i <= n * 2; ++i)
{
if (s[i] == '0') // 0选择座位，从小到大
{
st.push(seat[k++]);
printf("%d", seat[k-1].id);
}
else
{
printf("%d", st.top().id); // 1从栈顶开始选择座位
st.pop();
}
if (i < 2 * n)
printf(" ");
}
printf("\n");
return 0;
}

## C. Cut 'em all!（bfs）

• time limit per test：1 second
• memory limit per test：256 megabytes

You're given a tree with n vertices.

Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size.

### Input

The first line contains an integer n ($1≤n≤10^5$) denoting the size of the tree.

The next n−1 lines contain two integers u, v (1≤u,v≤n) each, describing the vertices connected by the i-th edge.

It's guaranteed that the given edges form a tree.

### Output

Output a single integer k — the maximum number of edges that can be removed to leave all connected components with even size, or −1 if it is impossible to remove edges in order to satisfy this property.

### Examples

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

### Note

In the first example you can remove the edge between vertices 1 and 4. The graph after that will have two connected components with two vertices in each.

In the second example you can't remove edges in such a way that all components have even number of vertices, so the answer is −1.

### 链接

http://codeforces.com/contest/982/problem/c

### 代码

• 版本一
// Accepted    - 62ms - 6900KB

#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200010;
int sum[maxn];
int n, cnt, ans;

struct Edge
{
int next, to;
}edge[maxn];

void init()
{
cnt = 1, ans = 0;
}

{
edge[cnt].to = v;
}

void dfs(int u, int fu)
{
sum[u] = 1;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (v != fu)
{
dfs(v, u);
sum[u] += sum[v]; // 节点及其子节点的数量之和
}
}
if (!(sum[u] & 1)) // 统计的数量为偶数
{
ans++;
sum[u] = 0;
}
}

int main()
{
int u, v;
init();
scanf("%d", &n);
for (int i = 0; i < n - 1; ++i)
{
scanf("%d%d", &u, &v);
}
if (n & 1)
printf("-1\n");
else
{
dfs(1, 1);
printf("%d\n", ans - 1);
}
return 0;
}
• 版本二
// Accepted - 77ms - 6800KB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int maxn = 100010;
vector <int> G[maxn];
int n, ans;

int dfs(int u, int fu)
{
int cnt = 0;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (v != fu)
{
int tmp = dfs(v, u); // 得到子树的节点数
if (!(tmp & 1)) // 节点树为偶数，切一刀
ans++;
cnt += tmp;
}
}
return cnt + 1;
}

int main()
{
int u, v;
scanf("%d", &n);
for (int i = 0; i < n - 1; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
if (n & 1)
{
printf("-1\n");
return 0;
}
ans = 0;
dfs(1, 1);
printf("%d\n", ans);
return 0;
}

The end.
2018-05-26 星期六