USACO23Jan Bronze

没有什么好说的，都是简单送分题。

很可惜我场上对着 T2 想了半天 \(M \le 2e5\)，一小时后才发现 \(M \le 10\)。

小丑。

放个代码应该就能理解了。

T1 
 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
// author : black_trees

#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int n; cin >> n;
    string s; cin >> s;
    s = ' ' + s;
    int fg = 0, fh = 0;
    for(int i = 1; i <= n; ++i) {
        if(s[i] == 'G') {fg = i; break; }
    }
    for(int i = 1; i <= n; ++i) {
        if(s[i] == 'H') {fh = i; break; }
    }
    int lsg = 0, lsh = 0;
    for(int i = n; i >= 1; --i) {
        if(s[i] == 'G') {lsg = i; break; }
    }
    for(int i = n; i >= 1; --i) {
        if(s[i] == 'H') {lsh = i; break; }
    }
    std::vector<int> a(n + 2);
    for(int i = 1; i <= n; ++i) cin >> a[i];

    int leadg = 0, leadh = 0;
    if(a[fg] >= lsg) leadg = fg;
    if(a[fh] >= lsh) leadh = fh;
    int ans = (leadg && leadh);
    int cnt1 = 0, cnt2 = 0;
    for(int i = fg; i >= 1; --i) {
        if(s[i] == 'H' && i != leadh && a[i] >= leadg) ++cnt1;
    }
    for(int i = fh; i >= 1; --i) {
        if(s[i] == 'G' && i != leadg && a[i] >= leadh) ++cnt2;
    }
    if(leadg > 0) ans += cnt1;
    if(leadh > 0) ans += cnt2;
    cout << ans << endl;

    return 0;
}

// ()()()(?
T2 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 1e2 + 10;

int n, m;
int s[si], t[si], c[si];
int a[si], b[si], p[si], w[si];
int state[si];

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m;
    for(int i = 1; i <= n; ++i) 
        cin >> s[i] >> t[i] >> c[i];
    for(int i = 1; i <= m; ++i)
        cin >> a[i] >> b[i] >> p[i] >> w[i];
    int ans = 0x3f3f3f3f;
    for(int msk = 0; msk < (1 << m); ++msk) {
        memset(state, 0, sizeof state);
        int ret = 0;
        for(int i = 1; i <= m; ++i)
            if(msk >> (i - 1) & 1) {
                for(int j = a[i]; j <= b[i]; ++j)
                    state[j] += p[i];
                ret += w[i];
            }
        bool f = true;
        for(int i = 1; i <= n; ++i) {
            for(int j = s[i]; j <= t[i]; ++j) {
                if(state[j] < c[i]) {
                    f = false; break;
                }
            }
            if(!f) break;
        }
        if(!f) continue;
        ans = min(ans, ret);
    }   
    cout << ans << endl;

    return 0;
}

// ()()()(?
T3 
 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
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    int T; cin >> T;
    while(T--) {
        string s; cin >> s;
        int ans = 0x3f3f3f3f;
        int n = s.size(); s = ' ' + s;
        for(int i = 1; i + 2 <= n; ++i) {
            if(s[i + 1] != 'O') continue;
            int ret = (s[i] != 'M') + (s[i + 2] != 'O');
            ret += n - 3, ans = min(ans, ret);
        }
        cout << ((ans == 0x3f3f3f3f) ? -1 : ans) << endl;
    }

    return 0;
}

// ()()()(?
最后更新: May 9, 2023