【NOIP2016】天天爱跑步

我能写80分我也是佩服我自己

我都想了80分了还没想到正解我也是佩服我自己

先讲部分分吧:

\(n\le 1000\):暴力。

一条链:第\(i\)个点能观察到的一定是\(i-w_i\)向右跑的和\(i+w_i\)向左跑的,只要跑了大于等于\(w_i\)即可,于是每个点记录所有以它为起点的玩家跑了多远,排序二分。

\(S=1\):只有以\(1\)为根的情况下\(dep_i=w_i\)的点能观察到,且能观察到的个数为它子树中终点的个数。标记并DFS即可。(我个SB还用了树状数组)

\(T=1\):一个玩家能被一个观察者观察到当且仅当玩家跑过了观察者且\(dep_s-dep_i=w_i\),即\(dep_s=dep_i+w_i\),然后打标记乱搞。

那么满分就是T=1复杂一点:必须要跑过观察者,并且有从上往下跑的。

将每个玩家从lca拆成两段,对于向上的和\(T=1\)同样处理,只是在lca上面再打一个\(-1\)的标记。向下的满足\(dep_i-w_i=2dep_{lca}-dep_s\)即可,在lca处打一个\(-1\)标记。

正解的lca用Tarjan求,复杂度为O(n+m)。我不会Tarjan lca就用倍增了,比较慢。

3
说点什么

2 Comment threads
1 Thread replies
1 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
游客

lca树链剖分求啊。。常数小跟O(1)没什么区别

成员
MasterJH5574

RG又换头像了0.0

游客
裙夏臣

%光勋