[NOIP2018模拟赛10.19]只会暴力报告

闲扯

今天又是暴力满满(并不)的一天呢

昨天老师说了分数要正态分布,今天看起来…不过暴力分很多,虽然我人太傻逼又没打满

T1 woc?不是说送分的吗,看起来又是个树形DP神题,暴力告辞,链上的搞一搞

T2 woc?又是树 纪中这么喜欢出图/树题的吗?第一眼暴力dij告辞

T3 woc?又又又是树?!看起来十分码农?!部分分还好很多,想到昨天老师提到了天天爱跑步的例子,感觉可以搞一搞…于是就开始爆肝了…结果期望30分开了个fread爆0了

$30+30+0$凉凉,T2堆改成$paring$_$heap$就50了,辣鸡STL.虽然有一个更优的暴力…

T1 lkf

又是道神奇树形DP,分析先咕会

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
/*
  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=3335;
const int inf=0x7fffffff;
const int P=19260817;
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;
}
int n,k,w[maxn],mx=-inf;
int id,o,lim;
ll f[maxn][maxn];
ll ans=0;
void dfs(int now,int fa){
	int v;ll p=1;
	//printf("%d %d\n",now,fa);
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa)continue;
		if(w[v]>=o&&w[v]<=o+lim&&(w[v]!=o||(w[v]==o&&v>id))){
			dfs(v,now);
			//printf("%d %d %d\n",fa,now,v);
			p=p*(f[v][lim]+1)%P;
		}
	}
	f[now][lim]=p;
	return ;
}
int main(){
	int x,y;
	read(n),read(k);
	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);
	}
	for(ri i=1;i<=n;i++){
		o=w[i],id=i,lim=k;
		dfs(i,0);
		//puts("wtf");
		if(k==0){
			ans=(ans+f[i][k])%P;
		}
		else{
			lim=k-1;
			dfs(i,0);
			ans=(ans+(f[i][k]-f[i][lim])%P+P)%P;
		}
	}
	printf("%lld\n",ans%P);
	return 0;
}

T2 worry

有个性质就是因为你树上边随便走,你断掉一条树边后你最多走一条非树边。$naiive$的做法就是枚举了,有没有更高明的呢?

我们边从小到大排序,发现对于边$(x,y)$,它影响$(x,y)$路径上的边(也就是断掉路径上的任何一条边还可以通过$(x,y)$联通),也就是$x,y$分别到$lca(x,y)$路径上的

树链剖分

那么链剖就可以搞喽,线段树维护一个永久标记,如果有标记了也不管(因为边权从小到大排序)

跑得还挺快

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
/*
  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=200005;
const int inf=0x7fffffff;
int n,m;
struct Edge{
	int ne,to;
	ll dis;
}edge[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to,ll c){
	edge[++num_edge].ne=h[f];
	edge[num_edge].to=to;
	edge[num_edge].dis=c;
	h[f]=num_edge;
}
pair<int,int> qwq[maxn];
struct Niconiconi{
	int x,y;
	ll dis;
	Niconiconi(){x=y=dis=0;}
	Niconiconi(int _x,int _y,ll _c){x=_x,y=_y,dis=_c;}
	bool operator <(const Niconiconi &rhs)const{
		return dis<rhs.dis;
	}
}con[maxn<<1];
int dep[maxn],fa[maxn],son[maxn],size[maxn],top[maxn],dfn[maxn],rnk[maxn],tot=0;
void dfs1(int now){
	int v;
	size[now]=1;
	//printf("%d %d\n",now,fa[now]);
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now])continue;
		dep[v]=dep[now]+1,fa[v]=now;
		dfs1(v);
		size[now]+=size[v];
		if(!son[now]||size[son[now]]<size[v])son[now]=v;
	}
	return ;
}
void dfs2(int now,int t){
	int v;
	top[now]=t,dfn[now]=++tot,rnk[tot]=now;
	if(!son[now])return ;
	dfs2(son[now],t);
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now]||v==son[now])continue;
		dfs2(v,v);
	}
	return ;
}
int tag[maxn<<2],w[maxn];
int L,R,dta;
inline void pushdown(int now){
	if(!tag[now<<1])tag[now<<1]=tag[now];//tag[now<<1|1]=tag[now];
	if(!tag[now<<1|1])tag[now<<1|1]=tag[now];
}
void update(int now,int l,int r){
	if(tag[now])return ;
	if(L<=l&&r<=R){
		tag[now]=dta;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(now);
	if(L<=mid&&!tag[now<<1])update(now<<1,l,mid);
	if(mid<R&&!tag[now<<1|1])update(now<<1|1,mid+1,r);
	return ;
}
void ahaha(int now,int l,int r){
	if(l==r){
		if(tag[now])w[rnk[l]]=tag[now];
		else w[rnk[l]]=-1;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(now);
	ahaha(now<<1,l,mid);
	ahaha(now<<1|1,mid+1,r);
	return ;
}
inline void update_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];
		update(1,1,n);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])std::swap(x,y);
	L=dfn[x]+1,R=dfn[y];
	//printf("--%d %d--\n",rnk[L],rnk[R]);
	if(L>R)return ;
	update(1,1,n);
}
int main(){
	int x,y;ll z;
	FO(worry);
	read(n),read(m);
	for(ri i=1;i<n;i++){
		read(x),read(y);
		add_edge(x,y,0);
		add_edge(y,x,0);
		qwq[i]=pair<int,int>(x,y);
	}
	for(ri i=1;i<=m;i++){
		read(x),read(y),read(z);
		con[i]=Niconiconi(x,y,z);
	}
	std::sort(con+1,con+1+m);
	dep[1]=0,fa[1]=0;
	dfs1(1);
	dfs2(1,1);
	memset(tag,0,sizeof(tag));
	for(ri i=1;i<=m;i++){
		x=con[i].x,y=con[i].y,dta=con[i].dis;
		update_path(x,y);
	}
	ahaha(1,1,n);
	for(ri i=1;i<n;i++){
		x=qwq[i].first,y=qwq[i].second;
		if(dep[x]<dep[y])std::swap(x,y);
		printf("%d\n",w[x]);
	}
	return 0;
}

并查集

题解是更高明的并查集做法,我还是Too Young Too Simple,只会SB暴力树剖

每个点指向下一个没被打标记的点$nxt[x]$(以点代边),显然这是可传递的

这样的话每次查询直接往上跳就好了,连LCA都不用求

居然跑到rank1哈哈

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
/*
  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=100005;
const int inf=0x7fffffff;
int n,m;
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;
}
struct Niconiconi{
	int x,y,z;
	bool operator <(const Niconiconi &qwq)const{
		return z<qwq.z;
	}
}nico[maxn];
int ans[maxn],dep[maxn],fa[maxn],nxt[maxn],fa_id[maxn];
int get(int x){return (nxt[x]==x)?nxt[x]:nxt[x]=get(nxt[x]);}
void dfs(int now){
	int v;
	for(ri i=h[now];i;i=edge[i].ne){
		if((v=edge[i].to)==fa[now])continue;
		fa[v]=now,dep[v]=dep[now]+1,fa_id[v]=i;
		dfs(v);
	}
	return ;
}
int main(){
	int x,y,z,p;
	FO(worry);
	read(n),read(m);nxt[n]=n;
	for(ri i=1;i<n;i++){
		read(x),read(y);
		add_edge(x,y),add_edge(y,x);
		nxt[i]=i;
	}
	for(ri i=1;i<=m;i++){
		read(nico[i].x),read(nico[i].y),read(nico[i].z);
	}
	std::sort(nico+1,nico+1+m);
	fa[1]=0,dfs(1);
	for(ri i=1;i<=m;i++){
		x=get(nico[i].x),y=get(nico[i].y),z=nico[i].z;
		while(x!=y){
			if(dep[x]<dep[y])std::swap(x,y);
			ans[fa_id[x]]=z;
			nxt[x]=x=get(fa[x]);	
		}
	}
	p=2*n;
	for(ri i=2;i<p;i+=2){
		printf("%d\n",ans[i]?ans[i]:(ans[i^1]?ans[i^1]:-1));
	}
	return 0;
}