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」狼人
LOJUOJLuogu分析以端点的 $\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$，从而求出所有 $f...
Codeforces Round #614 简要题解
Div1Div2从一月份一直咕到现在的一场比赛 /kelConneR and the A.R.C. Markland-N暴力往两边找即可。代码JOE is on TV!显然每次淘汰掉刚好一个人是最好的。答案即为 $\sum_{i=1}^n\frac{1}{i}$。代码NEKO's Maze Game维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即可。代码Aroma's...
AGC028E High Elements
AtCoder分析因为要字典序最小，所以可以贪心，从前往后确定所有位，每位尽量填 $0$。为了方便，我们把是 $p$ 中的前缀最大值的前缀最大值称作“旧的“，不是 $p$ 中前缀最大值的前缀最大值称作”新的“。首先有一个结论：如果一个 $s$ 合法，那么 $x,y$ 两个序列中一定有一个序列的前缀最大值全都是旧的。证明可以这样考虑：如果 $x,y$ 中都有一个新的前缀最大值，那么我们交换这两...
AtCoder Regular Contest 081 简要题解
比赛地址Make a Rectangle求出每种边的数量，$\geq 4$ 的看成 $2$ 个，$\in[2,3]$ 的看成 $1$ 个，将最大值和次大值作为长和宽即可。代码Coloring Dominoes根据当前列和上一列的情况算出当前的方案数，用乘法原理乘起来即可。代码Don't Be a Subsequence设 $nxt_{i,j}$ 表示 $[i,n]$ 中最靠前的 $j$ 字符...
CF1344D Résumé Review
CodeforcesLuogu分析对 $f_i(x)=x(a_i-x^2)$ 求二阶导可以发现它是凸的，那么每次选一个 $\Delta y$ 最大的放一定是最优的。我们二分最小的 $\Delta y$，对每个函数二分（或者直接解一元二次方程）找到它被加的次数，判断是否 $\leq k$ 即可。这样子最后可能并不能达到 $k$，把还没加的部分选加到 $\Delta y$ 最大的那些上即可。代码...
AtCoder Regular Contest 080 简要题解
比赛地址4-adjacent我们把所有数分成 $3$ 类：$4$ 的倍数、不是 $4$ 的倍数但是是 $2$ 的倍数、奇数。那么肯定是第三种和第一种交错排，在最后放第二种最好。直接判一下第一种的数量是否 $\geq$ 最后一种的数量即可。当没有第二种数时最后还可以放一个第三种数，此时应该是第一种的数量 $+1\geq$ 最后一种的数量。代码Grid Coloring蛇形填上每种颜色即可。代码...
AGC027F Grafting
AtCoder分析先考虑如果有一个点没有被操作过该怎么做。我们把这个点作为根，在两棵树上分别 DFS 一遍，那么如果有解的话答案一定是在两棵树上父节点不同的点数。现在的问题在于如何判无解。首先如果 A 中一个点不要被操作但它的父节点要被操作，那么一定是无解的。否则，考虑到 A 中一个点的父节点要在它之后被操作，B 中一个点的父节点要在它之前被操作，这样子就有若干个偏序关系，我们只需要拓扑排序...