2024“钉耙编程”中国大学生算法设计超级联赛1

1002、1008、1001

总结

成绩:SOLVE:3,Penalty:7

1002

签到题

非常裸的dp

 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
void SINGLE_TEST() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), b(n + 1), c(n + 1), d(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    vector<int> dp(k + 1, INF);
    dp[0] = 0;
    for (int id = 1; id <= n; id++) {
        for (int i = k; i >= 0; i--) {
            if (i - 1 >= 0) {
                dp[i] = min(dp[i], dp[i - 1] + a[id]);
            }
            if (i - 2 >= 0) {
                dp[i] = min(dp[i], dp[i - 2] + b[id]);
            }
            if (i - 3 >= 0) {
                dp[i] = min(dp[i], dp[i - 3] + c[id]);
            }
            if (i - 4 >= 0) {
                dp[i] = min(dp[i], dp[i - 4] + d[id]);
            }
        }
    }
    cout << dp[k] << "\n";
}

1008

根据n的每一位去分类,‘1’有12种,‘0’有4种

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void SINGLE_TEST() {
    int n, k;
    cin >> n >> k;
    ll anss = 1;
    for (int b = k; b >= 0; b--) {
        int t = (n >> b & 1);
        ll ans = 0;
        if (t == 1) {
            ans += 8 + 4;
        } else {
            ans += 4;
        }
        anss *= ans;
    }
    cout << anss / 4 << "\n";
}

1001

处理字符串相等时(字符串匹配),不难想到哈希解决

这里我们初步考虑存A的每一个循环串,但是空间太大,利用哈希简化即可

 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
const int P = 1E9 + 7;
void SINGLE_TEST() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    s = s + s;
    vector<ll> h1(2 * n + 1), h2(m + 1);
    vector<ll> p1(2 * n + 1), p2(m + 1);
    p1[0] = 1;
    p2[0] = 1;
    for (int i = 1; i <= 2 * n; i++) {
        p1[i] = p1[i - 1] * P;
        h1[i] = h1[i - 1] * P + s[i - 1];
    }
    for (int i = 1; i <= m; i++) {
        p2[i] = p2[i - 1] * P;
        h2[i] = h2[i - 1] * P + t[i - 1];
    }
    auto get1 = [&](int l, int r) { return h1[r] - h1[l - 1] * p1[r - l + 1]; };
    auto get2 = [&](int l, int r) { return h2[r] - h2[l - 1] * p2[r - l + 1]; };
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        mp[get1(i, i + n - 1)]++;
    }
    ll ans = 0;
    for (int i = 1; i + n - 1 <= m; i++) {
        if (mp.count(get2(i, i + n - 1))) ans++;
    }
    cout << ans << '\n';
}

赛时队友写了KMP的做法,相较于哈希繁杂很多,但也可以通过

 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
void Solve() {
    ll ans = 0;
    cin >> pat >> txt;
    //make next
    nxt[0] = -1;
    for(ll i = 1, j = -1; i < pat.size(); i ++ ) {
        while(j != -1 && pat[i] != pat[j + 1]) j = nxt[j];
        if(pat[i] == pat[j + 1]) j ++ ;
        nxt[i] = j;
    } 
    vector<ll> pos(txt.size() * 2, 0); // pos为pat最后一位
    //kmp    
    for(ll i = 0, j = -1; i < txt.size(); i ++ ) {
        while(j != -1 && txt[i] != pat[j + 1]) j = nxt[j];
        if(txt[i] == pat[j + 1]) j ++ ;
        if(j == pat.size() - 1) {
            // pos[i] = 1;
            if(pos[i] != 1) {
                ans ++ ;
                pos[i] = 1;
            }
            for(ll k = i + 1; k < txt.size() && k < i + pat.size(); k ++ ) {  // 向后匹配
                if(txt[k] == pat[k - i - 1]) {
                    ans ++ ; 
                    pos[k] = 1;
                }
                else break;
            }
            for(ll k = i - j - 1, poss = pat.size() - 1; k >= 0 && pos[k + pat.size() - 1] != 1; k --, poss -= 1) { // 向前匹配
                if(poss == -1) poss = pat.size() - 1;
                if(txt[k] == pat[poss]) ans ++ ;
                else break;
            }
        } else {
            if(i < txt.size() - 1 && txt[i + 1] != pat[j + 1] && j != -1 || i == txt.size() - 1) {
                bool ff = 0;
                ll cnt = 0;
                for(ll k = i - j - 1, poss = pat.size() - 1; k >= 0 && pos[k + pat.size() - 1] != 1; k -- , poss -= 1) {
                    if(poss == -1) poss = pat.size() - 1;
                    if(txt[k] != pat[poss]) break;
                    cnt ++ ;
                    if(cnt + j == pat.size() - 1) {
                        ans ++ ; ff = 1;
                        pos[k + pat.size() - 1] = 1;
                    }
                    else if(ff) {
                        ans ++ ;
                        pos[k + pat.size() - 1] = 1;
                    }
                }
            }
        }
    } 
    cout << ans << "\n";
}
Licensed under CC BY-NC-SA 4.0
最后更新于 Jul 19, 2024 00:00 UTC
本博客已稳定运行
使用 Hugo 构建
主题 StackJimmy 设计