Educational Codeforces Round 53 题解

2018/11/08

我(文化课)又菜了。

A. Diverse Substring

无脑爆搜。

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAX = 2001;
char buf[MAX];

int check(int i, int j) {
    static int lut[26];
    memset(lut, 0, sizeof(lut));
    int t = (j - i + 1) >> 1;
    
    for(int x=i;x<=j;x++) {
        lut[buf[x] - 'a']++;
        if(lut[buf[x] - 'a'] > t)
            return 0;
    }
    
    return 1;
}

int main() {
    int x;
    scanf("%d", &x);
    scanf("%s", buf+1);
    
    for(int i=1;i<=x;i++) {
        for(int j=i;j<=x;j++) {
            if(check(i, j)) {
                buf[j + 1] = 0;
                return printf("YES\n%s", buf + i), 0;
            }
        }
    }
    
    return printf("NO\n"), 0;
}

B. Bus of Characters

模拟。

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int SIZ = 2e5 + 1007;
int N, stk[SIZ], ord[SIZ], lut[SIZ];

int main() {
    scanf("%d", &N);
    
    for(int i=1;i<=N;i++)
        scanf("%d", &stk[i]);
    
    for(int i=1;i<=N;i++)
       scanf("%d", &ord[i]);
    
    int tp = 1;
    for(int i=1;i<=N;i++) {
        if(lut[ord[i]]) printf("%d ", 0);
        else {
            int c = 0;
            for(;tp<=N && stk[tp]!=ord[i];tp++)
                lut[stk[tp]] = 1, c++;
            lut[stk[tp++]] = 1;
            printf("%d ", c + 1);
        }
    }
    puts("");
}

C. Vasya and Robot

首先二分答案,假设某区间代表的向量是 a,目标 - 实际向量是 b,该区间可行当且仅当能构造出 a + b

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
using namespace std;
const int SIZ = 2e5 + 1007, inf = 1e9 + 7;
int N;
char buf[SIZ];

struct xy {
    int x, y;
    
    friend xy operator+(const xy &lhs, const xy &rhs) {
        return xy { lhs.x + rhs.x, lhs.y + rhs.y };
    }
    
    friend xy operator-(const xy &lhs, const xy &rhs) {
        return xy { lhs.x - rhs.x, lhs.y - rhs.y };
    }
    
    friend bool operator==(const xy &lhs, const xy &rhs) {
        return lhs.x == rhs.x && lhs.y == rhs.y;
    }
} dl[128], pfx[SIZ], tgt, dta; // magic lut

inline int iabs(int x) {
    return x > 0 ? x : -x; 
}

bool check_impl(int l, int r) {
    xy cp = pfx[r] - pfx[l-1];
    xy n = cp + dta;
    int ln = iabs(n.x) + iabs(n.y);
    int nn = r - l + 1;
    
    if(ln > nn || (ln & 1) != (nn & 1))
        return false;
    
    return true;
}

bool check(int len) {
    int _ = N - len + 1;
    for(int i=1;i<=_;i++)
        if(check_impl(i, i+len-1))
            return true;
    return false;
}

int main() {
    scanf("%d %s %d %d", &N, buf + 1, &tgt.x, &tgt.y);
    
    dl['U'].y = 1;
    dl['D'].y =-1;
    dl['L'].x =-1;
    dl['R'].x = 1;
    
    xy cp{0,  0};
    for(int i=1;i<=N;i++) {
        cp = cp + dl[buf[i]];
        pfx[i] = cp;
    }
    
    dta = tgt - cp;
    
    int ln = iabs(tgt.x) + iabs(tgt.y);
    
    if(ln > N || (ln & 1) != (N & 1))
        return puts("-1"), 0;
    
    if(cp == tgt)
        return puts("0"), 0;
    
    int L = 0, R = N; // (L, R]
    while(L + 1 < R) {
        int Mid = (L + R) >> 1;
        if(check(Mid))
            R = Mid;
        else
            L = Mid;
    }
    
    return printf("%d\n", R), 0;
}

D. Berland Fair

模拟。

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int SIZ = 2e5 + 1007;
int N;
ull pri[SIZ], mon;

int main() {
    scanf("%d %lld", &N, &mon);
    
    for(int i=1;i<=N;i++)
        scanf("%lld", &pri[i]);
    ull ans = 0;
    
    while(true) {
        int cnt = 0;
        ull tot = 0;
        for(int i=1;i<=N;i++)
            if(pri[i] <= mon) tot += pri[i], cnt++;    
        if(cnt == 0) break;
        
        ans += (mon / tot) * cnt;
        mon %= tot;
        for(int i=1;i<=N;i++)
            if(mon >= pri[i]) ans++, mon -= pri[i];
    }
    
    printf("%lld\n", ans);
}