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$，从而求出所...
Codeforces Round #614 简要题解
Div1 Div2 从一月份一直咕到现在的一场比赛 /kel ConneR and the A.R.C. Markland-N 暴力往两边找即可。 代码 JOE is on TV! 显然每次淘汰掉刚好一个人是最好的。 答案即为 $\sum_{i=1}^n\frac{1}{i}$。 代码 NEKO's Maze Game 维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即...
AGC028E High Elements
AtCoder 分析 因为要字典序最小，所以可以贪心，从前往后确定所有位，每位尽量填 $0$。 为了方便，我们把是 $p$ 中的前缀最大值的前缀最大值称作“旧的“，不是 $p$ 中前缀最大值的前缀最大值称作”新的“。 首先有一个结论：如果一个 $s$ 合法，那么 $x,y$ 两个序列中一定有一个序列的前缀最大值全都是旧的。 证明可以这样考虑：如果 $x,y$ 中都有一个新的前缀最大值，那么我...
CF1344D Résumé Review
Codeforces Luogu 分析 对 $f_i(x)=x(a_i-x^2)$ 求二阶导可以发现它是凸的，那么每次选一个 $\Delta y$ 最大的放一定是最优的。 我们二分最小的 $\Delta y$，对每个函数二分（或者直接解一元二次方程）找到它被加的次数，判断是否 $\leq k$ 即可。 这样子最后可能并不能达到 $k$，把还没加的部分选加到 $\Delta y$ 最大的那些上...
AGC027F Grafting
AtCoder 分析 先考虑如果有一个点没有被操作过该怎么做。 我们把这个点作为根，在两棵树上分别 DFS 一遍，那么如果有解的话答案一定是在两棵树上父节点不同的点数。 现在的问题在于如何判无解。首先如果 A 中一个点不要被操作但它的父节点要被操作，那么一定是无解的。否则，考虑到 A 中一个点的父节点要在它之后被操作，B 中一个点的父节点要在它之前被操作，这样子就有若干个偏序关系，我们只需要...