- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
比赛链接 。
签到。发现如果要找两条路径的话,能找到的充要条件是存在一个点的上方和左方的字母相同。(即使两条走过的点截然不同的路径也符合,这时终点会成为这个点).
即存在一个位置 \((i,j)\) 使得 \(s_{i-1,j}=s_{i,j-1}\),我们称位置 \((i,j)\) 是好位置.
扩展到三条路发现,存在上面的两个好位置就可以了,但对这两个位置有要求:
或者 同一列上相邻 。
贪心,思路其实很简单,只不过不好实现.
发现尽量留下小的节点比较优,于是中序遍历,每到一个节点则求出若留下它则至少要留多少个点(设这个数量为 \(x\)),比较 \(x\) 与 \(k\),若 \(x<k\) 则这个点可以留下来,标记上.
考虑具体如何查询一个点留下来至少要留的点的个数.
对于查询:
发现若一颗 AVL 树的高度若是确定的,则它最少包含的节点数量可求:
可以预处理出来 \(f[i]\),表示深度为 i 的AVL树,节点数至少多大。有递推式 \(f[i]=f[i−1]+f[i−2]+1\),可以看作一边深度为 i−1,一边深度为 i−2,在上面接上了根节点.
那么查询求出一个点留下来,一直回溯它的祖先节点直到根,对于该节点是左儿子的情况计算出保留这个节点至少需要右子树中有多少个节点,即可转化成求右子树的最小高度.
我们维护每个点的 深度 \(dep\)、子树内最大深度 \(dmax\),dfs 预处理这两个信息即可.
还要维护每个点为根的 子树中已选点的最大深度 \(had\),和若留下该点至少需要的深度 \(ned\).
这样询问所需点的个数就好说了,在询问点不断跳父亲回溯的过程中,当跳到的点是左儿子时,求出保留这个点,它父节点的右儿子最小高度.
具体看代码,那么现在我们还需要实时更新这些信息.
考虑更新:
每个点被选后都要不断回溯祖先节点至根节点来更新它所有祖先节点的已选子树的最大深度; 。
并且回溯过程中,该点为左儿子时需要更新父节点的右儿子留下来需要的最大深度,(为了保证满足 AVL 树的要求,即两儿子子树的高度差值不超过 1) 。
而该点为右儿子时则不用管父节点的左儿子,因为左儿子一定被我们优先考虑过是否可留下,右儿子在左儿子之后遍历到,不对左儿子有影响.
由于 AVL 树的性质,高度约为 \(\log n\),所以整体复杂度为 \(O(n\log n)\).
具体还有很详细的代码注释:
#include<bits/stdc++.h>
#define mp make_pair
#define Type int
#define qr(x) x=read()
typedef __int128 INT;
typedef long long ll;
using namespace std;
inline Type read(){
char c=getchar(); Type x=0, f=1;
while(!isdigit(c)) (c=='-'?f=-1:f=1), c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48), c=getchar();
return x*f;
}
const int N = 5e5 + 5;
int n, k, root, whi[N];
int son[N][2], fa[N], f[N];
int dep[N], dmax[N];
inline void dfs(int x, int p){ dfs 预处理
dmax[x] = dep[x] = dep[p] + 1;
for(int i=0; i<2; i++){
int y = son[x][i];
if(!y) continue;
dfs(y, x);
dmax[x] = max(dmax[x], dmax[y]);
}
}
int ned[N], had[N], vis[N];
inline int query(int u){
int y = u, x = fa[u], res = 0;
while(x != -1){
if(!whi[y]) res += f[max({had[x]-1, dep[u]-1, ned[son[x][1]]})-dep[x]];// 跳到点为左儿子时,加上右儿子的贡献
y = x, x = fa[x];
}
return res;
}
inline void update(int u){ //选了一个点,更新它对祖先节点的影响
had[u] = max(had[u], dep[u]);
int y = u, x = fa[u];
while(x != -1){
had[x] = max(had[x], dep[u]);//更新子树内已选的点的最大深度
if(!whi[y] and son[x][1]) ned[son[x][1]] = max(ned[son[x][1]], had[x] - 1); //该点是左儿子,更新若选右儿子需要的最大深度
y = x, x = fa[x];
}
}
inline void DFS(int x){
if(query(x) < k){
vis[x] = true;
k--; update(x);
}
if(son[x][0] and dmax[son[x][0]] >= ned[x]){ //左子树的最大深度达得到父节点需要的就选择左子树
ned[son[x][0]] = max(ned[son[x][0]], ned[x]);
if(son[x][1]) ned[son[x][1]] = max(ned[son[x][1]], ned[x] - 1);
}
else if(son[x][1]){ //否则选择右子树
ned[son[x][1]] = max(ned[son[x][1]], ned[x]);
if(son[x][0]) ned[son[x][0]] = max(ned[son[x][0]], ned[x] - 1);
}
for(int i=0; i<2; i++){
int y = son[x][i];
if(!y) continue;
DFS(y);
}
}
signed main(){ //avl
freopen("avl.in", "r", stdin), freopen("avl.out", "w", stdout);
qr(n), qr(k);
for(int i=1; i<=n; i++){
qr(fa[i]);
if(fa[i] == -1){root = i;continue;}
whi[i] = (i < fa[i] ? 0 : 1); //判断该点是其父节点的左子树还是右子树
son[fa[i]][whi[i]] = i;
}
if(k == 1){
for(int i=1; i<=n; i++)
cout<<(i == root ? 1 : 0);
return 0;
}
dfs(root, 0);
f[1] = 1;
for(int i=2; i<=30; i++) f[i] = f[i-1] + f[i-2] + 1; //递推求深度为 i 的 AVL 树的最少节点数
DFS(root);
for(int i=1; i<=n; i++)
cout<<vis[i];
cout<<'\n';
return 0;
}
最后此篇关于「模拟赛」CSP-S模拟11(T2超详细)的文章就讲到这里了,如果你想了解更多关于「模拟赛」CSP-S模拟11(T2超详细)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
这个问题在这里已经有了答案: Why don't Java's +=, -=, *=, /= compound assignment operators require casting? (11 个
我搜索了很多,但没有一个链接能帮助我解决这个问题。我得到了 ORA-21500: internal error code, arguments: [%s], [%s], [%s], [%s], [%s
我正在做 RegexOne 正则表达式教程,它有一个 question关于编写正则表达式以删除不必要的空格。 教程中提供的解决方案是 We can just skip all the starting
([\s\S]+|\s?) 中 |\s? 的目的或作用是什么?如果没有它,表达式会不会与 ([\s\S]+) 相同? 最佳答案 这不是完全相同的。 ([\s\S]+|\s?) 会匹配空字符串,而 ([
这个正则表达式有一组还是两组? 我正在尝试使用第二组访问 bookTitle 但出现错误: Pattern pattern = Pattern.compile("^\\s*(.*?)\\s+-\\s+
在 C 中给定一个字符串指针 s,下面的迭代会做什么?即它以什么方式遍历字符串? for (++s ; *s; ++s); 最佳答案 for (++s ; *s;++s) 表示 将指针 s 递增到字符
我正在用一个 node.js 应用程序解析一个大列表并有这段代码 sizeCode = dbfr.CN_DESC.split('\s+-\s*|\s*-\s+') 这似乎不起作用,因为它返回了 [ '
我正在编写一个简单的字符串连接程序。 该程序按照我发布的方式运行。但是,我首先使用以下代码编写它来查找字符串的结尾: while (*s++) ; 但是,这个方法并没有奏效。我传递给它的字符串
这个问题已经有答案了: What does (?和aramchand来自Mohandas Karamchand G 因此,在使用这些匹配来分割字符串后,您最终会得到 {"M", "K", "G"} 注
我正在尝试转换 Map到 List使用 lambda。 本质上,我想将键和值与 '=' 连接起来之间。这看起来微不足道,但我找不到如何去做。 例如 Map map = new HashMap<>();
我正在经历 K & R,并且在递增指针时遇到困难。练习 5.3(第 107 页)要求您使用指针编写一个 strcat 函数。 在伪代码中,该函数执行以下操作: 将 2 个字符串作为输入。 找到字符串
在下面的代码中,pS 和 s.pS 在最后一行是否保证相等?也就是说,在语句S s = S();中,是否可以确定不会构造一个临时的S? #include using namespace std; s
演示示例代码: public void ReverseString(char[] s) { for(int i = 0, j = s.Length-1; i < j; i++, j--){
我一直在寻找类似于 .NET examples 中的示例的 PowerShell 脚本.取一个 New-TimeSpan 并显示为 1 天 2 小时 3 分钟 4 秒。排除其零的地方,在需要的地方添加
def func(s): s = s + " is corrected" return s string_list = ["She", "He"] for s in string_li
我是 python 的新手。当我在互联网上搜索 lambda 时。我在 lambda_functions 中找到了这个声明. processFunc = collapse and (lambda s:
我最近开始学习正则表达式,并试图为上面的问题写一个正则表达式。如果限制只放在一个字母上(例如不超过 2 个“b”),这并不困难。 那么答案就是:a* c*(b|ε)a* c*(b|ε)a* c* 但是
当我运行 npm install 时出现以下错误,但我无法修复它。 我试过:npm install -g windows-build-tools 也没有修复这个错误 ERR! configure
有很多有趣的haskell网上可以找到片段。 This post可以在 this (awesome) Stack Overflow question 下找到. The author写道: discou
我知道以下三行代码旨在将字符串提取到$ value中并将其存储在$ header中。但是我不知道$value =~ s/^\s+//;和$value =~ s/\s+$//;之间有什么区别。 $val
我是一名优秀的程序员,十分优秀!