CF1062F Upgrading Cities
Codeforces 分析 一个结论：拓扑排序时，任意时刻同时在队列中的两个点不能互相到达。 设已经访问到的点数为 $tot$，那么 如果队列中只有 $u$ 一个点，那么它可以到达剩下的 $n-tot$ 个点。 如果队列中有 $u,x$ 两个点，那么首先 $u$ 不能到达 $x$；其次如果 $x$ 的出边中有一个点 $v$ 入度为 $1$，则 $u$ 一定无法到达那个点，那么 $u$ 就不...
M_sea 发布的文章
- 首页
- M_sea
UOJ513 【UR #19】清扫银河
UOJ 分析 结论：如果有解，那么步数必然 $\leq m+1$。 证明：首先操作 $2$ 可以合并，所以只需要进行至多一次；其次，我们随便造一个生成森林，那么每条非树边就相当于一个简单环，从而操作 $1$ 的次数不会超过非树边数。所以总操作数至多为 $m-n+2\leq m+1$。 于是我们只需要判是否有解即可。 那么我们相当于要选若干个简单环异或 $1$，使得所有 $1$ 边变成 $0$...
洛谷3547 [POI2013]CEN-Price List
Luogu 分析 显然最短路只有三种可能： 全走 $a$ 边。 把两条 $a$ 边看成一条 $b$ 边，如果还剩一条 $a$ 边就走 $a$ 边。 全走 $b$ 边。 前两种只需要简单 0/1 BFS 一遍即可，关键在于第三种如何处理。 有一个显然的 $\mathcal{O}(m^2)$ 思路是，枚举 $u$ 的出边 $v$ 和 $v$ 的出边 $w$，如果 $u,w$ 间没有连边就用 ...
LOJ576 「LibreOJ NOI Round #2」签到游戏
LOJ 分析 设 $s_i$ 为 $\sum_{j=1}^i b_j$，则一次询问可以确定 $s_r-s_{l-1}$。如果我们看成连边 $(l-1,r)$，则相当于要让 $(0,n)$ 连通，也就是要求最小生成树。 根据 Kruskal 那套理论，我们一定会连边 $(0,n)$。 根据 Prim 那套理论，剩下的点要么连 $(0,i)$，要么连 $(i,n)$。更具体的，一定存在一个点 $...
洛谷2179 [NOI2012]骑行川藏
Luogu LOJ 分析 我们画出每条路线的 $t-E$ 图像，大概是这个样子的（蓝色的是原函数，红色的是它的导数）： 感性理解一下可以知道，最后每条路径在其消耗的能量处的导数相同。 于是我们可以二分这个导数，然后把每段的速度求出来，算一下总能量是否 $\leq E_U$ 来 check。 现在考虑已知导数怎么算速度。我们有 这个东西在 $[v',+\infty)$ 上是单增的，所以同样...
UOJ515 【UR #19】前进四
UOJ 分析 把所有操作离线，按下标从大到小扫描线，并维护一棵以时间为下标的和后缀 $\min$ 有关的线段树。 那么每个操作相当于对某段时间内取 $\min$，一个位置的后缀最小值个数就是它被取 $\min$ 的次数。 用 Segment Tree Beats 维护即可。 具体的，我们只需要维护最大值、严格次大值和最大值被取 $\min$ 的次数，如果最大值 $\leq$ 要取 $\min...
CF997E Good Subsegments
Codeforces 分析 考虑一个好区间实际上是 $\max-\min=r-l$。 把所有询问按右端点排序，然后扫描线，则我们需要维护每个左端点到右端点的信息。 考虑每个左端点维护 $(\max-\min)-(r-l)$，显然这个东西是 $\geq 0$ 的，所以我们只需要维护最小值出现次数即可，可以用线段树维护。在右移右端点时需要更新信息，用单调栈维护最值即可。 但是我们要求的是所有区间...
LOJ2865 「IOI2018」狼人
LOJ UOJ Luogu 分析 以端点的 $\min$ 为边权建一棵 Kruskal 重构树，以端点的 $\max$ 为边权建一棵 Kruskal 重构树。 那么我们在第一棵树上从 $s$ 向上跳到最浅的 $\geq l$ 的点，其子树就是人类状态下从起点出发能走到的点；在第二课树上从 $t$ 向上跳到最浅的 $\geq r$ 的点，其子树就是狼人状态下能走到终点的点。 那么我们只需要求这...
CF1349D Slime and Biscuits
Codeforces 分析 设 $E(x)$ 为游戏结束时所有饼干都在 $x$ 手中的期望次数，$E'(x)$ 为游戏结束当且仅当所有饼干都在 $x$ 手中时的期望次数，$P(x)$ 为游戏结束时所有饼干都在 $x$ 手中的概率，$C$ 为所有饼干都在某个人手中时全部到另一个人手中的期望次数，则有 又因为 $g_0=f_0-f_1=n-1$，所以我们可以递推求出所有 $g_i$，从而求出所...