天天爱跑步怎么玩的

admin

《天天爱跑步》是一个养成类游戏,主要玩法如下:

游戏地图

游戏的地图可以看作一棵包含 \( n \) 个结点和 \( n-1 \) 条边的树。

每个结点编号为从 1 到 \( n \) 的连续正整数。

玩家起点和终点

有 \( m \) 个玩家,每个玩家有一个起点 \( s_i \) 和一个终点 \( t_i \)。

游戏过程

每天打卡任务开始时,所有玩家在第 0 秒同时从自己的起点出发。

玩家以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去。

玩家跑到终点后,该玩家就算完成了打卡任务。

观察员

在每个结点上都放置了一个观察员。

如果玩家在第 \( w_j \) 秒到达终点,则在结点 \( j \) 的观察员可以观察到这个玩家。

活跃度计算

观察员可以观察到在某个结点到达的玩家数量,这可以用来衡量游戏的活跃度。

具体算法

路径拆分

将一条路径拆分为往上和往下两条路径。

设路径的起点为 \( u \),终点为 \( v \),他们的最低公共祖先(LCA)为 \( p \)。

上行的路可以对 \( x \) 造成贡献当且仅当 \( dep[u] - dep[x] = w_x \),移项得 \( dep[u] = w_x + dep[x] \)。

观察者贡献

对于把结点 \( j \) 作为终点的玩家,如果在第 \( w_j \) 秒前到达终点,则在结点 \( j \) 的观察员不能观察到该玩家;

如果正好在第 \( w_j \) 秒到达终点,则在结点 \( j \) 的观察员可以观察到这个玩家。

示例输入输出

输入:

```

n = 4

m = 2

edges = [(1, 2), (1, 3), (2, 4)]

watch_times = [0, 2, 4]

player_starts = [1, 2]

player_ends = [3, 4]

```

输出:

```

[2, 0, 1, 1]

```

解释:

在结点 1,有 2 个玩家(1 和 2)在 0 秒到达,所以观察到 2 人。

在结点 2,没有玩家在 2 秒到达,所以观察到 0 人。

在结点 3,有 1 个玩家(2)在 4 秒到达,所以观察到 1 人。

在结点 4,有 1 个玩家(1)在 4 秒到达,所以观察到 1 人。

建议

玩家需要每天按时上线完成打卡任务,以保持游戏的连续性和活跃度。

观察员机制可以帮助了解每个结点的活跃情况,从而优化游戏设计。