codeforce#933 题解

作者：繁依Fanyi0 | 2024-04-28 16:22:40

踩

codeforce#933 题解

E. Rudolf and k Bridges

题意不讲了，不如去题干看图。
传统dp，每个点有两个选择，那么建桥要么不建。需要注意的是在状态转移的时候，桥是有长度的，如果不建需要前d格中建桥花费最少的位置作为状态转移的初态。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <unordered_set>
#include <map>
#include <queue>
 
#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)
 
using namespace std;
 
typedef long long ll;

const int maxn = 2e5+5;

struct contianer {
    private:
        int step;
        int pos = 0;
        ll loop[maxn];
        multiset<ll> store;

    public:
        contianer(int step):step(step) {}
        
        void add(ll x) {
            int now = pos % step;
            // need to remove
            if (pos >= step) {
                store.erase(store.find(loop[now]));
            }
            
            loop[now] = x;
            store.insert(x);
            pos ++;
        }
        
        /**
          * get min number
         */
        ll get() {
            return *store.begin();
        }
        
        void setStep(int s);
        
        void clear();
};

void contianer::setStep(int s) {
    step = s;
}

void contianer::clear() {
    store.clear();
    pos = 0;
}

ll sum[128];
int store[maxn];
ll dp[maxn][2];
int main() {
    IOS
    
    int t;
    cin>>t;
    while(t--) {
        int n,m,k,d;
        cin>>n>>m>>k>>d;
        contianer heap(d);
        
        sum[0] = 0LL;
        // input and dp
        rep(_,0,n) {
            // input
            rep(i,0,m) cin>>store[i];
            // init
            heap.clear();
            heap.add(store[0] + 1);
            dp[0][0] = dp[0][1] = store[0] + 1;
            // dp
            rep(i,1,m-1) {
                ll min_cost = heap.get();
                dp[i][0] = min_cost;
                dp[i][1] = min(dp[i-1][0], min_cost) + store[i] + 1;
//                cout<<"dp["<<i<<"][0]:"<<dp[i][0]<<" dp["<<i<<"][1]:"<<dp[i][1]<<endl;
                
                heap.add(dp[i][1]);
            }
            // cost
            sum[_ + 1] = min(dp[m-2][1], dp[m-2][0]) + 1LL;
//            cout<<sum[_+1]<<endl;
        }
        // pre sum
        rep(i,1,n+1) sum[i] += sum[i-1];
        // the k min
        ll ans = sum[k] - sum[0];
        rep(i,k+1,n+1) {
            ans = min(ans, sum[i] - sum[i-k]);
        }
        // cout
        cout<<ans<<endl;
    }
    
    return 0;
}
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112

F. Rudolf and Imbalance

求两数和的plus版本。给出数组a，现在要分别从d和f挑选一个数相加后放入a，使得所有 $a_{i+1} - a_i$ 中最大值尽可能小。
显然，我们只要找到在没有挑选插入前 $a_{i+1} - a_i$ 的最大值以及 $i$ 的值，然后构造 $a_{i+1} > d+f > a_i$ ，就可以破坏最大值。且 $\frac {a_{i+1} + a_i}{2}$ 时，能将最大值分割的尽可能小。
其中，如果最大值和第二大值一样，那么无论怎么分割都改变不了最大值，可以直接输出。
至于怎么让 $d + f$ 尽可能靠近中点就不细说了，固定d然后二分搜索f。~~这里我脑干缺失写了个int target = abs(aim - commonA);我是真的睿智~~

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;

const int maxn = 2e5+5;

struct record{
    int val;
    int ind;
};

int store[maxn/2];
record dif[maxn/2];
int d[maxn], f[maxn];
bool cmp(const record& a, const record& b) {
    return a.val < b.val;
}
int abs(int a) {
    if (a<0) return -a;
    else return a;
}
int main() {
    IOS
    
    int t;
    cin>>t;
    while(t--) {
        int n,m,k;
        cin>>n>>m>>k;
        
        int pos = 0;
        cin>>store[0];
        rep(i,1,n) {
            cin>>store[i];
            dif[pos].ind = i;
            dif[pos ++].val = store[i] - store[i-1];
        }
        sort(dif, dif+pos,cmp);
//        rep(i,0,pos) cout<<dif[i].val<<endl;
        
        int len_d , len_f;
        if (m < k) {
            rep(i,0,m) cin>>d[i];
            sort(d, d+m);
            len_d = m;
            rep(i,0,k) cin>>f[i];
            sort(f, f+k);
            len_f = k;
        } else {
            rep(i,0,m) cin>>f[i];
            sort(f,f+m);
            len_f = m;
            rep(i,0,k) cin>>d[i];
            sort(d,d+k);
            len_d = k;
        }
        
        if (pos > 2 && dif[pos-1].val == dif[pos-2].val) {
            cout<<dif[pos-1].val<<endl;
            continue;
        }
        
        int sup = store[dif[pos-1].ind];
        int inf = store[dif[pos-1].ind - 1];
        int aim = inf + (sup - inf)/2;
        int minn = dif[pos-1].val;
        rep(i,0,len_d) {
            int commonA = d[i];
            if (commonA >= sup) break;
            
            int target = aim - commonA;
//            cout<<"d[i]:"<<d[i]<<" target:"<<target<<endl;
            auto it = upper_bound(f, f+len_f-1, target);
//            cout<<"it:"<<it<<endl;
            
            int commonB = *it;
//            cout<<"find:"<<commonB<<endl;
            int num = commonA + commonB;
            if (inf<num && num<sup)
                minn = min(minn, max(sup - num ,num - inf));
            
            if (it != f) {
                commonB = *(it-1);
                num = commonA + commonB;
                if (inf<num && num<sup)
                    minn = min(minn, max(sup - num ,num - inf));
            }
        }
        /*
        if (d[0] + f[0] < store[0]) {
            aim = store[0];
            rep(i,0,len_d) {
                int commonA = d[i];
                if (commonA >= aim) break;
                
                int target = abs(aim - commonA);
                auto it = lower_bound(f, f+len_f-1, target-1);
                
                int commonB = *it;
                cout<<"commonA:"<<commonA<<" commonB:"<<commonB<<" target:"<<target<<endl;
                int num = commonA + commonB;
                if (num < store[0])
                    minn = min(minn, store[0] - num);
                
                if (it != f) {
                    commonB = *(it-1);
                    num = commonA + commonB;
                    if (num < store[0])
                        minn = min(minn, store[0] - num);
                }
            }
        }
        
        aim = store[n-1];
        if (d[len_d-1] + f[len_f-1] > aim)
            rep(i,0,len_d) {
                int commonA = d[i];
                
                int target = abs(aim - commonA);
                auto it = upper_bound(f, f+len_f-1, target+1);
                
                int commonB = *it;
                int num = commonA + commonB;
                if (num > aim) {
                    minn = min(minn, num - aim);
                }
                if(it == f) break;
            }
        */
        cout<<max(minn, pos>=2? dif[pos-2].val : 0)<<endl;
    }
    
    return 0;
}
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

G. Rudolf and Subway

~~很好的图论使我小脑萎缩~~
边染色，求A->B最少经过几种颜色。其中相同颜色的边一定构成连通图。
~~机智如我~~并没有按照题解中加边的思路，而是采用合并点的方式，从颜色的维度处理。将相同颜色的边视为从同一个点出发(因为相同颜色内移动不会影响结果，只有移动到新的颜色上才会影响结果)，从而将问题转化为最短路。采用bfs那么首先经过的颜色一定是最短路，从而可以作为优化的条件。
此外由于是边染色，所有可能一个点会被多个颜色所合并。如果在颜色A的合并点里走到了点v，同时v又连接B、C等颜色的边，虽然后续B、C颜色的合并也会重新遍历v的边，但是由于bfs的特性此时的遍历不会影响已经过的颜色A，也不会加入新的颜色(因为v涉及的所有颜色都在颜色A的合并点中加入到了队列)，所以图中的每个点只需要访问一次，不需要重复访问。
~~没有这个优化会T 嘤嘤嘤~~

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <time.h>
#include <set>
#include <map>
#include <queue>

#define IOS     ios::sync_with_stdio(0);cin.tie(0);
#define mem(A,B) memset(A,B,sizeof(A));
#define rep(index,start,end) for(int index = start;index < end; index ++)
#define drep(index,start,end) for(int index = start;index >= end; index --)

using namespace std;

typedef long long ll;

const int maxn = 2e5+5;

struct node{
    int to;
    int color;
};

queue<int> Q;
bool vis[maxn],visNode[maxn];
int dis[maxn];
set<int> colors;
set<int> colorSet[maxn];
vector<node> adj[maxn];
int main() {
    IOS
    cout.tie(0);
    
    int t;
    cin>>t;
    while(t--) {
        for(auto it=colors.begin();it!=colors.end();it++){
            vis[*it] = false;
            colorSet[*it].clear();
        }
        colors.clear();
        
        int n,m;
        cin>>n>>m;
        rep(i,0,n+1) {
            adj[i].clear();
            visNode[i] = false;
        }
        
        rep(i,0,m) {
            int commonA,commonB,color;
            cin>>commonA>>commonB>>color;
            adj[commonA].push_back({commonB, color});
            adj[commonB].push_back({commonA, color});
            
            colorSet[color].insert(commonA);
            colorSet[color].insert(commonB);
            
            colors.insert(color);
        }
        int commonA,commonB;
        cin>>commonA>>commonB;
        if (commonA==commonB) {
            cout<<0<<endl;
            continue;
        }
        
        for(auto it=colors.begin();it!=colors.end();it++)
            dis[*it] = INT_MAX;
        
        visNode[commonA] = true;
        rep(i,0,adj[commonA].size()) {
            node edge = adj[commonA][i];
            if (!vis[edge.color]) {
                Q.push(edge.color);
//                cout<<"push color:"<<edge.color<<endl;
                dis[edge.color] = 1;
                vis[edge.color] = true;
            }
        }
        while(!Q.empty()) {
            int now = Q.front();
//            cout<<"color:"<<now<<" dis:"<<dis[now]<<endl;
            Q.pop();
            
            for(int v : colorSet[now]) {
                if (visNode[v]) continue;
                visNode[v] = true;
                int len = adj[v].size();
                
                rep(i,0,len) {
                    node next = adj[v][i];
                    int next_color = next.color;
                    if (vis[next_color] || visNode[next.to]) continue;
                    
                    dis[next_color] = dis[now]+1;
                    Q.push(next_color);
                    vis[next_color] = true;
                }
            }
        }
        
        int ans = INT_MAX;
        rep(i,0,adj[commonB].size()) {
            node edge =adj[commonB][i];
            int des_color = edge.color;
            ans = min(ans, dis[des_color]);
        }
        
        cout<<ans<<endl;
        
        
    }
    
    return 0;
}
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

官方题解则是通过加边的方法传送门
请添加图片描述将染色边转化为一个新的染色节点连接到原有边的端点。可能这样画体现不出这个方法精妙之处。点多了就能看出来，这样形成一个星形的连接，相同颜色的点之间移动都只需要经过两条边。仍然还是bfs，只不过由于边多加了，所以需要最终结果/2

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/503203