CF2062E1 The Game (Easy Version) 题解

发表于2025-02-12|更新于2025-03-23

|浏览量:

如果存在 $u$ 不在 $v$ 的子树内且 $w_u>w_v$ ，则最大的 $v$ 一定是可行的点。

此时，选择了这个点后，对方将无法选出一个点使得消除后剩下的点大于选择的点，因此可行。如果选择不出这样一个点，则无解。

首先想到枚举 $v$ ，并要求在 $O(\log n)$ 时间内完成判断。看到这个时间复杂度以及最大值，我想到的是线段树（BIT 也可以的）。

为了实现查询，要想办法使得区间连续，为了实现这个目标，可以使用 DFS 序，令其为 $dfn$ ，这时查询的最大值可以分成 $dfn$ 中的两段，前一段是 $[1,dfn_v]$ ，为了描述后一段，定义当前节点 $v$ 的子树中 $dfn$ 最大的点的下一个点为 $nxt_v$ ，于是第二段为 $[nxt_v,n]$ ， $nxt$ 的求法可以在 DFS 中完成，详见代码。

提示：注意可能取到空区间，线段树中注意判断！

文章作者: shicj

文章链接: https://shicj.pages.dev/2025/02/12/CF2062E1%20The%20Game%20(Easy%20Version)%20%E9%A2%98%E8%A7%A3/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 shicj's blog！

相关推荐

CF1185E Polycarp and Snakes 题解

CF1481D AB Graph 题解

分类讨论。【111】当 mmm 是奇数时，构造 $ \text{abababab} \cdots$ 的串即可满足题意，于是直接交替输出 111 和 222 凑足 m+1m+1m+1 个即可。【222】当 mmm 是偶数时：【2.12.12.1】存在一个点对，来回字母一样，如下图：这时显然和【111】相同处理即可。【2.22.22.2】存在三个点，路径上字母相同，如下图：这时构造一个 ⋯1→2→1→2→3→2→3⋯\cdots 1\rightarrow2\rightarrow\boxed{1\rightarrow2\rightarrow3}\rightarrow2\rightarrow3\cdots⋯1→2→1→2→3→2→3⋯...

CF1487E Cheap Dinner 题解

提供一种简单的线段树写法。首先，给出朴素的 DP，令 dpi,jdp_{i,j}dpi,j 表示前 iii 种食物，第 iii 种选择了 jjj 的最小花费，显然得出转移： dpi,j=min⁡(j,k) is OKdpi−1,k+ci,jdp_{i,j}=\min\limits_{\text{(j,k)\ is\ OK}}dp_{i-1,k}+c_{i,j} dpi,j=(j,k) is OKmindpi−1,k+ci,j 边界： dp1,i=c1,idp_{1,i}=c_{1,i} dp1,i=c1,i 接下来将取最小值的枚举优化，一种简单的想法是，以 dpi−1dp_{i-1}dpi−1 建立线段树，每次枚举 kkk 时，将所有不符合条件的数字设置为正无穷，处理完这个 jjj 之后再将修改复原，这样的均摊时间复杂度为 O(nlog⁡n)O(n\log...

CF1638D Big Brush 题解

正难则反，倒序操作，操作的一定是四个同色格子（或者其中有已经完成操作的点，其他同色），可以从此入手进行 DFS。遍历每一个点，对其进行 DFS，首先检查是否已经完成处理（被标记为 000）、越界或者不符合条件（有杂颜色），如果没有问题，标记这四个格子（改为 000），对其四周的格子进行搜索，具体的，分别是以下 888 个点： 1234dfs(x-1,y);dfs(x-1,y+1);dfs(x+2,y);dfs(x+2,y+1);dfs(x,y-1);dfs(x+1,y-1);dfs(x,y+2);dfs(x+1,y+2); 于是给出代码，注意倒序输出： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include<bits/stdc++.h>using namespace std;int n,m;int...

CF1916F Group Division 题解

upd 2024.11.20 “（否则选出这个点后 S2S_2S2 就不连通了）” S2S_2S2 改为 S1S_1S1 upd 2024.10.10 “且选出的点不是剩余点集 S2S_2S2 的割点” S2S_2S2 改为 S1S_1S1 题意给定一个无向图 GGG，点数为 n1+n2n_1+n_2n1+n2，边数为 mmm,保证 GGG 是一个点双连通分量且无重边。请将 GGG 划分为两个无交集的点集 S1S_1S1，S2S_2S2 满足 ∣S1∣=n1|S_1|=n_1∣S1∣=n1，∣S2∣=n2|S_2|=n_2∣S2∣=n2，且 S1S_1S1，S2S_2S2 的导出子图均连通。保证有解。思路因为 $ 1 \le n_1 , n_2 \le 2000 ，，， 1 \le m \le 5000 $ 所以可以考虑一个点一个点地选取和划分，每一次选取花费时间 O(log⁡m)O\left(\log\right.m)O(logm) 或更少。因此可以定义 S2S_2S2 为空集，所有点都在 S1S_1S1...

CF1970C2 Game on Tree (Medium) 题解

0x00 题目大意给出一棵树，在一个点上放一个棋子，两人轮流移动棋子到相邻位置，不可重复经过某个点，两人决策最优，问谁获胜。 0x01 初步分析看一下样例，画个图分析一下：然后看一下可以怎样移动：发现每一条路径都去往叶子节点，显而易见，每个叶子节点的状态是确定的：这个状态可以很快求出，接下来研究如何向上转移。 0x02 深入分析由于叶子节点状态已知，所以考虑自底向上分析。在这里，每一个节点上由谁选择（移到下一个点）很重要，我们用绿色字体标出每个节点上由谁选择：可以看出，由谁选择取决于节点的深度。易得，在最优决策中，总是要选择可以使得自己获胜的点，如果没有，则在这一点上出发对方获胜，否则自己获胜。于是可以自底向上标出每一个点上的获胜者：这时看一看起始节点上谁获胜就行了。 0x03 具体实现在代码中，可以如图中用字符表示状态（这样直观但代码量大），但更推荐用布尔值来实现，这样可以把判断获胜者的运算转化为深度模 222 和逻辑运算，具体的写法可以自己琢磨。求获胜者的步骤可以直接写在搜索的回溯部分，这样便于实现。 0x04...

评论