Chgtaxihe's blog

训练补题-牛客训练赛8

# 牛客训练赛8补题记录

# I: Interesting Computer Game

比赛的时候我用网络流AC了，看了题解发现完全不需要这么做。

考虑ai,bia_i,b_i之间建边，那么一个大小为nn连通块内如果只有n−1n-1条边，则只能选择n−1n-1个点，否则有环，可以选择nn个点

AC代码：

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define int128 _int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r == 0 ? ' ' : '\n')
#define pii pair<int, int>
#define sqr(x) ((x) * (x))
using namespace std;

const int maxn = 1e5 + 1000;

pii a[maxn];
int unq[maxn * 2], unq_size, n;
int fa[maxn * 2], edge_cnt[maxn * 2], sz[maxn * 2];

int get_fa(int x){return x==fa[x]?x:fa[x]=get_fa(fa[x]);}

void solve(){
    unq_size = 0;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i].first >> a[i].second;
        unq[unq_size++] = a[i].first;
        unq[unq_size++] = a[i].second;
    }

    sort(unq, unq + unq_size);
    unq_size = unique(unq, unq + unq_size) - unq;

    for(int i=0; i<=unq_size; i++) {
        fa[i] = i;
        edge_cnt[i] = 0;
        sz[i] = 1;
    }

    for(int i=0; i<n; i++){
        int x = get_fa(lower_bound(unq, unq + unq_size, a[i].first) - unq); 
        int y = get_fa(lower_bound(unq, unq + unq_size, a[i].second) - unq); 
        if(x == y){
            edge_cnt[x]++;
        }else{
            sz[x] += sz[y];
            edge_cnt[x] += edge_cnt[y] + 1;
            fa[y] = x;
            sz[y] = edge_cnt[y] = 0;
        }
    }

    int ans = 0;
    for(int i=0; i<unq_size; i++) {
        ans += min(edge_cnt[i], sz[i]);
    }
    cout << ans << '\n'; 
}

signed main() {
    Android;
    int t; cin >> t;
    for(int i=1; i<=t; i++){
        cout << "Case #" << i << ": ";
        solve();
    }
}
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

# K: Kabaleo Lite

std::ostream & operator << (std::ostream& os, __int128_t val) {
    if(val < 0) os << '-', val = -val;
    if(val >= 10) os << val / 10;
    return os << ((int)(val % 10));
}
1
2
3
4
5

# G: Game SET

题目说There are no identical cards.

暴力即可????

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<int, int>
#define sqr(x) ((x)*(x))
using namespace std;

const int maxn = 256 + 10;
const regex pattern("\\[(.+?)\\]\\[(.+?)\\]\\[(.+?)\\]\\[(.+?)\\]");

unordered_map<string, int> id = {
    {"*", -16},
    {"one", 1}, {"two", 2}, {"three", 3},
    {"diamond", 1}, {"squiggle", 2}, {"oval", 3},
    {"solid", 1}, {"striped", 2}, {"open", 3},
    {"red", 1}, {"green", 2}, {"purple", 3}
};

int feat[maxn][4];

void scan(int x, string & buf){
    smatch result;
    assert(regex_match(buf, result, pattern));
    for(int i=0; i<4; i++){
        feat[x][i] = id[result[i + 1]];
    }
}

bool isSet(int i, int j, int k){
    bool succ = true;
    for(int f=0, tmp; f<4; f++){
        tmp = feat[i][f] + feat[j][f] + feat[k][f];
        if(tmp > 0 && tmp != 6 && tmp % 3 != 0) {
            succ = false;
            break;
        }
    }
    return succ;
}

void solve(){
    int n; cin >> n;

    string _buffer;
    for(int i=0; i<n; i++){
        cin >> _buffer;
        scan(i, _buffer);
    }

    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            for(int k=j+1; k<n; k++){
                if(isSet(i, j, k)){
                    cout << (i + 1) << " " << (j + 1) << " " << (k + 1) << '\n';
                    return;
                }
            }
        }
    }
    cout << "-1\n";
}

signed main(){
    Android;
    int t; cin >> t;
    for(int i=1; i<=t; i++){
        cout << "Case #" << i << ": ";
        solve();
    }
}
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

# E: Enigmatic Partition

# 做法1: 搜索+背包dp

参考：

  • https://blog.csdn.net/tomjobs/article/details/107776412

序列由三个数字{l,l+1,l+2}\{l,l+1,l+2\}组成，令mid=l+1,r=l+2mid=l+1,r=l+2，主要思路为枚举ll

  • 当l<50l<50：（复杂度O(3∗50∗maxn)O(3*50*maxn)）
    • 背包dp即可
    • 注意代码中"巧妙"的部分
  • 当l≥50l\ge 50：（复杂度很迷）
    • 注意到两个midmid可以被拆分成l+rl+r
    • 因此，当ll的数量大于等于rr的数量时，只需要枚举cntl,cntmidcnt_l,cnt_{mid}即可
      • 确定cntlcnt_l之后，令其他数字全为midmid，则当前和共有(cntmid−1)/2(cnt_{mid}-1)/2种拆分
    • 当rr的数量大于ll的数量时，同理只需枚举cntr,cntmidcnt_r,cnt_{mid}

单靠背包dp无法处理l∈[1,105]l\in[1,10^5]的情况，单靠暴力搜索难以处理l∈[1,20]l\in[1,20]的情况

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 1000;

ll ans[maxn];
ll dp[50][maxn];

void solve(){
    for(int l = 50; l < maxn; l++){ // 复杂度???
        int mid = l + 1, r = l + 2;

        // 2 * mid 等价于 l + r
        for(int cnt_l = 0; cnt_l * l < maxn; cnt_l++){ // cnt_l >= cnt_r
            for(int cnt_mid = 3; cnt_mid * mid + cnt_l * l < maxn; cnt_mid++){
                ans[cnt_mid * mid + cnt_l * l] += (cnt_mid - 1) >> 1;
            }
        }

        for(int cnt_r = 1; cnt_r * r < maxn; cnt_r++){ // cnt_l < cnt_r
            for(int cnt_mid = 3; cnt_mid * mid + cnt_r * r < maxn; cnt_mid++){
                ans[cnt_mid * mid + cnt_r * r] += (cnt_mid - 1) >> 1;
            }
        }
    }
    // 背包dp
    for(int l = 1; l < 50; l++){ // O(3 * 50 * maxn)
        int val[3] = {l, l + 1, l + 2};
        dp[l][0] = 1;
        int sum = l + (l + 1) + (l + 2);
        for(int i=0; i<3; i++){
            for(int j=val[i]; j<maxn; j++){
                dp[l][j] += dp[l][j - val[i]];
            }
        }
        for(int i=sum; i<maxn; i++){
            ans[i] += dp[l][i - sum]; // 个人认为很巧妙的地方
            // 去掉一个sum，保证{l, l+1, l+2}每个数至少出现一次
        }
    }

    for(int i=1; i<maxn; i++) ans[i] += ans[i - 1];
}

signed main(){
    Android;
    solve();
    int t; cin >> t;
    for(int i=1, l, r; i<=t; i++){
        cin >> l >> r;
        cout << "Case #" << i << ": " << ans[r] - ans[l - 1] << '\n';
    }
}
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

# 二次差分（二次前缀和）

参考:

  • https://blog.csdn.net/qq_45458915/article/details/107777572
  • https://blog.csdn.net/tianyizhicheng/article/details/107773762

这个做法太考验观察能力了~

事实上，如果把+1，-1分别做差分和，理解起来应该会简单不少

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 1000;

ll ans[maxn * 10];

void solve(){
    for(int len = 3; len < maxn; len++){
        for(int l = 1, mid, r; len * l < maxn; l++){
            mid = l + 1, r = l + 2;
            ans[l * len + 3]++, ans[mid * len + 1]--;
            ans[mid * len + 2]--, ans[len * r - 3 + 1 + 2]++;
        }
    }
    for(int i=2; i<maxn; i++) ans[i] += ans[i-2]; // 第二次差分
    for(int i=1; i<maxn; i++) ans[i] += ans[i-1]; // 第一次差分
    for(int i=1; i<maxn; i++) ans[i] += ans[i-1]; // 前缀和
}

signed main(){
    Android;
    solve();
    int t; cin >> t;
    for(int i=1, l, r; i<=t; i++){
        cin >> l >> r;
        cout << "Case #" << i << ": " << ans[r] - ans[l - 1] << '\n';
    }
}
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

# A: A-All-Star Game

上次更新: 2021/02/24, 03:37:30
训练补题-牛客训练赛7
训练补题-牛客训练赛9

← 训练补题-牛客训练赛9→

最近更新
01
深入理解Java虚拟机
 03-04
02
DNS工作原理
 02-27
03
改用VuePress啦
 02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2021