CodeforcesLuogu分析我们把顶点黑白染色,那么一面镜子就可以看成是连接同色点的一条边。接下来给出一个结论:一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。(比较感性理解的)证明:首先,当黑点连边确定时白点连边一定唯一确定,所以我们只考虑黑边确定的情况。先证必要性:先考虑后面那个限制。如果连成了环,则环内部的边一定没有光线会穿过,所以不能有环。再考虑前面那个限制。我们需要...
官网AtCoderLOJ試験 / Examination三维偏序板子,CDQ 即可。代码ビーバーの会合 / Meetings首先有一个结论:Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。我们先在 $[1,n)$ 中随机一个点 $y$,然后询问 $(0,y,z)$,即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。那么直接递归处理链上每个点剩下的子树...
LOJUOJLuogu分析以端点的 $\min$ 为边权建一棵 Kruskal 重构树,以端点的 $\max$ 为边权建一棵 Kruskal 重构树。那么我们在第一棵树上从 $s$ 向上跳到最浅的 $\geq l$ 的点,其子树就是人类状态下从起点出发能走到的点;在第二课树上从 $t$ 向上跳到最浅的 $\geq r$ 的点,其子树就是狼人状态下能走到终点的点。那么我们只需要求这两棵子树中的...
比赛地址白昼夢 / Daydream如果当前字母是 d 则依次匹配 dreameraser、dreamerase、dreamer、dream,如果当前字母是 e 则依次匹配 eraser、erase。不如直接倒着做代码連結 / Connectivity开两个并查集,然后开个 map 维护一下 [find1(i),find2(i)] 即可。代码へんなコンパス / Manhattan Compa...
CodeforcesLuogu分析我们把每个连通块看成一个点,然后用 Prufer 序列计数。那么方案数为用并查集求出连通块个数及每个连通块的大小即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ===================...
CodeforcesLuogu分析显然满足 $G_{i,j}=\mathsf{A}$ 的 $i,j$ 在同一个强连通分量内,所以先把这些点并起来。那么如果一个强连通分量内有 XOR 边就是不合法的。显然每个强连通分量内成环最优,那么答案等于 $n-1+$点数 $\geq 2$ 的强连通分量个数,则应最小化后面那个东西,即把一些强连通分量在满足条件的情况下合并成一个大环。因为点数 $\geq ...
AtCoderLuogu分析设 $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}(\sqrt{...
Luogu分析考虑分块。对于每一块,维护它的最大值 $mx$。可以发现 $\sum mx$ 是 $\mathcal{O}(n\sqrt{n})$ 级别的,因此每一块如果能够 $\mathcal{O}(x)$ 修改的话复杂度就是 $\mathcal{O}(n\sqrt{n})$。可以想到这样的修改方式如果 $2x\geq mx$,则直接将所有 $>x$ 的数减去 $mx$。这样子是 $\...