JOISC2020 部分题解
先放一点上来,剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP:设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A,最后一个是 A/B 是否可行,转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$,为真的 $j$ 一定是一段区间,因此我们只需要维护这段区间,即可去掉 $j$ ...
先放一点上来,剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP:设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A,最后一个是 A/B 是否可行,转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$,为真的 $j$ 一定是一段区间,因此我们只需要维护这段区间,即可去掉 $j$ ...
Codeforces Luogu 分析 我们把顶点黑白染色,那么一面镜子就可以看成是连接同色点的一条边。 接下来给出一个结论:一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。 (比较感性理解的)证明: 首先,当黑点连边确定时白点连边一定唯一确定,所以我们只考虑黑边确定的情况。 先证必要性: 先考虑后面那个限制。如果连成了环,则环内部的边一定没有光线会穿过,所以不能有环。 再考虑前...
官网 AtCoder LOJ 試験 / Examination 三维偏序板子,CDQ 即可。 代码 ビーバーの会合 / Meetings 首先有一个结论:Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。 我们先在 $[1,n)$ 中随机一个点 $y$,然后询问 $(0,y,z)$,即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
LOJ UOJ Luogu 分析 以端点的 $\min$ 为边权建一棵 Kruskal 重构树,以端点的 $\max$ 为边权建一棵 Kruskal 重构树。 那么我们在第一棵树上从 $s$ 向上跳到最浅的 $\geq l$ 的点,其子树就是人类状态下从起点出发能走到的点;在第二课树上从 $t$ 向上跳到最浅的 $\geq r$ 的点,其子树就是狼人状态下能走到终点的点。 那么我们只需要求这...
Codeforces Luogu 分析 我们把每个连通块看成一个点,然后用 Prufer 序列计数。那么方案数为 用并查集求出连通块个数及每个连通块的大小即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ============...
Codeforces Luogu 分析 显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内,所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。 显然每个强连通分量内成环最优,那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数,则应最小化后面那个东西,即把一些强连通分量在满足条件的情况下合并成一个大环。 因为点数 $...
AtCoder Luogu 分析 设 $c_i=\max\left\{0,a_i-b_i\right\}$,则相当于要求任意在 $u$ 点的时刻手中都有至少 $c_u$ 円。 然后可以发现两个结论: 每个点只会在最后一次访问时被捐赠。 $c_i$ 大的会优先捐赠。 那么我们大概是这样捐赠的:首先选一个点 $u$,假设删掉 $u$ 后形成了 $tot$ 个连通块,则先捐赠掉 $tot-1$...
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少,则 若 $X_i+1=X_j$,则 $dis_{i,j}=-1,dis_{j,i}=1$,连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$,则 $dis_{i,j}=0$,连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环,另一种情况是...
Luogu 分析 先考虑没有修改怎么用分块做。 一个想法是将序列分块,然后维护 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量,然而这样子查询是 $\mathcal{O}(n)$ 的。 因此我们再对值域分块,并再维护 $s'_{i,j}$ 表示前 $i$ 块中值在第 $j$ 块中的数的数量,询问时先把所求在值域的哪一块中求出来,再在这一块中求,复杂度 $\mathcal{O}(\s...
Luogu 分析 考虑分块。 对于每一块,维护它的最大值 $mx$。可以发现 $\sum mx$ 是 $\mathcal{O}(n\sqrt{n})$ 级别的,因此每一块如果能够 $\mathcal{O}(x)$ 修改的话复杂度就是 $\mathcal{O}(n\sqrt{n})$。可以想到这样的修改方式 如果 $2x\geq mx$,则直接将所有 $>x$ 的数减去 $mx$。这样...