Andrewei's Blog
0%

Codeforces Round #325 (Div. 2)

发表于 更新于 分类于 ，

比赛链接：http://codeforces.com/contest/586

A题(Alena’s Schedule)

题目大意：

抽象出来就是给你一个 01 串，去除前导零和末尾的零后，统计 1 的个数与连续小于 2 的 0 的个数的和。

解题思路：

模拟一下这个统计过程就行了。

参考程序：

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
/*=============================================================================
# Author:			DATASOURCE
# Last modified: 	2015-10-12 16:41
# Filename: 		a.cpp
# Description: 
=============================================================================*/

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l, mid, ls
#define rson mid, r, rs
#define ls (rt << 1) + 1
#define rs (rt << 1) + 2
using namespace std;
const int MAXN = 110;

int a[MAXN];

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        int ans = 0, num = 0, dx = 0;
        while(!a[dx]) dx++;
        for(int i = dx; i <= n; i++){
            if(a[i]){ 
                ans++;
                if(num <= 1) ans += num;
                num = 0;
            } else num++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B题(Laurenty and Shop)

题目大意：

有两排楼房，每排有 $n(2 <= n <= 50)$栋，同一排相邻两栋之间的距离为 $a_i$(1 <= i < n), 两排楼房之间有条街道，街道相隔的面对面的两栋楼房的距离为 $b_i$(1 <= $b_i$ <= 100, 1 <= i <= n), 现在小明要从最右下角的一栋楼房去左上角的一栋楼房再返回并且来回不能走完全相同的道路，并且小明只能去的时候穿过一次中间的街道回来穿过一次，求小明最少走多少路(这蛋疼的题目意思。。。。。)

解题思路：

维护第一排楼房之间距离的前缀和和第二排楼房之间距离的后缀和然后遍历所有情况取个最小就行。

参考代码：

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
/*=============================================================================
# Author:			DATASOURCE
# Last modified: 	2015-10-12 17:32
# Filename: 		b.cpp
# Description: 
=============================================================================*/

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l, mid, ls
#define rson mid, r, rs
#define ls (rt << 1) + 1
#define rs (rt << 1) + 2
using namespace std;
const int MAXN = 110;

int a1[MAXN];
int a2[MAXN];
int b[MAXN];

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        memset(a1, 0, sizeof(a1));
        memset(a2, 0, sizeof(a2));

        for(int i = 1; i < n; i++)
            scanf("%d", &a1[i]);
        for(int i = 0; i < n - 1; i++)
            scanf("%d", &a2[i]);
        for(int i = 0; i < n; i++)
            scanf("%d", &b[i]);

        for(int i = 1; i <= n; i++)
            a1[i] = a1[i - 1] + a1[i];
        for(int i = n - 2; i >= 0; i--)
            a2[i] = a2[i + 1] + a2[i];

        int ans = (1 << 29);
        for(int i = 0; i < n; i++)
            for(int j = i + 1; j < n; j++){
                ans = min(ans, a1[i] + a2[i] + b[i] + a1[j] + a2[j] + b[j]);
            }
        printf("%d\n", ans);
    }
    return 0;
}

C题(Gennady the Dentist)

题目大意：

编号为 1 – n 的 $n(1 <= n <= 4000)$ 个孩子按照编号顺序去看牙医,  每次只有一个孩子进去诊疗室其余的孩子在大厅等候，进入的诊疗室的孩子一定会哭，每个孩子都有三个值 $v_i, d_i, p_i$ (1 <= $v_i, d_i, p_i$ <= $10^6$, $v_i, d_i$ 代表了他哭时的杀伤力, $p_i$代表这个孩子的自信心,  当这个孩子的自信心小于0时，这个孩子会哭，然后跑掉。当在诊疗室里的孩子 i 哭时，他会使编号比他小的孩子的自信心分别减少 $v_i, v_i - 1, v_i - 2, …. 0$, 如果这个影响使得大厅里的孩子 j 也哭的话，这个大厅里的孩子会使所有在大厅中的孩子的自信心减少 $d_j$, 再强调一遍，一个在大厅的孩子如果哭了的话，他会跑掉，问最后医生可以给多少个孩子看病。

解题思路：

模拟一下这个过程就行了，注意一点，用 int 时，$p_i$ 在减少是有可能爆掉！！

参考代码：

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
/*=============================================================================
# Author:			DATASOURCE
# Last modified: 	2015-10-12 17:56
# Filename: 		c.cpp
# Description: 
=============================================================================*/

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson l, mid, ls
#define rson mid, r, rs
#define ls (rt << 1) + 1
#define rs (rt << 1) + 2
using namespace std;
const int MAXN = 4200;

bool vis[MAXN];
long long v[MAXN];
long long d[MAXN];
long long p[MAXN];
long long res[MAXN];

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        for(int i = 1; i <= n; i++)
            scanf("%I64d%I64d%I64d", &v[i], &d[i], &p[i]);

        int ans = 0;
        fill(vis, vis + MAXN, 1);
        for(int i = 1; i <= n; i++)if(vis[i]){
            res[ans++] = i;
            int tmp = v[i];
            for(int j = i + 1; j <= n; j++)if(vis[j]){
                p[j] -= tmp;
                tmp--;
                if(tmp == 0) break;
            }
            for(int j = i + 1; j <= n; j++)if(vis[j] && p[j] < 0){
                vis[j] = 0;
                for(int k = j + 1; k <= n; k++)if(vis[k]) p[k] -= d[j];
            }
        }

        printf("%d\n", ans);
        for(int i = 0; i < ans; i++)
            printf("%I64d%c", res[i], i == ans - 1 ? '\n' : ' ');

    } 
    return 0;
}

D题(Phillip and Trains)

题目大意：

给一个3*n的地图，人s从最左边一列的某个位置出发，每次先向右走一步，再选择上、下、不动。接着连续的字母表示火车，均向左走两步。如此循环，人和火车不能相撞。问人是否能走到地图的最右边。

解题思路：

火车向左走两步可以看做火车不动，人向右移动两步，这样的话人每次可以有三种状态:

  1. 向右走一步后再向右走两步;
  2. 向右走一步后再向上走一步再向右走两步；
  3. 向右走一步后再向下走一步再向右走两步;
    参考代码：
    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
    /*=============================================================================
    # Author:			DATASOURCE
    # Last modified: 	2015-10-12 18:33
    # Filename: 		d.cpp
    # Description: 
    =============================================================================*/

    #include <map>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <cstdio>
    #include <string>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define lson l, mid, ls
    #define rson mid, r, rs
    #define ls (rt << 1) + 1
    #define rs (rt << 1) + 2
    using namespace std;
    const int MAXN = 110;
    int t, n, k;
    char ch[MAXN];
    char mp[4][MAXN];
    bool vis[4][MAXN];

    struct State{
        int x, y;
    };

    int dir[][2] = {-1, 1, 1, 1, 0, 1};

    bool bfs(int dx){
        State a, b, c;
        a.x = dx, a.y = 0;
        memset(vis, 0, sizeof(vis));
        vis[dx][0] = true;
        queue <State> que;
        que.push(a);
        while(!que.empty()){
            b = que.front();
            que.pop();
            if(b.y >= n - 1) return true;
            for(int i = 0; i < 3; i++){
                if(mp[b.x][b.y + 1] != '.') break;
                int dx = b.x + dir[i][0];
                int dy = b.y + dir[i][1];
                if(dx >= 0 && dx < 3 && dy >= 0 && dy < n && !vis[dx][dy + 2] && mp[dx][dy] == '.' && mp[dx][dy + 1] == '.' && mp[dx][dy + 2] == '.'){
                    c.x = dx, c.y = dy + 2;
                    vis[c.x][c.y] = true;
                    que.push(c);
                }
            }
        }
        return false;
    }

    int main(){
        scanf("%d", &t);
        while(t--){
            fill(mp[0], mp[4], '.');
            scanf("%d%d", &n, &k);
            for(int i = 0; i < 3; i++){
                scanf(" %s", mp[i]);
                mp[i][n] = '.';
            }
            int dx = 0;
            for(int i = 0; i < 3; i++)
                if(mp[i][0] == 's') dx = i;
           bool ans = bfs(dx);
           if(ans) printf("YES\n");
           else printf("NO\n");
        }
        return 0;
    }