2019DX#3

心已赠人 2021-11-10 03:04 272阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td>Solved</td> 
   <td>Pro.ID</td> 
   <td>Title</td> 
   <td>Ratio(Accepted / Submitted)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1001</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&amp;cid=850" rel="nofollow">Azshara's deep sea　</a>　　　　　　　凸包</td> 
   <td>6.67%(6/90)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;?</td> 
   <td>1002</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&amp;cid=850" rel="nofollow">Blow up the city</a>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 反向边，支配树思想，u有多个父节点，直接连向他们的lca</td> 
   <td>31.19%(126/404)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1003</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&amp;cid=850" rel="nofollow">Yukikaze and Demons</a>　　　　　　　　分治</td> 
   <td>16.67%(4/24)</td> 
  </tr> 
  <tr> 
   <td>?</td> 
   <td>1004</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&amp;cid=850" rel="nofollow">Distribution of books　　</a>　　　　　二分+dp检查+数据结构优化</td> 
   <td>19.29%(93/482)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1005</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1005&amp;cid=850" rel="nofollow">Easy Math Problem　</a>　　　　　　　　Min25筛，杜教筛</td> 
   <td>9.30%(4/43)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;<img src="http://acm.hdu.edu.cn/images/ac.gif" alt="" width="16" height="16"></td> 
   <td>1006</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&amp;cid=850" rel="nofollow">Fansblog</a></td> 
   <td>21.17%(671/3170)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;<img src="http://acm.hdu.edu.cn/images/ac.gif" alt="" width="16" height="16"></td> 
   <td>1007</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1007&amp;cid=850" rel="nofollow">Find the answer</a></td> 
   <td>11.24%(508/4521)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1008</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&amp;cid=850" rel="nofollow">Game</a>　　　　　　　　　　　　　　三维莫队</td> 
   <td>16.08%(23/143)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;?</td> 
   <td>1009</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&amp;cid=850" rel="nofollow">K Subsequence</a>　　　　　　　　优秀建图或者DJI版费用流，卡spfa</td> 
   <td>5.81%(87/1497)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>1010</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&amp;cid=850" rel="nofollow">Sindar's Art Exhibition</a>　　　　　　树链剖分</td> 
   <td>24.66%(18/73)</td> 
  </tr> 
  <tr> 
   <td>?&nbsp;</td> 
   <td>1011</td> 
   <td align="left"><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1011&amp;cid=850" rel="nofollow">Squrirrel　　</a>　　　　　　　　　　换根树形DP，注意细节</td> 
   <td>13.86%(46/332)</td> 
  </tr> 
 </tbody> 
</table>

# 1002 Blow up the city #

支配树的思想，u有多个父节点，直接连向他们的lca

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# 1004 Distribution of books #

二分答案x

dp\[\]表示前i个在满足每段sum<=x的情况下最多分成几段。

转移dp\[i\] = max(dp\[j\] + 1), 要求sum\[i\] - sum\[j\] <= x

我是用线段树优化的

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# 1009 K Subsequence #

卡了spfa，其他没了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <algorithm>
    #include  <iterator>
    #include  <iostream>
    #include   <cstring>
    #include   <cstdlib>
    #include   <iomanip>
    #include    <bitset>
    #include    <cctype>
    #include    <cstdio>
    #include    <string>
    #include    <vector>
    #include     <stack>
    #include     <cmath>
    #include     <queue>
    #include      <list>
    #include       <map>
    #include       <set>
    #include   <cassert>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    const int mod = 998244353;
    typedef long long ll;
    typedef pair<int,int>pii;
    #define pb push_back
    #define fi first
    #define se second
    /**********showtime************/
                    const int N = 4000 + 10;
                    const int INF = 0x3f3f3f3f;
    
                    struct edge {
                        int to, cap, cost, rev;
                        edge(int t, int c, int co,int re){
                            to = t;cap = c; cost = co; rev = re;
                        }
                    };
                    int V;
                    vector<edge>g[N];
                    int h[N], dis[N], prevv[N], preve[N];
                    void addedge(int u, int v, int cap, int cost) {
                        g[u].pb(edge(v, cap, cost, g[v].size()));
                        g[v].pb(edge(u, 0, -cost, g[u].size()-1));
                    }
    
                    int solve(int s, int t, int f) {
                        int res = 0;
                        memset(h, 0, sizeof(h));
                        while(f > 0) {
                            priority_queue<pii, vector<pii>, greater<pii> > q;
                            memset(dis, inf, sizeof(dis));
                            dis[s] = 0;
                            q.push(pii(0, s));
                            while(!q.empty()) {
                                pii p = q.top();
                                q.pop();
                                int v = p.se;
                                if(dis[v] < p.fi) continue;
                                for (int i = 0; i < g[v].size(); ++i) {
                                    edge &e = g[v][i];
                                    if(e.cap > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to]) {
                                        dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];
                                        prevv[e.to] = v;
                                        preve[e.to] = i;
                                        q.push(pii(dis[e.to], e.to));
                                    }
                                }
                            }
                            if(dis[t] == INF) return -1;
                            for (int v = 0; v < V; ++v) h[v] += dis[v];
                            int d = f;
                            for (int v = t; v != s; v = prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap);
                            f -= d;
                            res += d*h[t];
                            for (int v = t; v != s; v = prevv[v]) {
                                edge &e = g[prevv[v]][preve[v]];
                                e.cap -= d;
                                g[v][e.rev].cap += d;
                            }
                        }
                        return res;
                    }
                    const int maxn = 2e3+9;
                    int a[maxn];
    int main(){
                int T;  scanf("%d", &T);
                while(T--) {
                    int n,k;
                    scanf("%d%d", &n, &k);
    
                    int s = 0, t = 2 * n + 1, ss = t+1;
                    V = ss+1;
                    
                    for(int i=0; i<V; i++) g[i].clear();
                    for(int i=1; i<=n; i++) {
                        scanf("%d", &a[i]);
                        addedge(i, i+n, 1, -1*a[i]);
                    }
                    for(int i=1; i<=n; i++) {
                        addedge(s, i, 1, 0);
                        addedge(i + n, t, 1, 0);
                        for(int j=i+1; j<=n; j++) {
                            if(a[i] <= a[j] ) {
                                addedge(i+n, j, inf, 0);
                            }
                        }
                    }
                    addedge(ss, s, k, 0);
                    printf("%d\n", -1*solve(ss, t, k));
                }
                return 0;
    }

# 1011 Squrirrel #

换根的树形dp

由于有一条边可以删除，所以我们要把儿子分成三种（最长的儿子，次长的儿子，普通儿子），记录最长的儿子，次长的儿子，并预处理出换根时不同类型儿子要的数据，就是同一个父节点下最优的最长路长度。

这个题有一点要清楚，就是对于同一个父节点，只有把最长路儿子的一个路径消成0，才能减少这个父节点的答案。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <algorithm>
    #include  <iterator>
    #include  <iostream>
    #include   <cstring>
    #include   <cstdlib>
    #include   <iomanip>
    #include    <bitset>
    #include    <cctype>
    #include    <cstdio>
    #include    <string>
    #include    <vector>
    #include     <stack>
    #include     <cmath>
    #include     <queue>
    #include      <list>
    #include       <map>
    #include       <set>
    #include   <cassert>
    // #include<bits/extc++.h>
    // using namespace __gnu_pbds;
    using namespace std;
    #define pb push_back
    #define fi first
    #define se second
    #define debug(x) cerr<<#x << " := " << x << endl;
    #define bug cerr<<"-----------------------"<<endl;
    #define FOR(a, b, c) for(int a = b; a <= c; ++ a)
    
    typedef long long ll;
    typedef long double ld;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    
    const int inf = 0x3f3f3f3f;
    const ll inff = 0x3f3f3f3f3f3f3f3f;
    const int mod = 998244353;
    /**********showtime************/
    
                const int maxn = 2e5+9;
                vector<pii>mp[maxn];
                int f[maxn][2], s[maxn][3];
                int son[maxn][2];
                void dfs1(int u, int fa) {
                    f[u][0] =0; f[u][1] = 0;
                    s[u][0] =0; s[u][1] = 0;
                    s[u][2] = 0;
                    int x = 0, y = 0;
                    for(pii p : mp[u]) {
                        int v = p.fi;
                        if(v == fa) continue;
                        dfs1(v, u);
                        if(s[u][0] <= f[v][0] + p.se) {
                            y = v;
                            s[u][0] = f[v][0] + p.se;
                            if(s[u][0] > f[u][0]) swap(s[u][0], f[u][0]), swap(x, y);
                        }
                    }
                    son[u][0] = x;  //最长儿子
                    son[u][1] = y;  //次长儿子
    
                    if(y){          //最长儿子用
                        int m = 0;
                        for(pii p : mp[u]) {
                            int v = p.fi;
                            if(v == fa) continue;
                            if(v == x)  continue;
                            if(v != y){
                                 m = max(m, f[v][0] + p.se);
                            }
                            else {
                                 m = max(m,  min(f[v][1] + p.se, f[v][0]));
                            }
                        }
                        s[u][2] = m;
                    }
    
                    if(x) {         //普通儿子用
                        int m = 0;  
                        for(pii p : mp[u]) {
                            int v = p.fi;
                            if(v == fa) continue;
                            if(v != x){
                                 m = max(m, f[v][0] + p.se);
                            }
                            else {
                                 m = max(m,  min(f[v][1] + p.se, f[v][0]));
                            }
                        }
                        f[u][1] = m;
                    }
    
                    if(y) {         //次长儿子用
                        int m = 0;
                        for(pii p : mp[u]) {
                            int v = p.fi;
                            if(v == fa) continue;
                            if(v == y) continue;
                            if(v != x){
                                 m = max(m, f[v][0] + p.se);
                            }
                            else m = max(m,  min(f[v][1] + p.se, f[v][0]));
                        }
                        s[u][1] = m;
                    }
                }
                int mx, ans;
    
                void dfs2(int u, int fa, int mx0, int mx1) { 
    
                    int x = max(mx0, f[u][1]);
                    
                    x = min(x, max(mx1, f[u][0]));
    
    
                    if(mx > x) mx = x, ans = u;
                    else if(mx == x) ans = min(ans, u);
    
                    for(pii p : mp[u]) {
                        int v = p.fi;
                        if(v == fa) continue;
                        
                        int tmpmx0 = mx0;
                        int tmpmx1 = mx1;
    
                        if(son[u][0] == v) {
                            tmpmx0 = max(mx0, s[u][0]);
                        }
                        else tmpmx0 = max(mx0, f[u][0]);
    
                        if(son[u][0] == v){
                            tmpmx1 = min(max(mx0, s[u][2]), max(mx1, s[u][0]));//x去掉和去掉次大一条边
                            //注意这里或的关系，只能有一个裁剪
                        }
                        else {
                            if(son[u][1] != v)
                            {
                                tmpmx1 = min(max(mx1, f[u][0]),max(mx0, f[u][1]));
                            }
                            else {
                                tmpmx1 = min(max(mx0, s[u][1]) , max(mx1, f[u][0]));
                            }
                        }
    
                        tmpmx1 = min(tmpmx0, tmpmx1 + p.se);
                        tmpmx0 += p.se;
                        dfs2(v, u, tmpmx0, tmpmx1);
                    }
                }
    int main(){
                int T;  scanf("%d", &T);
                while(T--) {
                    int n;      
                    scanf("%d", &n);
                    for(int i=1; i<=n; i++) mp[i].clear();
                    for(int i=1; i<n; i++) {
                        int u,v,w;
                        scanf("%d%d%d", &u, &v, &w);
                        mp[u].pb(pii(v, w));
                        mp[v].pb(pii(u, w));
                    }
                    dfs1(1, 1);
                    mx = inf, ans = inf;
                    dfs2(1, 1, 0, 0);
                    printf("%d %d\n", ans, mx);
                }
                return 0;
    }
    
    /*
    1
    10
    2 1 139
    3 1 72
    4 2 141
    5 2 133
    6 5 121
    7 5 49
    8 7 182
    9 5 174
    10 9 171
    
    
    output：5 344
    */

转载于:https://www.cnblogs.com/ckxkexing/p/11265628.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/61ee8578da7f48058730972684718731.png