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

题意

有n把椅子排成一排，0表示没人坐，1表示有人坐。现问你这排椅子是否符合两个规则：

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

题解

首先，没有相邻的两个1，然后，没有相邻的三个0，最后，首尾没有相邻的两个0，注意特判只有一个字符0

代码

• 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

题意

乘客按照要求选择座位，0选择两个座位都是空的且宽度最小，1选择一个座位是空的且宽度最大。

题解

按照宽度从小到大排序后，用栈进行模拟。具体参见代码。

代码

• 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

题意

给定一颗树，n个节点，n-1条边，问最多能去掉多少条边，使得剩余的每个联通分量的大小都是偶数。

题解

首先，节点数量n必须是偶数才符合要求。

当n为偶数时，对整颗数进行dfs遍历，统计某个节点及其子节点的数量之和，如果递归到底统计的数量为偶数，那么答案加一。

代码

• 版本一

// Accepted    - 62ms - 6900KB

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

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

void init()
{
    cnt = 1, ans = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

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);
        add(u, v);
        add(v, u);
    }
    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;
}

第三题参考了上紫的题解和Chen_Jr_的题解，又复习了链式前向星，第四题是并查集，应该能补上。

The end.
2018-05-26 星期六