[NOIP2018模拟10.15]比赛报告

[NOIP2018模拟10.15]比赛报告

闲扯

昨晚又颓到好晚,Yali的降智光环感觉持续至今…

题面好评 T1T3都玩过 逃)

T1没看多久就开始写二分+并查集 然后T3看着眼熟想了一个多小时…结果啥都没想出来

赶紧看T2发现还是没什么思路,码个暴力回来看T1,发现了两个致命又SB的错误,倒数15分钟前终于改回来,刺激

结果80+35+0 T1还是挂分了,检查时发现还是一个思博错误,没有判上下相连与左右相连情况,感谢出题人良心数据

T2调了好久结果爆栈RE,不想改了。T3听完晚上的讲评后才茅塞顿开,太菜了

T1 刺客信条 AC

分析

我的做法很naiive,直接距离,将每个人看成圆心画一个二分距离的圆,两个圆有交就连在一起,最后判断Ezio能不能过去.

这里的判读大佬们都是将4面墙看成4个点处理,我最SB,每个点开四个bool变量记录,合并时暴力合并bool值

std求了个最小生成树,比较神奇

然后加了一些优化,预处理点对距离,特判之类的一开始跑了个rank4

代码

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
/*
  code by RyeCatcher
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <utility>
#include <cmath>
#include <queue>
#include <vector>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w",stdout);
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define ri register int
#define ll long long
#define ull unsigned long long
#define SIZE 1<<22
using std::sqrt;
using std::min;
using std::max;
using std::priority_queue;
using std::queue;
using std::vector;
using std::pair;
using namespace __gnu_pbds;
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*10)+c-48;x=ne?-x:x;return ;
}
const int maxn=3005;
const int inf=0x7fffffff;
const long double eps=1e-7;
struct Pt{
    long double x,y;
}pt[maxn];
long double X,Y;
int fa[maxn];
struct Flag{
    bool f1,f2,f3,f4;
    inline void clear(){f1=f2=f3=f4=0;}
}ff[maxn];
inline void merge(int x,int y){
    if(ff[x].f1|ff[y].f1)ff[x].f1=ff[y].f1=1;
    if(ff[x].f2|ff[y].f2)ff[x].f2=ff[y].f2=1;
    if(ff[x].f3|ff[y].f3)ff[x].f3=ff[y].f3=1;
    if(ff[x].f4|ff[y].f4)ff[x].f4=ff[y].f4=1;
    return ;
}
int get(int x){
    merge(x,fa[x]);
    if(fa[x]!=x){
        fa[x]=get(fa[x]);
    }
    return fa[x];
}
bool vis[maxn];
long double fafa[maxn][maxn];
int n;
bool check(long double Dis){
    for(ri i=1;i<=n;i++){
        vis[i]=0;
        fa[i]=i;
		ff[i].clear();
    }
    long double x,y;
    for(ri i=1;i<=n;i++){
    	int cnt=0;
        x=pt[i].x,y=pt[i].y;
        if(Dis-x>1e-11)ff[i].f1=1,cnt++;
        if(Dis-y>1e-11)ff[i].f2=1,cnt++;
        if(Dis-(X-x)>1e-11)ff[i].f3=1,cnt++;
        if(Dis-(Y-y)>1e-11)ff[i].f4=1,cnt++;
        //if(cnt>=2)return 1;
        if(ff[i].f1&&ff[i].f2)return 1;
        if(ff[i].f3&&ff[i].f4)return 1;
        
    }
    int fx,fy;
    for(ri i=1;i<=n;i++){
        x=pt[i].x,y=pt[i].y;
        for(ri j=i+1;j<=n;j++){
            long double p=fafa[i][j];
            if(Dis*2-p>1e-11){
                fx=get(i),fy=get(j);
                fa[fx]=fy;
                merge(fx,fy);
            }
        }
    }
    for(ri i=1;i<=n;i++){
        fx=get(i);
        if(vis[fx])continue;
        vis[fx]=1;
        int tmp=ff[fx].f1+ff[fx].f2+ff[fx].f3+ff[fx].f4;
        if(ff[fx].f1&&ff[fx].f2)return 1;
        if(ff[fx].f3&&ff[fx].f4)return 1;
        if(ff[fx].f2&&ff[fx].f4)return 1;
        if(ff[fx].f1&&ff[fx].f3)return 1;
    }
    return 0;
}
int main(){
	long double x,y;
	//freopen("AC.in","r",stdin);
	//freopen("AC.out","w",stdout);
    read(X),read(Y),read(n);
    for(ri i=1;i<=n;i++){
        read(pt[i].x),read(pt[i].y);
    }
    for(ri i=1;i<=n;i++){
        x=pt[i].x,y=pt[i].y;
        for(ri j=i+1;j<=n;j++){
            fafa[i][j]=sqrtl((x-pt[j].x)*(x-pt[j].x)+(y-pt[j].y)*(y-pt[j].y));
        }
    }
    long double mid,L=0,R=sqrtl(X*X+Y*Y+233);
    while(R-L>eps){
        mid=(L+R)/2;
        if(check(mid))R=mid;
        else L=mid;
        //printf("%.4lf %.4lf\n",L,R);
    }
    printf("%.2Lf\n",R);
    return 0;
}

T2 黑暗之魂 darksoul

分析

先不考虑自环和重边,最终的图像肯定是一个环,环上若干点,点可能向外扩展成一棵树

假如最终答案在一颗树中,我们就要求出树上相距最远的两点,用树形DP即可,

$g[x]$表示向下在以x为根的子树中最远能扩展到哪里,$o[x]$表示次远值

g[x]=max(g[x],g[v]+dis(x,v)),o[x]就不赘述了

然后以x为LCA的两点最远值f[x]=g[x]+o[x],然后$max_{x \in T}(f[x])$就是树T的贡献

但是如果答案的路径经过了环上的边呢,对于环上路径$(x,y)$. (x,y都是环上的点)

它的贡献为$g[x]+g[y]+dis(x,y)$

$g$值我们是已经求出来的,但是$dis$怎么求?我们化环为链,钦定起点$st$,用前缀和数组$pre[x]$表示$dis(st,x)$

那么$dis(x,y)$就是$pre[x]-pre[y]$(设$x$在$y$之后),注意我们要倍长这条链

这样贡献就变成了$g[x]+pre[x]+g[y]-pre[y]$

然而需要注意的是如果$pre[x]-pre[y]$大于环周长的一半是不合法的,为啥?因为他总是选择最短路走,既然这段大于周长一半,反过来走肯定更短

暴力的做法就是N方环上每一对点枚举一遍,考虑高级一点的做法,发现化环为链后处理的$pre$数组是单调递增的,

于是维护一个$g[y]-pre[y]$值递减的滑动窗口(因为当前点为$x$,$g[x]+pre[x]$是固定的),一旦队头$p$到当前点距离,即$pre[x]-pre[p]$大于两倍周长就弹出队头

然后大佬们都是用拓扑排序搞,我只会naiive的深搜,然后交上去最后两个点爆栈了

同时还发现我没有考虑答案是在一棵树中的情况,只能说这数据水了…

代码

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
/*
  code by RyeCatcher
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <utility>
#include <queue>
#include <vector>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w",stdout);
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define ri register int
#define ll long long
#define ull unsigned long long
#define SIZE 1<<22
using std::min;
using std::max;
using std::priority_queue;
using std::deque;
using std::vector;
using std::pair;
using namespace __gnu_pbds;
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=2000005;
const int inf=0x7fffffff;
struct Edge{
	int ne,to;
	ll dis;
}edge[maxn<<1];
int h[maxn];ll 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;
}
int n;
int fa[maxn],dep[maxn];
bool vis[maxn],flag_1;
int fo1,fo2;
void pre_dfs(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]&&dep[v]==dep[now]+1){
        	//puts("11");
			for(ri k=h[now];k;k=edge[k].ne){
				//printf("%d\n",edge[k].to);
				if(edge[k].to==v){
					if(!fo1)fo1=k;
					else fo2=k;
				}
			}
			flag_1=1;return ;
		}
		else if(vis[v])continue;
        dep[v]=dep[now]+1;
        pre_dfs(v,now);
    }
    return;
}
namespace Tree{
    ll Tmp=-1,ans=-1;
    int rt=1;
    void dfs_1(int now,int fa,ll dis){
        int v;
        if(Tmp<dis){
            rt=now,Tmp=dis;
        }
        for(ri i=h[now];i;i=edge[i].ne){
            v=edge[i].to;
            if(i==fo1||i==fo2)continue;
            if(v==fa||v==now)continue;
            dfs_1(v,now,dis+edge[i].dis);
        }
        return ;
    }
    void dfs_2(int now,int fa,ll dis){
        int v;
        ans=max(ans,dis);
        for(ri i=h[now];i;i=edge[i].ne){
            v=edge[i].to;
            if(i==fo1||i==fo2)continue;
            if(v==fa||v==now)continue;
            dfs_2(v,now,dis+edge[i].dis);
        }
        return ;
    }
    void main(){
    	if(edge[fo1].dis<edge[fo2].dis){
    		fo1=fo2^1;
		}
		else{
			fo2=fo1^1;
		}
        dfs_1(1,0,0);
        Tmp=-1;
        dfs_2(rt,0,0);
        printf("%lld\n",ans+1);
        return ;
    }
}
int sta[maxn],cnt=0,st,ed,len=0;
bool on_cyc[maxn];
void find_cyc(int now){
	int v;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now])continue;
		if(dep[v]&&dep[v]<dep[now]){
			st=now,ed=v;
			int x=now;
			while(x!=v)len++,on_cyc[x]=1,sta[++cnt]=x,x=fa[x];
			len++,on_cyc[v]=1,sta[++cnt]=v;
			continue;
		}
		else if(dep[v])continue;
		fa[v]=now;
		dep[v]=dep[now]+1;
		find_cyc(v);
	}
	return ;
}
int rt;
ll dm[maxn];
ll tmp=-1,cc=0;
ll dp[maxn];
void dfs_1(int now,int fa){
	int v;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(on_cyc[v]||v==fa)continue;
		dfs_1(v,now);
		dp[now]=max(dp[now],dp[v]+edge[i].dis);
	}
	return ;
}
ll pre[maxn];//dist from st
int ff[maxn],ne[maxn],tot=0;
void dfs_on_cyc(int now,int fa){
	int v;
	if(tot==len*2-1)return ;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v!=ne[now])continue;
		pre[tot+1]=pre[tot]+edge[i].dis;
		ff[++tot]=v;
		if(tot==len+1)cc=pre[tot];
		dfs_on_cyc(v,now);
	}
	return ;
}
deque <int> q;
ll arr[maxn];
int main(){	
	bool flag=0;
	int x,y;ll z;
	FO(darksoul);
	//freopen("darksoul19.in","r",stdin);
	read(n);
	//puts("sss");
	//system("PAUSE");
	for(ri i=1;i<=n;i++){
		read(x),read(y),read(z);
		add_edge(x,y,z);
		add_edge(y,x,z);
		if(x==y)flag=1;
	}
	dep[1]=1;
	pre_dfs(1,0);
	if(flag||flag_1){
		//puts("ss");
		Tree::main();return 0;
	}
	//memset(vis,0,sizeof(vis));
	memset(dep,0,sizeof(dep));
	fa[1]=0,dep[1]=1;
	find_cyc(1);
	for(ri i=1;i<=cnt;i++){
		rt=sta[i];
		if(i!=cnt)ne[sta[i]]=sta[i+1];
		else ne[sta[i]]=sta[1];
		tmp=-1;
		dfs_1(rt,0);
		dm[sta[i]]=dp[rt];
	}
	tot=1,ff[1]=sta[1];
	dfs_on_cyc(st,0);
	for(ri i=1;i<=len*2-1;i++){		
		arr[i]=dm[ff[i]]-pre[i];
	}
	ll ans=-1;
	for(ri k=1;k<=len*2-1;k++){				
		if(q.empty())q.push_back(k);
		else{	
			while(q.size()&&pre[k]-pre[q.front()]>cc/2)q.pop_front();		
			ans=max(ans,dm[ff[k]]+pre[k]+arr[q.front()]);
			while(q.size()&&arr[q.back()]<=arr[k])q.pop_back();
			q.push_back(k);
		}
	}
	printf("%lld\n",ans+1);
	return 0;
}

T3 传送门 portal

分析

巧妙的树形DP

假设当前我们正在$x$点,$y$是$x$的一个儿子,$f[x]$表示以$x$为根的子树的最优答案,

ialsk4.png

那么我们考虑假如传送门在$y$,那么$y$的贡献就是$f[y]+c*2$,因为$x,y$还得靠你自己走

假如一个传送门在$x$,那么$y$的贡献为$sum_e(y) \times 2-g(y)+c$,$sum_e(y)$表示$y$的子树中边权之和,$g(y)表示$$y$的子树中的最长链长度.

这时候有人会问一个问题,你这样为什么不每次走到底再传送到x然后再经过$c$,但是这样的话要经过多次$c$,为什么不干脆将传送门设在$y$,这样的贡献肯定不会比你那样走更多,所以我们这时候要选择最长链跳,其余的都靠步行的方式计算贡献

综上$f[x]= \sum min(f[y]+c \times 2,sum_e(y) \times 2-g(y)+c)$

由于我们能够安排儿子的$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
75
76
77
78
/*
  code by RyeCatcher
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <utility>
#include <queue>
#include <vector>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w",stdout);
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define ri register int
#define ll long long
#define ull unsigned long long
#define SIZE 1<<22
using std::min;
using std::max;
using std::priority_queue;
using std::queue;
using std::vector;
using std::pair;
using namespace __gnu_pbds;
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=1000005;
const int inf=0x7fffffff;
int n;
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;
}
ll g[maxn],s[maxn],f[maxn];
void dfs(int now,int fa){
	int v;ll c;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa)continue;
		dfs(v,now);
		c=edge[i].dis;
		s[now]=s[now]+s[v]+c;
		g[now]=max(g[now],g[v]+c);
		f[now]+=min(s[v]*2-g[v]+c,f[v]+c*2);
	}
	return ;
}
int main(){
	int x,y,z;
	FO(portal);
	read(n);
	for(ri i=1;i<n;i++){
		read(x),read(y),read(z);
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	dfs(1,0);
	printf("%lld\n",f[1]);
	return 0;
}