训练补题-牛客训练赛6

# 牛客训练赛5补题记录

# D: Drop Voicing

跑一个最长上升子序列

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 100;

int val[maxn];
int dp[maxn], n;

int check(int s){
    int ret = 0;
    for(int i=0; i<n; i++){
        dp[i] = 1;
        for(int j=i-1; j>=0; j--){
            if(val[s + j] < val[s + i]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ret = max(ret, dp[i]);
    }
    return ret;
}

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> val[i];
        val[i + n] = val[i];
    }
    
    int lcs = 0;
    for(int i=1; i<=n; i++){
        lcs = max(lcs, check(i));
    }
    cout << n - lcs << '\n';
}
  
signed main(){
    Android;
    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

# B: Graph

显然，只要操作符合题目要求，则 $\forall u,v(u\ne v),path(u,v)=C$ ，其中 $C$ 为某一常数（不因加边/删边而改变）， $path(u,v)$ 代表路径上的边权异或和。

那么，可以给每个点设置一个点权 $w$ ，两个点之间的边权为两点权的异或。

问题转化为最小异或生成树的求解。

AC代码：

#define TARGET_OJ Codeforces
#define AGRESSIVE_OPT 1
#ifdef ONLINE_JUDGE
    #if (TARGET_OJ == Codeforces || TARGET_OJ == HDU)
        #pragma GCC optimize("unroll-loops")
        #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    #endif
    #if (AGRESSIVE_OPT == 1)
        #pragma GCC optimize("Ofast")
    #endif
#endif

#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("./input.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;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 100;

int trie[maxn * 33][2], l[maxn * 33], r[maxn * 33], node_cnt = 1;
int a[maxn], n;
vector<pii> G[maxn];

void build(int rt, int val, int dep, int tag){
    if(l[rt] == 0) l[rt] = tag;
    r[rt] = max(r[rt], tag);

    if(dep > 30) return;
    
    int bit = (val & (1<<(30-dep))) > 0;
    if(trie[rt][bit] == 0) trie[rt][bit] = ++node_cnt;
    build(trie[rt][bit], val, dep + 1, tag);
}

int query(int rt, int val, int dep){
    if(dep > 30) {
        return 0;
    }
    int bit = (val & (1<<(30-dep))) > 0;
    if(trie[rt][bit] == 0){
        return query(trie[rt][bit ^ 1], val, dep + 1) + (1 << (30-dep));
    }
    return query(trie[rt][bit], val, dep + 1);
}

ll dfs(int rt, int dep){
    if(dep > 30) return 0;
    if(trie[rt][0] && trie[rt][1]){
        ll mn = INT_MAX;
        for(int i=l[trie[rt][0]]; i<=r[trie[rt][0]]; i++){
            mn = min(mn, query(trie[rt][1], a[i], dep + 1) + (1ll << (30 - dep)));
        }
        return dfs(trie[rt][0], dep + 1) + dfs(trie[rt][1], dep + 1) + mn;
    }
    if(trie[rt][0]) return dfs(trie[rt][0], dep + 1);
    return dfs(trie[rt][1], dep + 1);
}

void build_a_array(int rt, int fa, int cur){
    a[rt] = cur;
    for(pii ve:G[rt]){
        int dest = ve.first;
        if(dest == fa) continue;
        build_a_array(dest, rt, cur ^ ve.second);
    }
}

void solve(){
    cin >> n;
    
    for(int i=1, u, v, w; i<n; i++){
        cin >> u >> v >> w;
        u++, v++;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    build_a_array(1, 0, 0);

    sort(a + 1, a + 1 + n);
    for(int i=1; i<=n; i++)
        build(1, a[i], 0, i);
    cout << dfs(1, 0) << '\n';
}
  
signed main(){
    Android;
    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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

# A: Portal

首先要注意到，两扇传送门，我们只需要维护其中一扇的状态即可。

可以把任务拆分成到 $a_i$ 再到 $b_i$ 两个子任务。

接着，设 $dp[i][j]$ 代表完成了任务 $i$ ，且传送门在 $j$ 点时最小的代价。

转移方程稍微想想就能得出来了。

#define TARGET_OJ Codeforces
#define AGRESSIVE_OPT 1
#ifdef ONLINE_JUDGE
    #if (TARGET_OJ == Codeforces || TARGET_OJ == HDU)
        #pragma GCC optimize("unroll-loops")
        #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    #endif
    #if (AGRESSIVE_OPT == 1)
        #pragma GCC optimize("Ofast")
    #endif
#endif

#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("./input.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;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 300 + 10;

ll G[maxn][maxn];
int n, m, k, task[maxn * 2];
ll dp[2 * maxn][maxn];

void solve(){
    memset(G, 0x3f, sizeof G);
    memset(dp, 0x3f, sizeof dp);
    cin >> n >> m >> k;
    for(int i=0, u, v, w; i<m; i++){
        cin >> u >> v >> w;
        G[u][v] = G[v][u] = min(G[u][v], w * 1ll);
    }
    for(int i=0; i<=n; i++) G[i][i] = 0;
    for(int i=0; i<k; i++){
        cin >> task[(i<<1) + 1] >> task[(i<<1|1) + 1];
    }
    k = k * 2;
    task[0] = 1;
    dp[0][1] = 0;

    for(int mid=1; mid<=n; mid++){
        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n; j++){
                G[i][j] = G[j][i] = min(G[i][j], G[i][mid] + G[mid][j]);
            }
        }
    }

    for(int mis=1; mis<=k; mis++){
        int former = task[mis - 1];
        int cur = task[mis];
        for(int i=1; i<=n; i++){
            dp[mis][i] = min(inf, dp[mis - 1][i] + G[former][cur]);
            for(int j=1; j<=n; j++){
                dp[mis][i] = min(dp[mis][i], dp[mis - 1][j] + min(inf, G[former][i] + G[i][cur]));
                dp[mis][i] = min(dp[mis][i], dp[mis - 1][j] + min(inf, G[j][i] + G[i][cur]));
                dp[mis][i] = min(dp[mis][i], dp[mis - 1][j] + min(inf, G[former][i] + G[j][cur]));
            }
        }
    }
    ll ans = inf;
    for(int i=1; i<=n; i++) ans = min(ans, dp[k][i]);
    cout << ans << '\n';
}
  
signed main(){
    Android;
    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
76
77
78

# H: Interval

# C: Easy 生成函数

上次更新: 2021/02/24, 03:37:30

← 训练补题-牛客训练赛3 训练补题-牛客训练赛6→