小花生

study & life record.

Educational Codeforces Round 166 (Rated for Div.2)

发表于 分类于 ，

5月30日 Codeforces 实战记录。（1559 -> 1495）

比赛跳转：Educational Codeforces Round 166 (Rated for Div.2)

题解

A. Verify Password

题意：

  • password should consist only of lowercase Latin letters and digits;
  • there should be no digit that comes after a letter (so, after each letter, there is either another letter or the string ends);
  • all digits should be sorted in the non-decreasing order;
  • all letters should be sorted in the non-decreasing order.

分析：以上所有条件等价于：按 ASCII 码升序排序。（模拟题意就慢了）

完整代码：

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
#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read();
    string s, ss;
    cin >> s;
    ss = s;
    sort(s.begin(), s.end());
    if(s == ss) cout << "YES" << '\n';
    else cout << "NO" << '\n';	
}

int main(){
    int t = read();
    while(t--){
        solve();
    }
    return 0;
}

B. Increase/Decrease/Copy

分析：关键在找出 copy 后，最后一项的最小改变次数。

完整代码：

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read();
    vector<int>a(n), b(n + 1);
    for(auto &i : a) i = read();
    for(auto &i : b) i = read();
    int x = b[n];
    int mindis = 0x3f3f3f3f;
    
    int res = 1;
    for(int i = 0; i < n; i++){
        if(a[i] < b[i]) swap(a[i], b[i]);
        res += a[i] - b[i];
        if(a[i] >= x && x >= b[i]) mindis = 0;
        else if(x > a[i]) mindis = min(mindis, x - a[i]);
        else if(x < b[i]) mindis = min(mindis, b[i] - x);
    }
    
    cout << res + mindis << '\n';
}

signed main(){
    int t = read();
    while(t--){
        solve();
    }
    return 0;
}

C. Job Interview

分析：用树状数组维护已经 hire 的 programmer 的个数与 tester 的个数，二分查询，找出一方已经招满的最小位置，再用预处理过的前缀和直接计算。

完整代码：

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

const int N = 2e5 + 10;
int n, m, s;
int a[N], b[N];
int c[N], d[N];
int sma[N], smb[N];
int suma[N], sumb[N];

int lowbit(int x) { return x & -x; }

void add(int tr[], int x, int a) { for (int i = x; i <= s; i += lowbit(i)) tr[i] += a; }

int sum(int tr[], int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += tr[i]; return res; }

void solve() {
    memset(c, 0, sizeof c);
    memset(d, 0, sizeof d);

    n = read(), m = read(), s = n + m + 1;
    for (int i = 1; i <= s; i++) a[i] = read();
    for (int i = 1; i <= s; i++) b[i] = read();
    for (int i = 1; i <= s; i++) {
        if (a[i] > b[i]) {
            add(c, i, 1);
            sma[i] = a[i] + sma[i - 1];
            smb[i] = smb[i - 1];
        }
        else {
            add(d, i, 1);
            smb[i] = b[i] + smb[i - 1];
            sma[i] = sma[i - 1];
        }
        suma[i] = suma[i - 1] + a[i];
        sumb[i] = sumb[i - 1] + b[i];
    }

    for (int i = 1; i <= s; i++) {
        add(c, i, -(a[i] > b[i]));
        add(d, i, -(b[i] > a[i]));

        int l = 0, r = s;
        while (l < r) {
            int mid = l + r >> 1;
            if (sum(c, mid) >= n) r = mid;
            else l = mid + 1;
        }
        int posn = l;

        l = 0, r = s;
        while (l < r) {
            int mid = l + r >> 1;
            if (sum(d, mid) >= m) r = mid;
            else l = mid + 1;
        }
        int posm = l;

        int res = 0;
        if (posn > posm) {
            res = sma[posm] + smb[posm] + (suma[s] - suma[posm]);
            if (i <= posm) {
                if (a[i] > b[i]) res -= a[i];
                else res -= b[i];
            }
            else res -= a[i];
        }
        else {
            res = sma[posn] + smb[posn] + (sumb[s] - sumb[posn]);
            if (i <= posn) {
                if (a[i] > b[i]) res -= a[i];
                else res -= b[i];
            }
            else res -= b[i];
        }

        cout << res << ' ';

        add(c, i, a[i] > b[i]);
        add(d, i, b[i] > a[i]);
    }
    puts("");
}

signed main() {
    int t = read();
    while (t--) solve();
    return 0;
}