2018ICPC-Ningxia

Posted on | Edited on | In | Views:

E. 2-3-4 Tree

题意

裸的 $B+$ 树

题解

代码

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
const int k=4;
struct Node{
    int cnt;
    bool isLeaf;
    int a[3];
    Node *child[k];
    Node(){
        isLeaf=1;
        cnt=0;
        mem0(child);
    }
    void out(){
        assert(cnt);
        out0(a,cnt);
    }
}*root;
void del(Node*rt){
    if(rt->isLeaf)delete rt;
    else{
        for(int i=0;i<=rt->cnt;i++)del(rt->child[i]);
        delete rt;
    }
}
pair<Node*,int> split(Node *rt){
    rt->cnt=1;
    Node *tmp=new Node;
    tmp->cnt=1;
    tmp->a[0]=rt->a[2];
    tmp->isLeaf=rt->isLeaf;
    tmp->child[0]=rt->child[2];
    tmp->child[1]=rt->child[3];
    pair<Node*,int> tmm=pair<Node*,int>(tmp,rt->a[1]);
    if(rt==root){
        Node *p=new Node;
        p->cnt=1;
        p->a[0]=tmm.se;
        p->isLeaf=0;
        p->child[0]=rt;
        p->child[1]=tmp;
        root=p;
    }
    return tmm;
}
void add(Node *rt,int x){
    rt->a[rt->cnt++]=x;
    sort(rt->a,rt->a+rt->cnt);
}
pair<Node*,int> insert(Node *rt,int x){
    int id;
    for(id=0;id<rt->cnt;id++){
        if(x<rt->a[id]){
            break;
        }
    }
    if(rt->cnt==k-1){
        pair<Node*,int> ret = split(rt);
        if(rt->isLeaf){
            if(id<2)add(rt,x);
            else add(ret.fi,x);
            return ret;
        }else{
            if(id>1)rt=ret.fi;
            pair<Node*,int>tmp= insert(rt,x);
            if(tmp.se){
                if(id%2){
                    rt->cnt++;
                    rt->child[2]=tmp.fi;
                    rt->a[1]=tmp.se;
                }else {
                    rt->cnt++;
                    rt->a[1]=rt->a[0];
                    rt->a[0]=tmp.se;
                    rt->child[2]=rt->child[1];
                    rt->child[1]=tmp.fi;
                }
            }
            return ret;
        }
    }else{
        if(rt->isLeaf){
            add(rt,x);
        }else{
            pair<Node*,int>tmp= insert(rt->child[id],x);
            if(tmp.se){
                for(int i=rt->cnt;i>=id+1;i--){
                    rt->a[i]=rt->a[i-1];
                    rt->child[i+1]=rt->child[i];
                }
                rt->cnt++;
                rt->a[id]=tmp.se;
                rt->child[id+1]=tmp.fi;
            }
        }
        return pair<Node*,int>(0,0);
    }
}
void dfs(Node *rt){
    rt->out();
    if(!rt->isLeaf){
        for0(i,rt->cnt+1)dfs(rt->child[i]);
    }
}
int main() {
    int t,n,x;
    in(t);
    for1(ca,t){
        root=new Node;
        in(n);
        for0(i,n){
            in(x);
            insert(root,x);
        }
        printf("Case #%d:\n",ca);
        dfs(root);
        del(root);
    }
    return 0;
}

G. Factories

题意

给一棵树，选择 $k(1\le k\le 100)$ 个叶节点，使得两两之间的路径和最小。

题解

$dp[i][j]$ 表示在以 $i$ 为根的子树中选择 $j$ 个叶节点的最小花费，其中不仅包括 $j$ 个节点两两之间的路径，还包括 $j$ 个节点经过节点 $i$ 与另外 $k-j$ 相连的路径和。

转移方程为 $dp[u][i]=min(dp[u][i],dp[u][i-j]+dp[v][j]+j\times (k-j)\times dis[u][v])$

状态转移的时 $i$ 应该从大到小枚举，避免先更新了较小值后面又使用。另外还需要记录一下每个节点的有效值的范围，不然会 $TLE$

代码

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
struct Node{
    int v;
    ll w;
    Node(int _v,int _w){v=_v;w=_w;}
};
vector<Node> node[N];
ll dp[N][110];
ll ans;
int k;
int cnt[N];//记录每个节点有效值的范围
void dfs(int u,int fa){
    for(auto v:node[u]){
        if(v.v==fa)continue;
        dfs(v.v,u);
        int tmp=cnt[u];
        for(int i=k;i>0;i--){
            for(int j=min(cnt[v.v],i);j>0&&i-j<=tmp;j--){
                cnt[u]=max(cnt[u],i);
                dp[u][i]=min(dp[u][i],dp[u][i-j]+dp[v.v][j]+v.w*j*(k-j));
            }
        }
    }
    ans=min(ans,dp[u][k]);
}
int main() {
    int t,n,u,v,w;
    in(t);
    for1(ca,t){
        in(n,k);
        ans=inf_ll;
        for1(i,n){
            node[i].clear();
            meminf(dp[i]);
            dp[i][0]=0;
            cnt[i]=0;
        }
        int root=1;
        for0(i,n-1){
            in(u,v,w);
            node[u].push_back(Node(v,w));
            node[v].pu_b(Node(u,w));
            if(node[u].size()>1)root=u;
            if(node[v].size()>1)root=v;
        }
        for1(i,n)if(node[i].size()==1)dp[i][1]=0,cnt[i]++;
        dfs(root,0);
        assert(ans!=inf_ll);
        printf("Case #%d: %lld\n",ca,ans);
    }
    return 0;
}

题意

题解

代码

1
2