[NOIP2018模拟赛10.16]手残报告

[NOIP2018模拟赛10.16]手残报告

闲扯

炉石乱斗模式美滋滋啊,又颓到好晚…

上来T2先敲了树剖,看T1发现是个思博DP,然后没过大样例,写个暴力发现还是没过大样例!?才发现理解错题意了,真是太菜了

然后看T3发现又要树剖,想了想发现边双缩点似乎能做…结果码来码去比赛临近结束才搞完,赶紧交代码.

但是那台机子上的Chrome似乎是个假的,打开什么网页都巨慢,最后T1手残交了份一开始的错误代码上去,T2T3生死未卜

结果40+0+0 T1错代码居然还有40？！数据这么水…再交遍正确代码一A

T2T3下午检查的时候发现树剖犯了SB错误 还是记在了我错误笔记上的…太菜了

下午改T3边双缩点居然A了std是圆方树的T3?!还跑了rank2?! (虽然现在xxzh巨佬是rank2

而且第一发交的树剖还是有错的.这数据无力吐槽了

晚上码T2,结果至今卡死在70 TLE三点,然而那台老年机都跑过了我也不知道咋回事

T1 轻功

分析

思博DP,$f[i][j]$表示当前使用第$j$轻功种走到$i$这个点的最短时间

$f[i][j]=min(f[i-a[j]][p]+v[j]+[j!=p] \times w)$

预处理一下非法情况就好了

代码

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
/*
  code by RyeCatcher
*/
inline char gc(){
    static char buf[SIZE],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;
    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=505;
const ll inf=1e17;
int n,k,q;
ll v[maxn];
int a[maxn];
bool fob[maxn][105];
bool ok[maxn][105];
ll w,f[maxn][105];
namespace bf{
	ll ans=inf;
	void dfs(int now,int kk,ll c){
		if(ok[now][kk])return ;
		if(now>n)return ;
		if(now==n){
			ans=min(ans,c);
			return ;
		}
		for(ri i=1;i<=k;i++){
			if(ok[now+a[i]][i])continue;
			if(i==kk){
				dfs(now+a[i],i,c+v[i]);
			}
			else dfs(now+a[i],i,c+v[i]+w);
		}
		return ;
	}
	void main(){
		for(ri i=1;i<=k;i++)dfs(0,i,0);
		printf("%lld\n",ans);
		return ;
	}
}
int main(){
	int x,y;
	FO(qinggong);
	read(n),read(k),read(w);
	for(ri i=1;i<=k;i++){
		read(a[i]),read(v[i]);
	}
	memset(fob,0,sizeof(fob));
	memset(ok,0,sizeof(ok));
	read(q);
	while(q--){
		read(x),read(y);
		fob[x][y]=1;
	}
	
	for(ri i=0;i<=n;i++){
		for(ri j=1;j<=k;j++)f[i][j]=inf;
	}
	int t=0;
	for(ri i=0;i<=k;i++)if(!fob[0][i])f[0][i]=0;
	for(ri i=0;i<=n;i++){
		for(ri j=1;j<=k;j++){
			bool flag=0;
			if(i>=a[j]){
				for(ri o=i-a[j];o<=i;o++)if(fob[o][j]){flag=1;break;}
				if(flag)ok[i][j]=1;
			}
		}
	}
	if(n<=15){bf::main();return 0;}
	for(ri i=1;i<=n;i++){
		for(ri j=1;j<=k;j++){
			if(ok[i][j])continue;
			for(ri p=1;p<=k;p++){
				if(i>=a[j]){
					if(ok[i-a[j]][p])continue;
					f[i][j]=min(f[i][j],1ll*(f[i-a[j]][p]+v[j]+((j==p)?0:w)));
				}
			}
		}
	}
	ll ans=inf;
	for(ri i=1;i<=k;i++)ans=min(ans,f[n][i]);
	if(ans==inf)puts("-1");
	else printf("%lld\n",ans);
	return 0;
}

T2 开荒

精巧的树剖，询问时将所有点按$dfs$序排序

钦定当前公共$LCA$ $x$,对于排序后第$i$个点和$i-1$号点的LCA $y$,如果$y$在$x$子树中,那么计算$i$到$y$路径贡献(不包括$y$),否则根据DFS序排序后的性质, $y$就比$x$高明,将$y$设为公共$LCA$,计算$fa[x]$到$i$号点路径贡献

然后一直卡在70分。。。以后能用树状数组再也不用线段树了

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
/*
  code by RyeCatcher
*/
inline char gc(){
    static char buf[SIZE],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;
    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=200005;
const int inf=0x7fffffff;
int n,q;
int que[10000005],cnt=0;
struct Edge{
	int ne,to;
}edge[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to){
	edge[++num_edge].ne=h[f];
	edge[num_edge].to=to;
	h[f]=num_edge;
}
ll w[maxn];
int dep[maxn],fa[maxn],dfn[maxn],top[maxn],size[maxn],son[maxn],tot=0,rnk[maxn];
void dfs_1(int now){
	int v;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now]||dep[v])continue;
		fa[v]=now,dep[v]=dep[now]+1;
		dfs_1(v);
		size[v]+=size[now];
		if(!son[now]||size[v]>size[son[now]])son[now]=v;
	}
	return ;
}
void dfs_2(int now,int t){
	int v;
	top[now]=t,dfn[now]=++tot,rnk[tot]=now;
	if(!son[now])return ;
	dfs_2(son[now],t);
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now]||v==son[now]||dfn[v])continue;
		dfs_2(v,v);
	}
}
int L,R,t;
ll dta,ans=0;
ll s[maxn<<2];
inline void add(){for(;t<=n;t+=t&(-t))s[t]+=dta;}
inline ll sum(int x){ll tmp=0;for(;x;x-=x&(-x))tmp+=s[x];return tmp;}
inline ll calc(int l,int r) {return sum(r)-sum(l-1);}
bool cmp(int a,int b){return dfn[a]<dfn[b];}
inline int get_lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])std::swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])return y;
	return x;
}
inline void query_path(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])std::swap(x,y);
		L=dfn[top[x]],R=dfn[x];
		ans+=calc(L,R);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])std::swap(x,y);
	L=dfn[x],R=dfn[y];
	ans+=calc(L,R);
	return ;
}
inline void solve(){
	int x,y;
	if(cnt==1){
		printf("%lld\n",w[que[1]]);
		return ;
	}
	x=que[1],ans=w[x];
	for(ri i=2;i<=cnt;i++){
		y=get_lca(que[i],que[i-1]);
		if(dfn[x]<=dfn[y]){
			query_path(y,que[i]);
			ans-=w[y];
		}
		else{
			query_path(fa[x],que[i]);
			x=y;
		}
	}
	printf("%lld\n",ans);
	return ;
}
int main(){
	int x,y;
	FO(kaihuang);
	//freopen("ex_kaihuang.in","r",stdin);
	read(n),read(q);
	for(ri i=1;i<=n;i++)read(w[i]);
	for(ri i=1;i<n;i++){
		read(x),read(y);
		add_edge(x,y);
		add_edge(y,x);
	}
	dep[1]=1,fa[1]=0;
	dfs_1(1);
	dfs_2(1,1);
	for(ri i=1;i<=n;i++){
		t=dfn[i],dta=w[i];
		add();
	}
	char opt[10];
	while(q--){
		scanf("%s",opt);
		if(opt[0]=='Q'){
			read(x);
			cnt=0;
			while(x){
				que[++cnt]=x;
				read(x);
			}
			if(cnt==0){
				puts("0");
				continue;
			}
			std::sort(que+1,que+1+cnt,cmp);
			cnt=std::unique(que+1,que+1+cnt)-(que+1);
			solve();
		}
		else{
			read(x),read(y);
			t=dfn[x],dta=y-w[x],w[x]=y;
			add();
		}
		//puts("fafa");
	}
	return 0;
}

T3 跑商

分析

考场上Tarjan还有行写反了G

标算圆方树不会啊,我这个边双感觉就是个挺靠谱的假算法,边双缩点后形成的的树进行树链剖分,缩的点用一个$multiset$动态维护点内的最小值,查询直接树剖

代码

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
inline char gc(){
    static char buf[SIZE],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;
    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=200005;
const int inf=0x7fffffff;
int n,m,q;
ll w[maxn],val[maxn];
struct Edge{
	int ne,to;
}edge[maxn<<1];
struct SE{
	int ne,to;
}se[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to){
	edge[++num_edge].ne=h[f];
	edge[num_edge].to=to;
	h[f]=num_edge;
} 
int sh[maxn],num_se=1;
inline void add_se(int f,int to){
	se[++num_se].ne=sh[f];
	se[num_se].to=to;
	sh[f]=num_se;
}
namespace Tree{//树的情况
	int dep[maxn],fa[maxn],dfn[maxn],rnk[maxn],tot=0,top[maxn],son[maxn],size[maxn];
	void dfs_1(int now){
    	int v;
    	size[now]=1;
    	for(ri i=h[now];i;i=edge[i].ne){
        	v=edge[i].to;
        	if(dep[v]||v==fa[now])continue;
        	dep[v]=dep[now]+1;
        	fa[v]=now;
        	dfs_1(v);
        	size[now]+=size[v];
        	if(!son[now]||size[son[now]]<size[v])son[now]=v;
    	}
	}
	void dfs_2(int now,int t){
    	int v;
    	top[now]=t;
    	dfn[now]=++tot,rnk[tot]=now;
    	if(!son[now])return ;
    	dfs_2(son[now],t);
    	for(ri i=h[now];i;i=edge[i].ne){
        	v=edge[i].to;
        	if(dfn[v]||v==fa[now]||v==son[now])continue;
        	dfs_2(v,v);
    	}
    	return ;
	}
	int L,R,t;
	ll dta;
	ll mi[maxn<<2];
	inline void up(int now){mi[now]=min(mi[now<<1],mi[now<<1|1]);}
	void build(int now,int l,int r){
    	if(l==r){
        	mi[now]=w[rnk[l]];//注意!!! 
        	return ;
    	}
    	int mid=(l+r)>>1;
    	build(now<<1,l,mid);
    	build(now<<1|1,mid+1,r);
    	up(now);
    	return ;
	}
	void update(int now,int l,int r){
    	if(l==r){
        	mi[now]=dta;
        	return ;
    	}
    	int mid=(l+r)>>1;
    	if(t<=mid)update(now<<1,l,mid);
    	else update(now<<1|1,mid+1,r);
    	up(now);
    	return ;
	}
	ll ans=inf;
	void query(int now,int l,int r){
    	if(L<=l&&r<=R){
        	ans=min(ans,mi[now]);
        	return ;
    	}
    	int mid=(l+r)>>1;
    	if(L<=mid)query(now<<1,l,mid);
    	if(mid<R)query(now<<1|1,mid+1,r);
    	up(now);
    	return ;
	}
	inline void query_path(int x,int y){
    	ans=inf;
    	while(top[x]!=top[y]){
        	if(dep[top[x]]<dep[top[y]])std::swap(x,y);
        	L=dfn[top[x]],R=dfn[x];
        	query(1,1,n);
        	x=fa[top[x]];
    	}
    	if(dfn[x]>dfn[y])std::swap(x,y);
    	L=dfn[x],R=dfn[y];
    	query(1,1,n);
    	return ;
	}
	void main(){
		int x,y;
		dep[1]=1,fa[1]=1;
    	dfs_1(1);
    	dfs_2(1,1);
    	build(1,1,n);
    	char opt[5];
    	//puts("fafa");
    	read(q);
    	while(q--){
        	scanf("%s",opt);
       	 	if(opt[0]=='C'){
            	read(x),read(dta);
            	t=dfn[x];
            	w[x]=dta;
            	update(1,1,n);
        	}
        	else{
            	read(x),read(y);
            	ans=inf;
            	if(x==y)puts("0");
            	else {
					query_path(x,y);
            		printf("%lld\n",max(1ll*0,w[x]-ans));
            		//system("PAUSE");
            	}
        	}
    	}
		return;
	}
}
int inb[maxn],cnt=0;
multiset <ll> mib[maxn];
int dep[maxn],rnk[maxn],fa[maxn],dfn[maxn],tot=0,size[maxn],son[maxn],top[maxn];
void dfs_1(int now){
	int v;size[now]=1;
	for(ri i=sh[now];i;i=se[i].ne){
		v=se[i].to;
		if(v==fa[now]||dep[v])continue;
		dep[v]=dep[now]+1,fa[v]=now;
		dfs_1(v);
		size[now]+=size[v];
		if(!son[now]||size[son[now]]<size[v])son[now]=v;
	}
	return ;
}
bool vis[maxn];
void dfs_2(int now,int t){
	int v;top[now]=t;
	dfn[now]=++tot,rnk[tot]=now;
	if(!son[now])return ;
	dfs_2(son[now],t);
	for(ri i=sh[now];i;i=se[i].ne){
		v=se[i].to;
		if(dfn[v]||v==son[now]||v==fa[now])continue;
		dfs_2(v,v);
	}
	return ;
}
int L,R,t;
ll lst,dta;
ll mi[maxn<<2];
inline void up(int now){mi[now]=min(mi[now<<1],mi[now<<1|1]);}
void build(int now,int l,int r){
	if(l==r){
		mi[now]=*mib[rnk[l]].begin();
		return ;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	up(now);
}
void update(int now,int l,int r){
	if(l==r){
		mib[rnk[l]].erase(mib[rnk[l]].lower_bound(lst));
		mib[rnk[l]].insert(dta);
		mi[now]=*mib[rnk[l]].begin();
		return ;
	}
	int mid=(l+r)>>1;
	if(t<=mid)update(now<<1,l,mid);
	else update(now<<1|1,mid+1,r);
	up(now);
	return ;
}
ll ans=inf;
void query(int now,int l,int r){
	if(L<=l&&r<=R){
		ans=min(ans,mi[now]);
		return ;
	}
	int mid=(l+r)>>1;
	if(L<=mid)query(now<<1,l,mid);
	if(mid<R)query(now<<1|1,mid+1,r);
	up(now);
	return ;
}
inline void query_path(int x,int y){
	ans=inf;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])std::swap(x,y);
		L=dfn[top[x]],R=dfn[x];
		//printf("%d %d %d %d\n",x,y,L,R);
		query(1,1,cnt);
		x=fa[top[x]];
	}
	if(dfn[x]>dfn[y])std::swap(x,y);
	L=dfn[x],R=dfn[y];//puts("wtf");
	//printf("%d %d %d %d\n",x,y,L,R);
	query(1,1,cnt);
	return ;
}
int low[maxn],dd[maxn],pc=0;
bool bri[maxn<<1];
void tarjan(int now,int id){
	int v;
	dd[now]=low[now]=++pc;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(!dd[v]){
			tarjan(v,i);
			low[now]=min(low[now],low[v]);
			if(dd[now]<low[v]){
				bri[i]=bri[i^1]=1;
			}
		}
		else if(i!=(id^1))low[now]=min(low[now],dd[v]);
	}
	return ;
}
void pre_dfs(int now,int fa){
	int v;
	vis[now]=1;
	mib[cnt].insert(w[now]);
	inb[now]=cnt;
	//printf("%d %d\n",now,fa);
	for(ri i =h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(inb[v]||bri[i]||bri[i^1]||v==fa)continue;
		pre_dfs(v,now);
	}
	return ;
}
bool fg=0;
void pre_ck(int now,int fa){
	int v;vis[now]=1;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa)continue;
		if(vis[v]){fg=1;return ;}
		pre_ck(v,now);
	}
	return ;
}
int main(){
	int x,y;
	FO(paoshang);
	//freopen("paoshang1.in","r",stdin);
	read(n),read(m);
	for(ri i=1;i<=n;i++)read(w[i]);
	for(ri i=1;i<=m;i++){
		read(x),read(y);
		add_edge(x,y);
		add_edge(y,x);
	}
	pre_ck(1,0);
	if(!fg){Tree::main();return 0;}
	memset(vis,0,sizeof(vis));
	for(ri i=1;i<=n;i++)if(!dd[i])tarjan(i,0);
	for(ri i=1;i<=n;i++){
		if(!inb[i]){
			cnt++;
			pre_dfs(i,0);
		}
	}
	for(ri i=1;i<=n;i++){
		x=inb[i];
		for(ri j=h[i];j;j=edge[j].ne){
			y=inb[edge[j].to];
			if(x!=y){
				add_se(x,y);
				add_se(y,x);
			}
		}
	}
	//printf("--%d--\n",cnt);	
	dep[1]=1,fa[1]=0;
	tot=0;
	dfs_1(1);
	dfs_2(1,1);
	build(1,1,cnt);
	read(q);
	char opt[5];
	while(q--){
		scanf("%s",opt);
		if(opt[0]=='C'){
			read(x),read(dta);
			lst=w[x];
			t=dfn[inb[x]];
			w[x]=dta;
			update(1,1,cnt);
		}
		else{
			read(x),read(y);
			if(x==y)puts("0");
			else {
				query_path(inb[x],inb[y]);
				printf("%lld\n",max(1ll*0,w[x]-ans));
			}		
		}
	}
	return 0;
}