多校里的一道好题

ACM

hdu contest7里面一道超级好的题目

hdu 5296

题解

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
#define push_back pb
#define make_pair mp
#define first X
#define second Y
int n, m;
struct Edge{
    int to, next, w;
}edge[maxn<<1];
int tot, head[maxn];
bool is_root[maxn];
int F[maxn*2];//dfs的第一次的序号和第二次的序号
int p[maxn];//第一次出现的下标
int cnt;
int rmq[maxn*2];//表示的是深度
int dis[maxn<<1];
bool vis[maxn];
struct ST{
    int mm[maxn<<1];
    int dp[maxn<<1][20];
    //dp保存的是区间的最小值的下标
    void init(int n){
        mm[0] = -1;
        for(int i=1; i<=n; i++){
            mm[i] = ((i)&(i-1))==0?mm[i-1]+1:mm[i-1];
            dp[i][0] = i;
        }
        for(int j=1; j<=mm[n]; j++){
            for(int i=1; i+(1<<j)-1<=n; i++){
                dp[i][j] = rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?
                            dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
            }
        }
    }
    int query(int a, int b){
        if(a>b) swap(a, b);
        int k = mm[b-a+1];
        return rmq[dp[a][k]]<=rmq[dp[b-(1<<k)+1][k]]?
                dp[a][k]:dp[b-(1<<k)+1][k];
        }
}st;
void init(){
    tot = 0;
    memset(head, -1, sizeof(head));
}
void add_edge(int u, int v, int w){
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void dfs(int u, int pre, int dep){
    F[++cnt] = u;
    rmq[cnt] = dep;
    p[u] = cnt;
    for(int i=head[u]; ~i; i=edge[i].next){
        int v = edge[i].to;
        if(v == pre) continue;
        dis[v] = dis[u]+edge[i].w;
        dfs(v, u, dep+1);
        F[++cnt] = u;
        rmq[cnt] = dep;
    }
}
void lca_init(int rt, int n){
    cnt = 0;
    dfs(rt, rt, 0);
    st.init(2*n);
}
int lca_query(int u, int v){
    return F[st.query(p[u], p[v])];
}
set<int> s;
int Cal(int u)//计算dfs序为u的点的加入集合增加的花费
{
    if (s.empty()) return 0;
    int x,y;//x,y分别是比dfs序为u的点大的最小点和比它小的最大点
    set<int>::iterator it = s.upper_bound(u);//返回集合中第一个键值大于u的元素迭代器位置
    if (it == s.end()||it == s.begin())//没有比他大的或者都比他大
    {
        x = F[*s.rbegin()];//*s.rbegin()是dfs序,在这里转换成了原树上的节点保存于x
        y = F[*s.begin()];
    }
    else
    {
        x = F[*it];
        it--;
        y = F[*it];
    }
    u = F[u];//u也换回成原树上的节点来计算
    return dis[u] - dis[lca_query(x,u)] - dis[lca_query(y,u)] + dis[lca_query(x,y)];
}
int main(){
    int _;
    scanf("%d", &_);
    int kas=0;
    while(_--){
        scanf("%d%d", &n, &m);
        memset(dis, 0, sizeof(dis));
        init();
        int u, v, w;
        printf("Case #%d:\n",++kas);
        for(int i=0; i<n-1; i++){
            scanf("%d%d%d", &u, &v, &w);
            add_edge(u, v, w);
            add_edge(v, u, w);
        }
        int rt = 1;
        lca_init(rt, n);
        memset(vis, 0, sizeof(vis));
        s.clear();
        int ans = 0;
        int op;
        for (int i = 0;i < m;++i)
        {
            scanf("%d %d",&op,&u);
            if (op == 1)
            {
                if (!vis[u])
                {
                    vis[u] = 1;
                    ans += Cal(p[u]);//用u的dfs序去计算
                    s.insert(p[u]);
                }
            }
            else
            {
                if (vis[u])
                {
                    vis[u] = 0;
                    s.erase(p[u]);
                    ans -= Cal(p[u]);
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

Gym - 101808K Another Shortest Path Problem

题目链接
题解
cf官方的题解
一个无向图，图的形状是基环树，问任意两点之间的最短距离。
我们只要删去一条边，使得基环树的结构变成树形的结构就行了。
然后求任意两点之间的最短距离的时候，只要分情况讨论就可以了。

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
#define push_back pb
#define make_pair mp
#define first X
#define second Y
typedef long long ll;
int n, m;
struct Edge{
    int to, next;
    ll w;
}edge[maxn<<1];
int tot, head[maxn];
int F[maxn*2];//dfs的第一次的序号和第二次的序号
int p[maxn];//第一次出现的下标
int cnt;
int rmq[maxn*2];//表示的是深度
ll dis[maxn<<1];
struct ST{
    int mm[maxn<<1];
    int dp[maxn<<1][26];
    //dp保存的是区间的最小值的下标
    void init(int n){
        mm[0] = -1;
        for(int i=1; i<=n; i++){
            mm[i] = ((i)&(i-1))==0?mm[i-1]+1:mm[i-1];
            dp[i][0] = i;
        }
        for(int j=1; j<=mm[n]; j++){
            for(int i=1; i+(1<<j)-1<=n; i++){
                dp[i][j] = rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?
                            dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
            }
        }
    }
    int query(int a, int b){
        if(a>b) swap(a, b);
        int k = mm[b-a+1];
        return rmq[dp[a][k]]<=rmq[dp[b-(1<<k)+1][k]]?
                dp[a][k]:dp[b-(1<<k)+1][k];
        }
}st;
void init(){
    tot = 0;
    memset(head, -1, sizeof(head));
}
void add_edge(int u, int v, int w){
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void dfs(int u, int pre, int dep){
    F[++cnt] = u;
    rmq[cnt] = dep;
    p[u] = cnt;
    for(int i=head[u]; ~i; i=edge[i].next){
        int v = edge[i].to;
        if(v == pre) continue;
        dis[v] = dis[u]+edge[i].w;
        dfs(v, u, dep+1);
        F[++cnt] = u;
        rmq[cnt] = dep;
    }
}
void lca_init(int rt, int n){
    cnt = 0;
    dfs(rt, rt, 0);
    st.init(2*n);
}
int lca_query(int u, int v){
    return F[st.query(p[u], p[v])];
}
ll cal(int x,int y)
{
    return dis[x]+dis[y]-2*dis[lca_query(x,y)];
}
int main(){
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &m);
        memset(dis, 0, sizeof(dis));
        init();
        int u, v; ll w;
        for(int i=0; i<n-1; i++){
            scanf("%d%d%lld", &u, &v, &w);
            add_edge(u, v, w);
            add_edge(v, u, w);
        }
        int X,Y;ll Z;
        scanf("%d%d%lld",&X,&Y,&Z);
        int rt = 1;
        lca_init(rt, n);
        ll ans=0;
        while(m--)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            ans=cal(u,v);
            ans=min(ans,cal(u,X)+cal(v,X));
            ans=min(ans,cal(u,Y)+cal(v,Y));
            ans=min(ans,cal(u,X)+cal(v,Y)+Z);
            ans=min(ans,cal(u,Y)+cal(v,X)+Z);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

poj 2763

ac code

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e5+10;
#define push_back pb
#define make_pair mp
#define first X
#define second Y
typedef long long ll;
int n, m;
struct Edge{
    int to, next;
    ll w;
    int id;
}edge[maxn<<1];
ll w[maxn];
int tot, head[maxn];
int F[maxn*2];//dfs的第一次的序号和第二次的序号
int p[maxn];//第一次出现的下标
int cnt;
int rmq[maxn*2];//表示的是深度
ll dis[maxn<<1];
int dfs_clock;
int l[maxn<<1], r[maxn<<1];
int G[maxn];
struct ST{
    int mm[maxn<<1];
    int dp[maxn<<1][26];
    //dp保存的是区间的最小值的下标
    void init(int n){
        mm[0] = -1;
        for(int i=1; i<=n; i++){
            mm[i] = ((i)&(i-1))==0?mm[i-1]+1:mm[i-1];
            dp[i][0] = i;
        }
        for(int j=1; j<=mm[n]; j++){
            for(int i=1; i+(1<<j)-1<=n; i++){
                dp[i][j] = rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?
                            dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
            }
        }
    }
    int query(int a, int b){
        if(a>b) swap(a, b);
        int k = mm[b-a+1];
        return rmq[dp[a][k]]<=rmq[dp[b-(1<<k)+1][k]]?
                dp[a][k]:dp[b-(1<<k)+1][k];
        }
}st;
void init(){
    tot = 0;
    memset(head, -1, sizeof(head));
    dfs_clock = 0;
}
void add_edge(int u, int v, int w, int id){
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].id = id;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void dfs(int u, int pre, int dep){
    F[++cnt] = u;
    rmq[cnt] = dep;
    p[u] = cnt;
    l[u] = ++dfs_clock;
    for(int i=head[u]; ~i; i=edge[i].next){
        int v = edge[i].to;
        if(v == pre) continue;
        dis[v] = dis[u]+edge[i].w;
        G[edge[i].id] = v;
        dfs(v, u, dep+1);
        F[++cnt] = u;
        rmq[cnt] = dep;
    }
    r[u] = dfs_clock;
}
void lca_init(int rt, int n){
    cnt = 0;
    dfs(rt, rt, 0);
    st.init(2*n);
}
int lca_query(int u, int v){
    return F[st.query(p[u], p[v])];
}
ll c[maxn<<2];
int lowbit(int x){
    return x&(-x);
}
void update(int x, int val){
    while(x<=n){
        c[x] += val;
        x += lowbit(x);
    }
}
ll sum(int x){
    ll ans = 0;
    while(x>0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
ll cal(int x,int y)
{
    return sum(l[x])+sum(l[y])-2*sum(l[lca_query(x,y)]);
}
int s;
int main(){
    while(~scanf("%d%d%d", &n, &m, &s)){
        memset(dis, 0, sizeof(dis));
        memset(c, 0, sizeof(c));
        init();
        int u, v;
        int ww;
        for(int i=1; i<=n-1; i++){
            scanf("%d%d%d", &u, &v, &ww);
            add_edge(u, v, ww, i);
            add_edge(v, u, ww, i);
            w[i] = ww;
        }
        int X,Y;
        int Z;
        w[n] = Z;
        int rt = 1;
        lca_init(rt, n);
        //cout<<"hahah"<<lca_query(3, 4)<<endl;
//        for(int i=1; i<=n; i++){
//            cout<<i<<"   "<<l[G[i]]<<" "<<r[G[i]]<<endl;
//        }
//        for(int i=1; i<=n; i++){
//            cout<<i<<" "<<G[i]<<endl;
//        }
//        cout<<"dfs_clock"<<endl;
//        for(int i=1; i<=n; i++){
//            cout<<i<<" "<<l[i]<<" "<<r[i]<<endl;
//        }
        for(int i=1; i<n; i++){
            update(l[G[i]], w[i]);
            update(r[G[i]]+1, -w[i]);
        }
        ll ans=0;
        int op;
        ll vv;
        int now = s;
        while(m--)
        {
            scanf("%d", &op);
            if(op == 0){
                scanf("%d", &u);
                ans = cal(now, u);
                printf("%d\n", ans);
                now = u;
            }
            else {
                scanf("%d%lld", &u, &vv);
                update(l[G[u]], vv-w[u]);
                update(r[G[u]]+1, -vv+w[u]);
                w[u] = vv;
            }
        }
    }
    return 0;
}

hdu 6393

题解来源
上面做的题目都是为这一道题目进行铺垫的，这道题太好了！！！
首先给一个无向图的基环树，然后有两种操作：

  1. 询问u, v之间的最短路
  2. 修改编号为i的边的边权为x

题解

首先拆任意一条边，使之变成树形的结构。
用树状数组维护边的权值。

ac code

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
#define push_back pb
#define make_pair mp
#define first X
#define second Y
typedef long long ll;
int n, m;
struct Edge{
    int to, next;
    ll w;
    int id;
}edge[maxn<<1];
ll w[maxn];
int tot, head[maxn];
int F[maxn*2];//dfs的第一次的序号和第二次的序号
int p[maxn];//第一次出现的下标
int cnt;
int rmq[maxn*2];//表示的是深度
ll dis[maxn<<1];
int dfs_clock;
int l[maxn<<1], r[maxn<<1];
int G[maxn];
struct ST{
    int mm[maxn<<1];
    int dp[maxn<<1][26];
    //dp保存的是区间的最小值的下标
    void init(int n){
        mm[0] = -1;
        for(int i=1; i<=n; i++){
            mm[i] = ((i)&(i-1))==0?mm[i-1]+1:mm[i-1];
            dp[i][0] = i;
        }
        for(int j=1; j<=mm[n]; j++){
            for(int i=1; i+(1<<j)-1<=n; i++){
                dp[i][j] = rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?
                            dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
            }
        }
    }
    int query(int a, int b){
        if(a>b) swap(a, b);
        int k = mm[b-a+1];
        return rmq[dp[a][k]]<=rmq[dp[b-(1<<k)+1][k]]?
                dp[a][k]:dp[b-(1<<k)+1][k];
        }
}st;
void init(){
    tot = 0;
    memset(head, -1, sizeof(head));
    dfs_clock = 0;
}
void add_edge(int u, int v, int w, int id){
    edge[tot].to = v;
    edge[tot].w = w;
    edge[tot].id = id;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void dfs(int u, int pre, int dep){
    F[++cnt] = u;
    rmq[cnt] = dep;
    p[u] = cnt;
    l[u] = ++dfs_clock;
    for(int i=head[u]; ~i; i=edge[i].next){
        int v = edge[i].to;
        if(v == pre) continue;
        dis[v] = dis[u]+edge[i].w;
        G[edge[i].id] = v;
        dfs(v, u, dep+1);
        F[++cnt] = u;
        rmq[cnt] = dep;
    }
    r[u] = dfs_clock;
}
void lca_init(int rt, int n){
    cnt = 0;
    dfs(rt, rt, 0);
    st.init(2*n);
}
int lca_query(int u, int v){
    return F[st.query(p[u], p[v])];
}
ll c[maxn<<2];
int lowbit(int x){
    return x&(-x);
}
void update(int x, int val){
    while(x<=n){
        c[x] += val;
        x += lowbit(x);
    }
}
ll sum(int x){
    ll ans = 0;
    while(x>0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
ll cal(int x,int y)
{
    return sum(l[x])+sum(l[y])-2*sum(l[lca_query(x,y)]);
}
int main(){
    int _;
    scanf("%d", &_);
    while(_--){
        scanf("%d%d", &n, &m);
        memset(dis, 0, sizeof(dis));
        memset(c, 0, sizeof(c));
        init();
        int u, v;
        int ww;
        for(int i=1; i<=n-1; i++){
            scanf("%d%d%d", &u, &v, &ww);
            add_edge(u, v, ww, i);
            add_edge(v, u, ww, i);
            w[i] = ww;
        }
        int X,Y;
        int Z;
        scanf("%d%d%lld",&X,&Y,&Z);
        w[n] = Z;
        int rt = 1;
        lca_init(rt, n);
//        for(int i=1; i<=n; i++){
//            cout<<i<<"   "<<l[G[i]]<<" "<<r[G[i]]<<endl;
//        }
        for(int i=1; i<n; i++){
            update(l[G[i]], w[i]);
            update(r[G[i]]+1, -w[i]);
        }
        ll ans=0;
        int op;
        ll vv;
        while(m--)
        {
            scanf("%d%d%lld", &op, &u, &vv);
            if(op == 0){
                if(u==n)
                    w[n] = vv;
                else{
                    update(l[G[u]],vv-w[u]);
                    update(r[G[u]]+1,-vv+w[u]);
                    w[u]=vv;
                }
            }
            else {
                ans=cal(u,vv);
                ans=min(ans,cal(u,X)+cal(vv,X));
                ans=min(ans,cal(u,Y)+cal(vv,Y));
                ans=min(ans,cal(u,X)+cal(vv,Y)+Z);
                ans=min(ans,cal(u,Y)+cal(vv,X)+Z);
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}

未解决的问题

本文标题:多校里的一道好题

文章作者:Babydragon

发布时间:2018-08-14, 15:15:20

最后更新:2018-08-14, 21:25:01

原始链接:http://baolintian.github.io/2018/08/14/多校里的一道好题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. hdu 5296
    1. 1.1. ac code
  2. 2. Gym - 101808K Another Shortest Path Problem
    1. 2.1. ac code
  3. 3. poj 2763
    1. 3.1. ac code
  4. 4. hdu 6393
    1. 4.1. 题解
    2. 4.2. ac code
  5. 5. 未解决的问题
{{ live2d() }}