Chonu

2023ICPC合肥

Posted on Edited on In , Valine:

已补E,F,G,J

F - Colorful Balloons

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve(){
     int n;cin>>n;
     int k=n;
     map<string,int>mp;
     int ans=0;
     while(n--){
        string s;cin>>s;
        mp[s]++;
        ans=max(ans,mp[s]);
     }        
     for(auto [s,i]:mp){
        if(i>k/2){
            cout<<s<<"\n";
            return;
        }
     }
     cout<<"uh-oh\n";
}

E - Matrix Distances

考虑对x和y的贡献分开进行计算

相同颜色中，排序后的下为i的x的贡献值为

$\sum_1^i(a[i].first-a[j].first)+\sum_i^{end}(a[j].first-a[i].first)$

对该式子化简后可得

$a[i].first*(i-1)-\sum_1^ia[j].first+\sum_i^{end}a[j].first-(end-i)*a[i].first$

y的贡献同理

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
void solve() {
    int n,m;cin>>n>>m;
    vector<vector<int>>g(n+1,vector<int>(m+1));
    map<int,vector<pair<int,int>>>mp;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
            mp[g[i][j]].push_back({i,j});
        }
    }
    int ans=0;
    auto work=[&](){
        for(auto &[x,y]:mp){
            sort(y.begin(),y.end(),[&](auto l,auto r){
                return l.first<r.first;
            });
            vector<int>pre(y.size()+10,0);
            for(int i=0;i<y.size();i++){
                pre[i+1]=pre[i]+y[i].first;
            }
            for(int i=1;i<=y.size();i++){
                int l=i-1,r=y.size()-i;
                ans+=l*y[i-1].first-pre[i-1]+pre[y.size()]-pre[i]-r*y[i-1].first;
            }
        }
    };
    work();
    for(auto &[x,y]:mp){
        for(auto &[x1,y1]:y){
            swap(x1,y1);
        }
    }
    work();
    cout<<ans<<"\n";
}

J - Takeout Delivering

开始的想法很朴素，正反跑两边dijkstra，求出每个点到点1和点n的最长距离

然后遍历所有点i，使得两条最长边分别确定在1-i与i-n之间，求出两边之和的最小值

这样有一个显然的错误就是可能会存在两条最长边在一边的情况，最终使得求出的答案小于正确答案

为了解决这种情况，我们将点的遍历改为边的遍历，确定该边为这条路径上的最长边，这样次长边一定是在该边的两端的两个顶点分别到点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
56
57
58
void solve() {
    int n, m;cin >> n >> m;
    vector<vector<pair<int, int>>>g(n + 1);
    vector<array<int, 3>>edge;
    for (int i = 1;i <= m;i++) {
        int u, v, w;cin >> u >> v >> w;
        g[u].push_back({ v,w });
        g[v].push_back({ u,w });
        edge.push_back({ u,v,w });
    }
    vector<int>dis1(n + 10, 1e18), dis2(n + 10, 1e18);
    vector<int>st1(n + 10, 0), st2(n + 10, 0);
    auto dig1 = [&](int fi, int se) {
        priority_queue<PII, vector<PII>, greater<>>heap;
        heap.push({ 0, fi });
        dis1[fi] = 0;
        while (heap.size()) {
            auto [d, u] = heap.top();heap.pop();
            if (st1[u]) continue;
            st1[u] = 1;
            for (auto [i, w] : g[u]) {
                if (max(w, dis1[u]) < dis1[i]) {
                    dis1[i] = max(w, dis1[u]);
                    heap.push({ dis1[i],i });
                }
            }
        }
        };
    auto dig2 = [&](int fi, int se) {
        priority_queue<PII, vector<PII>, greater<>>heap;
        heap.push({ 0, fi });
        dis2[fi] = 0;
        while (heap.size()) {
            auto [d, u] = heap.top();heap.pop();
            if (st2[u]) continue;
            st2[u] = 1;
            for (auto [i, w] : g[u]) {
                if (max(w, dis2[u]) < dis2[i]) {
                    dis2[i] = max(w, dis2[u]);
                    heap.push({ dis2[i],i });
                }
            }
        }
        };
    dig1(1, n);
    dig2(n, 1);
    int ans = 1e18;
    for (auto i : edge) {
        auto [u, v, w] = i;
        if (w >= dis1[u] && w >= dis2[v]) {
            ans = min(ans, max(dis1[u], dis2[v]) + w);
        }
        if (w >= dis2[u] && w >= dis1[v]) {
            ans = min(ans, max(dis2[u], dis1[v]) + w);
        }
    }
    cout << ans << "\n";
}

G - Streak Manipulation

看到多项，每项都有选/不选求最优解的问题，可以想到dp

为求第k长的1串长度，可以想到二分，每次在二分里状态转移

观察到k数字很小

$dp[i][j][k]$表示前i个字符中有j个1串长度大于等于二分值mid的最小代价，k表示第i个字符是0还是1

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
void solve(){
     int n,m,k;cin>>n>>m>>k;
     string s;cin>>s;
     s=" "+s;
     vector<int>pre(n+1,0);
     for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+(s[i]=='0');
     }
     vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(k+1,vector<int>(2,1e9)));
     auto check=[&](int x){
          for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                dp[i][j][0]=1e9;
                dp[i][j][1]=1e9;
            }
          }
         dp[0][0][0]=0;
         for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
               if(s[i]=='0') {
                  dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]);
                  //将该位置0,只能是当前位置是0,此时不用付代价
               }                
               dp[i][j][1]=min(dp[i-1][j][0],dp[i-1][j][1])+(s[i]=='0');
               if(i>=x&&j>=1){ 
                   dp[i][j][1]=min(dp[i-x][j-1][0]+pre[i]-pre[i-x],dp[i][j][1]);
               }
            }
         }
          return min(dp[n][k][1],dp[n][k][0])<=m;
     };
     int l=-1,r=n+1;
     while(l+1!=r){
        int mid=l+r>>1;
        if(check(mid)) l=mid;
        else r=mid;
     }        
     if(l!=0) cout<<l<<"\n";
     else cout<<l-1<<"\n";
}

Welcome to my other publishing channels