Codeforces Round 442 (Div. 2) 题解

2017/10/28

A. Alex and broken contest

签到题。

 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
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;

string c[] = {"Danil", "Olya", "Slava", "Ann", "Nikita"};

int main() {
    char buf[300]; scanf("%s", buf);
    string t(buf);
    
    int cnt = 0;
    for(string s : c) {
        if(t.find(s) != string::npos) {
            cnt++;
            
            if(t.find(s, t.find(s) + s.size()) != string::npos)
                return puts("NO"), 0;
        }
    }
    
    puts(cnt == 1 ? "YES" : "NO");
}

B. Nikita and string

继续签到

 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
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

int N;
char buf[5007];

int preB[5007], posB[5007];
int preA[5007];
// pre[x] -> [1, x]
// pos[x] -> [x, N]

int main() {
    scanf("%s", buf + 1);
    N = strlen(buf + 1);
    
    for(int i=1;i<=N;i++) {
        preA[i] = preA[i-1] + (buf[i] == 'a');
        preB[i] = preB[i-1] + (buf[i] == 'b');
    }
    
    for(int i=N;i;i--) {
        posB[i] = posB[i+1] + (buf[i] == 'b');
    }
    
//  for(int i=1;i<=N;i++) {
//      printf("%d %d %d\n", preA[i], preB[i], posB[i]);
//  }
    
    int ans = INT_MAX;
    for(int i=1;i<=N;i++) {
        for(int j=i;j<=N+1;j++) {
            int cur = preB[i-1] + (preA[j-1] - preA[i-1]) + posB[j];
//          printf("[1, %d) [%d, %d) [%d, N] = %d\n", i, i, j, j, cur);
            ans = min(ans, cur);
        }
    }
    
    printf("%d", N - ans);
}

C. Slava and tanks

构造型签到题。

 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
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int N;
int main() {
    scanf("%d", &N);
    int x = N>>1;

    printf("%d\n", x + N);

    for(int i=2;i<=N;i+=2) {
        printf("%d ", i);
    }

    for(int i=1;i<=N;i+=2) {
        printf("%d ", i);
    }

    for(int i=2;i<=N;i+=2) {
        printf("%d ", i);
    }

    puts("");
}

D. Olya and Energy Drinks

给一个长方形占用矩阵,有一个人可以在空白位置行走,每次最多可以沿上下左右方向走 k 格。

求给定起点到终点的最小次数。

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
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
const int SIZ = 3007;

int N, M, K;
int sx, sy, tx, ty;
int dx[] = {0, 0, 1,-1};
int dy[] = {1,-1, 0, 0};
char Mat[SIZ][SIZ];
int ans[SIZ][SIZ];

bool valid(int x, int y) {
    return min(x, y) > 0 && x <= N && y <= M && Mat[x][y] != '#';
}

int bfs() {
    queue<pii> q; q.push(pii(sx, sy));
    memset(ans, 0x3f, sizeof(ans));
    ans[sx][sy] = 0;
    
    while(!q.empty()) {
        int cx = q.front().first, cy = q.front().second; q.pop();
        
        if(cx == tx && cy == ty) {
            return ans[cx][cy];
        }
        
        for(int i=0;i<4;i++) {
            int nx = cx + dx[i], ny = cy + dy[i];
            for(int k=1;k <= K && valid(nx, ny);k++) {
                if(ans[nx][ny] <= ans[cx][cy]) break;
                if(ans[nx][ny] == 0x3f3f3f3f) q.push(pii(nx, ny));
                ans[nx][ny] = ans[cx][cy] + 1;
                
                nx = nx + dx[i], ny = ny + dy[i];
            }
        }
    }
    
    return -1;
}

int main() {
    scanf("%d %d %d", &N, &M, &K);

    for(int i=1;i<=N;i++)
        scanf("%s", Mat[i] + 1);
    
    scanf("%d %d %d %d", &sx, &sy, &tx, &ty); 
    
    printf("%d\n", bfs());
}

E. Danil and a Part-time Job

树上每个点有一个二进制权值,每次操作子树按位取反,询问子树和。

转 dfs 序后线段树维护。

  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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int SIZ = 4e5 + 2007;

int N;

struct tgno {
    int v; tgno* n;
} POOL[SIZ], *Head[SIZ]; int ppos;

void _add(int u, int v) {
    POOL[ppos].v = v;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v) {
    _add(u, v), _add(v, u);
}

int L[SIZ], R[SIZ]; int T = 0;
void dfs(int u = 1, int pre = 0) {
    L[u] = ++T;
    
    typedef tgno* It;
    for(It i=Head[u];i;i=i->n) {
        if(i->v != pre) dfs(i->v, u);
    }
    
    R[u] = T;
}

#define lson(x) ((x) << 1)
#define rson(x) (lson(x) | 1)
int sum[SIZ<<1], l[SIZ<<1], r[SIZ<<1];
int lzy[SIZ<<1]; // 1 for inversion
int M;

void pdown(int x) {
    if(lzy[x] && x < M) {
        lzy[lson(x)] ^= 1;
        lzy[rson(x)] ^= 1;
        
        sum[lson(x)] = (r[lson(x)] - l[lson(x)] + 1) - sum[lson(x)];
        sum[rson(x)] = (r[rson(x)] - l[rson(x)] + 1) - sum[rson(x)];
    }
    
    lzy[x] = 0;
}

void pup(int x) {
    sum[x] = sum[lson(x)] + sum[rson(x)];
}

void initSeg(int C) {
    for(M=1;M<=C;M<<=1);
    
    int k = 0;
    
    for(int i=1;i<=N;i++) {
        scanf("%d", &k);
        sum[M - 1 + L[i]] = k;
    }
    for(int i=0;i<M;i++) l[M + i] = r[M + i] = i + 1;
    
    for(int i=M-1;i;i--) {
        pup(i);
        l[i] = l[lson(i)];
        r[i] = r[rson(i)];
    }
}

void change(int Ql, int Qr, int x = 1) {
    if(l[x] == Ql && r[x] == Qr) {
        lzy[x] ^= 1;
        sum[x] = (r[x] - l[x] + 1) - sum[x];
        return;
    }
    
    pdown(x);
    int Mid = (l[x] + r[x]) >> 1;
    
    if(Qr <= Mid) change(Ql, Qr, lson(x));
    else if(Ql > Mid) change(Ql, Qr, rson(x));
    else change(Ql, Mid, lson(x)), change(Mid+1, Qr, rson(x));
    pup(x);
}

int query(int Ql, int Qr, int x = 1) {
    pdown(x);
    
    if(l[x] == Ql && r[x] == Qr) {
        return sum[x];
    }
    
    int Mid = (l[x] + r[x]) >> 1;
    int ret = 0;
    if(Qr <= Mid) ret = query(Ql, Qr, lson(x));
    else if(Ql > Mid) ret = query(Ql, Qr, rson(x));
    else ret = query(Ql, Mid, lson(x)) + query(Mid+1, Qr, rson(x));
    pup(x);
    return ret;
}

int main() {
    scanf("%d", &N);
    
    int v;
    for(int i=2;i<=N;i++) {
        scanf("%d", &v);
        addEdge(i, v);
    }
    
    dfs();
    // Eular [1, T]

    initSeg(T + 1);
    int Q; scanf("%d", &Q);
    
    char op[32]; int x;
    while(Q--) {
        scanf("%s %d", op, &x);
        
        if(op[0] == 'g') {
            printf("%d\n", query(L[x], R[x]));
        } else {
            change(L[x], R[x]);
        }
    }
}