多校第九场总结,树剖

Posted by Cww97 on 2017-08-23

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/77493673
http://bestcoder.hdu.edu.cn/blog/

02

官方题解

由于没有修改操作,一个显然的想法是离线处理所有问题
将询问拆成1-x,1-y,1-LCA(x,y),则处理的问题转化为从根到节点的链上的问题。
解决这个问题,我们可以在dfs时向treap插入当前的数,在退出时删除这个数,并且每次维护在该点上的答案。
当然也可以将所有的查询和点权排序,用树链剖分做这个题,在线段树上面插入就ok。

一开始队友说用lca让他变成,让我解决怎么求带限制的区间和的问题,
jcx说:“我负责任的告诉你,主席树”
忘了,完全忘了怎么写,出事了,于是乎,百度一波,搜到一个例题,百度那个题号
发现可以对查询排序,离线查询,分批次插入线段树(用树状数组更短更简单)

于是算法出炉:每次ask求a到b的,转化为求1到a-1和1到b,将每次ask的a-1和b同归为k,对所有的k排序去重(ks[]),每次将小于k[i]的所有礼物插入线段树,然后更新有k的ask,然后处理k[i++],实现起来巨烦无比。

然后,队友发现lca搞出的序列不清真,只能处理rmq的情况,有重复的点,算sum肯定崩盘

mdzz,czj -

改算法,有重复的,树映射到线段树上,树链剖分嘛,怎么早没想到,这个时候因为写的一波离线查询的各种struct已经身心疲惫,两个队友还说,交给我,一个也不来帮忙,想砍人
树剖这里讲的不错

改完发现代码180行了,哇
为了防止自己在这一团炸裂的逻辑中迷失,这里我分了好多struct,略微增加了行数,不过,也增加了一些可读性吧(划掉)

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
177
178
179
180
181
182
183
184
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3e5 + 7;
typedef long long LL;
int n;
struct gift{
int pos, val;
void read(int id){
scanf("%d", &val);
pos = id;
}
bool operator < (const gift & b) const {
return val < b.val;
}
} gifts[N];

struct ZKWsegTree{
#define lc (t<<1)
#define rc (t<<1^1)
LL sum[N];
int M;
inline void build(int n){
M = 1; for(;M<n;)M<<=1; if(M!=1)M--;
memset(sum, sizeof(sum), 0);
}
void add(int t, LL x){
for (sum[t+=M]+=x, t>>=1; t; t>>=1){
sum[t] = sum[lc] + sum[rc];
}
}
LL query(int l, int r){
LL ans = 0;
for (l+=M-1,r+=M+1; l^r^1; l>>=1,r>>=1){
if (~l&1) ans += sum[l^1];
if ( r&1) ans += sum[r^1];
}
return ans;
}
} T;

struct TreeChain{
struct Edge{
int from, to, nxt;
Edge(){}
Edge(int u, int v, int n):
from(u), to(v), nxt(n){}
}edges[N];
int n, E, head[N];

int tim;
int siz[N]; //用来保存以x为根的子树节点个数
int top[N]; //用来保存当前节点的所在链的顶端节点
int son[N]; //用来保存重儿子
int dep[N]; //用来保存当前节点的深度
int fa[N]; //用来保存当前节点的父亲
int tid[N]; //用来保存树中每个节点剖分后的新编号,线段树
int Rank[N];//tid反向数组,不一定需要

inline void AddEdge(int f, int t){
edges[++E] = Edge(f, t, head[f]);
head[f] = E;
}
inline void Init(int n){
tim = 0;
this -> n = n ; E = -1;
for (int i = 0; i <= n; i++) head[i] = -1;
for (int i = 0; i <= n; i++) son[i] = -1;
}

void dfs1(int u, int father, int d){
dep[u] = d;
fa[u] = father;
siz[u] = 1;
int nxt;
for(int i = head[u]; i != -1; i = nxt){
Edge &e = edges[i]; nxt = e.nxt;
if (e.to == father) continue;
dfs1(e.to, u, d + 1);
siz[u] += siz[e.to];
if(son[u]==-1 || siz[e.to] > siz[son[u]]) son[u] = e.to;
}
}
void dfs2(int u, int tp){
top[u] = tp;
tid[u] = ++tim;
Rank[tid[u]] = u;
if (son[u] == -1) return;
dfs2(son[u], tp);
int nxt;
for(int i = head[u]; i != -1; i = nxt){
Edge &e = edges[i]; nxt = e.nxt;
if(e.to == son[u] || e.to == fa[u]) continue;
dfs2(e.to, e.to);
}
}
LL query(int u, int v){
int f1 = top[u], f2 = top[v];
LL tmp = 0;
for (; f1 != f2;){
if (dep[f1] < dep[f2]){
swap(f1, f2);
swap(u, v);
}
tmp += T.query(tid[f1], tid[u]);
u = fa[f1]; f1 = top[u];
}
if (dep[u] > dep[v]) swap(u, v);
return tmp + T.query(tid[u], tid[v]);
}
} g ;

int ks[N], K, H;
map<int, int> hashK;
vector<int> whoAsk[N*2];
void insertK(int id, int k){
if (hashK.find(k) == hashK.end()) {
hashK[k] = ++H;
whoAsk[H].clear();
}
whoAsk[hashK[k]].push_back(id);
}
struct ask{
int u, v, a, b, pos;
vector<LL> ans;
void read(int pos){
this->pos = pos;
ans.clear();
scanf("%d%d%d%d", &u, &v, &a, &b);
a--;
ks[++K] = a, ks[++K] = b;
insertK(pos, a);
insertK(pos, b);
}
} asks[N];

int main () {
freopen("in.txt", "r", stdin);
int m, u, v;
while(cin >> n >> m) {
for(int i = 1; i <= n; i++) {
gifts[i].read(i);
}
sort(gifts + 1, gifts + n+1);
g.Init(n);
for(int i = 0; i < n - 1; i++) {
scanf("%d%d", &u, &v);
g.AddEdge(u, v);
g.AddEdge(v, u);
}
g.dfs1(1, -1, 0);
g.dfs2(1, 1);

T.build(n);
K = 0, H = 0;
hashK.clear();
for (int i = 1; i <= m; i++) asks[i].read(i);
sort(ks + 1, ks + K+1);
K = unique(ks + 1, ks + K+1) - (ks + 1);

int cur = 1;
for (int i = 1; i <= K; i++){
for (int &j = cur; j <= n; j++){
if (gifts[j].val > ks[i]) break;
T.add(g.tid[gifts[j].pos], gifts[j].val);
}
int kk = hashK[ks[i]];
for (int j = 0; j < whoAsk[kk].size(); j++){
ask &a = asks[whoAsk[kk][j]];
a.ans.push_back(g.query(a.u, a.v));
}
}

for (int i = 1; i <= m; i++){
printf("%lld", abs(asks[i].ans[1] - asks[i].ans[0]));
putchar(i==m ? '\n' : ' ');
}
}
return 0;
}

05

官方题解说

缩点为DAG,则如果在拓扑序中出现了有两个及以上入度为0的点则不合法

哇,我咋没想到,比赛的时候看见这题刚刚开始有人A的时候都是1800ms过的,好多200msWA的

于是乎,感觉这是个大暴力,算个复杂度,好像似乎,不会炸吧(虽然后来证实极限数据会炸,6000条边)

当时的想法是,先WA一发再说,做n次dfs,然后就过了

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
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N = 1e3 + 10;
const int M = 6e3 + 10;

struct Dinic{
struct Edge{
int from, to, nxt;
Edge(){}
Edge(int u, int v, int n):
from(u), to(v), nxt(n){}
}edges[M];
int n, E, head[N];
bool vis[N], reach[N][N];

inline void AddEdge(int f, int t){
edges[++E] = Edge(f, t, head[f]);
head[f] = E;
}

inline void Init(int n){
this -> n = n ; E = -1;
for (int i=0;i<=n;i++) head[i] = -1;
}

void dfs(int start, int u){
vis[u] = 1;
reach[start][u] = 1;
int nxt;
for (int i = head[u]; i != -1; i = nxt){
Edge &e = edges[i]; nxt = e.nxt;
if (vis[e.to]) continue;
dfs(start, e.to);
}
}

inline bool live(){
memset(reach, 0, sizeof(reach));
for (int i = 1; i <= n; i++){
memset(vis, 0, sizeof(vis));
dfs(i, i);
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (!(reach[i][j] | reach[j][i])) return false;
}
}
return true;
}
} g ;

int main(){
///freopen("in.txt", "r", stdin);
int _, n, m, u, v;
scanf("%d", &_);
for (; _--;){
scanf("%d%d", &n, &m);
g.Init(n);
for (; m--;){
scanf("%d%d", &u, &v);
g.AddEdge(u, v);
}
if (g.live()) puts("I love you my love and our love save us!");
else puts("Light my fire!");
}
return 0;
}

06

官方题解

类比cf 835E,枚举二进制位按照标号当前位为1 和当前位为0分为两个集合,每次求解两个集合之间的最短路即可覆盖到所有的点对。时间复杂度20*dijstla时间

厉害厉害,我们用了一个有毒的算法,n次dj,只有第一次情况dist数组为INF,之后用之前的结果
哪位大佬看下正确性(队友信誓旦旦说是对的),还是数据弱

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
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<queue>
#include<vector>
using namespace std;

typedef long long LL;
const int MAXN = 1e5 + 5;
typedef pair<int,int> pii;
vector<pii> vec[MAXN];
int st[MAXN];
int d[MAXN];
const int INF = 0x3f3f3f3f;
void dijkstra(int s) {
priority_queue<pii, vector<pii>, greater<pii> > que;
que.push(pii(0, s));
while(!que.empty()) {
pii p = que.top(); que.pop();
int v = p.second;
if(d[v] < p.first) continue;
for(int i = 0; i < vec[v].size(); i++) {
pii e = vec[v][i];
if(e.first != s && d[e.first] > p.first + e.second) {
d[e.first] = p.first + e.second;
que.push(pii(d[e.first], e.first));
}
}
}
}
int main()
{
int T;
cin >> T;
for(int cas = 1; cas <= T; cas++) {
int n, m;
cin >> n >> m;
for(int i = 0; i <= n; i++) vec[i].clear();
for(int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
vec[u].push_back(pii(v, w));
}
int k;
cin >> k;
for(int i = 0; i < k; i++) {
scanf("%d", st + i);
}
fill(d, d + n + 1, INF);
for(int i = 0; i < k; i++) {
dijkstra(st[i]);
}
int Min = INF;
for(int i = 0; i < k; i++) {
Min = min(Min, d[st[i]]);
}
printf("Case #%d: %d\n", cas, Min);
}
return 0;
}

08

这里写图片描述
这里写图片描述

代码这么丑,一看就不是我写的

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+10;
const int MOD = 1e9+7;
typedef long long LL;
map<int, int> mp;
vector<int> vec;
vector<int> ans;
int main () {
int m;
while(cin >> m) {
vec.clear();ans.clear();
for(int i = 0; i < m; i++) {
int x;
scanf("%d", &x);
vec.push_back(x);
mp[x]++;
}
//int n = (-1 + (int)sqrt(2+4*m)) / 2;
sort(vec.begin(), vec.end());
for(int i = 0; i < m; i++) {
int x = vec[i];
if(mp[x] > 0) {
mp[x]--;
for(int j = 0; j < ans.size(); j++) {
mp[x + ans[j]]--;
}
ans.push_back(x);
}
}
printf("%d\n", ans.size());
for(int i = 0; i < ans.size(); i++) {
printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
}
}

return 0;
}

10

定义dp[i][j][k],k = 0,表示A串从0~i 的子串A[0,i],能否匹配B串从0~j的子串B[0,j];k = 1,表示A[0,i] + A[i]能否匹配B[0,j]。

本来不想开这题,md开局100+提交没人过,后来没题开了

转移时考虑几种特殊情况,”a*” 可以匹配 “” ,”a”,”aa”…,”._“可以匹配”“,”a”,”b”,”aa”,”bb”…,注意 “._” 不能匹配 “ab”这种串。

现场看见很多用java交TLE的,看来是用正则表达式直接套的,本题,明明可以贪心的(划掉),队友出到数据来hack这个贪心了,丹这个时候,已经A了,果然本场数据有毒

完了,这个代码快把我丑哭了

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
#include<bits/stdc++.h>
using namespace std;
string a;
string b;
int cnt[100];
int main(){
for(int i = 0; i < 100; i++) cnt[i] = i;
int t;
cin >> t;
getchar();
while( t-- ){
getline( cin,a );
getline( cin,b );
bool thisflag=true;
a+=']';
b+=']';
int positionA,positionB;
positionA=positionB=cnt[2] - 2;;
for( ; positionA<a.size()&&positionB<b.size(); ){
if( a[positionA]==b[positionB] ){
positionA++;
positionB++;
continue;
} else if( b[positionB]=='.' ){
b[positionB]=a[positionA];
positionA++;
positionB++;
continue;
} else if( b[positionB]=='*' ){
if( positionB+1<b.size()&&positionB>0&&b[positionB+1]==b[positionB-1] ){
swap( b[positionB],b[positionB+1] );
continue;
}else{
while( a[positionA]==b[positionB-1] ){
positionA++;
}
positionB++;
}
} else if( a[positionA]!=b[positionB] ){
if( positionB+1<b.size()&&b[positionB+1]=='*' ){
positionB+=2;
}else{
thisflag=false;
break;
}
}
}
if( !thisflag ) printf( "no\n" );
else printf( "yes\n" );
}
}

再修一修树剖的板

不知道为什么,用char op, scanf %c会TLE
改成char op[5], scanf %s就过了
有毒

这里写图片描述
这里写图片描述

hdu3966

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 7;
typedef long long LL;
const int INF = 0x3f3f3f3f;
int n, a[N];
int tid[N]; //用来保存树中每个节点剖分后的新编号,线段树

struct ZKWsegTree{
int tree[N];
int M, n;

void build(int n){
this->n = n;
M = 1; while (M < n) M <<= 1; if (M!=1) M--;
for (int t = 1 ; t <= n; t++) tree[tid[t]+M] = a[t];
for (int t = n+1; t <= M+1; t++) tree[t+M] = INF;
for (int t = M; t >= 1; t--) tree[t] = min(tree[t<<1], tree[t<<1^1]);
for (int t = 2*M+1; t >= 1; t--) tree[t] = tree[t] - tree[t>>1];
}

void update(int l, int r, int val){
int tmp;
for (l+=M-1, r+=M+1; l^r^1; l>>=1, r>>=1){
if (~l&1) tree[l^1] += val;
if ( r&1) tree[r^1] += val;
if (l > 1) tmp = min(tree[l], tree[l^1]), tree[l]-=tmp, tree[l^1]-=tmp, tree[l>>1]+=tmp;
if (r > 1) tmp = min(tree[r], tree[r^1]), tree[r]-=tmp, tree[r^1]-=tmp, tree[r>>1]+=tmp;
}
for (; l > 1; l >>= 1){
tmp = min(tree[l], tree[l^1]), tree[l]-=tmp, tree[l^1]-=tmp, tree[l>>1]+=tmp;
}
tree[1] += tree[0], tree[0] = 0;
}

int query(int t){
t += M;
int ans = tree[t];
for (;t > 1;) ans += tree[t>>=1];
return ans;
}
} T;

struct TreeChain{
struct Edge{
int from, to, nxt;
Edge(){}
Edge(int u, int v, int n):
from(u), to(v), nxt(n){}
}edges[N];
int n, E, head[N];

int tim;
int siz[N]; //用来保存以x为根的子树节点个数
int top[N]; //用来保存当前节点的所在链的顶端节点
int son[N]; //用来保存重儿子
int dep[N]; //用来保存当前节点的深度
int fa[N]; //用来保存当前节点的父亲
//int tid[N]; //用来保存树中每个节点剖分后的新编号,线段树, 全局变量了
int Rank[N];//tid反向数组,不一定需要

inline void AddEdge(int f, int t){
edges[++E] = Edge(f, t, head[f]);
head[f] = E;
}
inline void Init(int n){
this -> n = n; E = -1; tim = 0;
for (int i = 0; i <= n; i++) head[i] = -1;
for (int i = 0; i <= n; i++) son[i] = -1;
}

void dfs1(int u, int father, int d){
dep[u] = d;
fa[u] = father;
siz[u] = 1;
int nxt;
for(int i = head[u]; i != -1; i = nxt){
Edge &e = edges[i]; nxt = e.nxt;
if (e.to == father) continue;
dfs1(e.to, u, d + 1);
siz[u] += siz[e.to];
if(son[u]==-1 || siz[e.to] > siz[son[u]]) son[u] = e.to;
}
}
void dfs2(int u, int tp){
top[u] = tp;
tid[u] = ++tim;
Rank[tid[u]] = u;
if (son[u] == -1) return;
dfs2(son[u], tp);
int nxt;
for(int i = head[u]; i != -1; i = nxt){
Edge &e = edges[i]; nxt = e.nxt;
if(e.to == son[u] || e.to == fa[u]) continue;
dfs2(e.to, e.to);
}
}
void update(int u, int v, int x){
int f1 = top[u], f2 = top[v];
for (; f1 != f2;){
if (dep[f1] < dep[f2]){
swap(f1, f2);
swap(u, v);
}
T.update(tid[f1], tid[u], x);
u = fa[f1]; f1 = top[u];
}
if (dep[u] > dep[v]) swap(u, v);
T.update(tid[u], tid[v], x);
}
} g ;

int main () {
///freopen("in.txt", "r", stdin);
int n, m, q, u, v, x;
char op[5];
for (; ~scanf("%d%d%d", &n, &m, &q);) {
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
g.Init(n);
for (; m--;){
scanf("%d%d", &u, &v);
g.AddEdge(u, v);
g.AddEdge(v, u);
}
g.dfs1(1, 0, 0);
g.dfs2(1, 1);
T.build(n);
for (; q--;){
scanf("%s", op);
if (op[0] == 'Q'){
scanf("%d\n", &u);
printf("%d\n", T.query(tid[u]));
}else{
scanf("%d%d%d\n", &u, &v, &x);
if (op[0] == 'I') g.update(u, v, x);
else g.update(u, v, -x);
}
}
}
return 0;
}