首页 > 其他分享 >2024.10.7 test

2024.10.7 test

时间:2024-10-07 15:45:04浏览次数:6  
标签:2024.10 区间 链上 深度 test 操作 节点 dp

nf #33

B

有一棵包含 \(n\) 个节点的有根树,且树的高度不超过 \(100\)。每次操作时可以选择一个节点 \(u\),使其与父节点断开(如果有),成为一颗新树的根节点,然后删除以节点 \(u\) 为根的树中的所有叶节点。
求删除所有节点所需的最少操作次数和通过最少次操作删除所有节点的方案数。\(n\le 2e5\)。

显然,操作次数最少为树的深度,只需要不停操作根节点即可满足。
其次,我们能删除的点,一定满足在这棵树内不存在与其深度相同的点,所以一定在最长链上。
那么我们考虑把最长链拿出来 dp,且其长度是 \(\le 100\) 的。
对于链上每个点,求出 \(a_i\) 表示链外儿子最大的深度,其制约着我们的选择。
不难发现,我们可以把子任务划分为区间的形式,也就是当前分割出深度 \([l,r]\) 的点的方案数。
我们每次操作,相当于把当前所在区间割裂,然后使深度大的区间里的 \(a_i\) 全部减去 \(1\)。
操作的条件是对于深度小的点里,\(a_i\) 最大值小于当前操作深度。
所以我们还需要再加一维状态表示当前整个区间被深度小的点减了多少次,设为 \(t\)。
那么,\(dp_{l,r,t}\) 可以由 \(dp_{l,p,t}\) 和 \(dp_{p+1,r,t+1}\) 转移,转移系数需要乘上组合数,因为两两区间独立。
其中枚举的 \(p\) 需要满足上述操作条件。复杂度 \(O(d^4)\)。
这个题你需要观察出选择的点都在最长链上的性质,然后转化为一个简单的 dp。

标签:2024.10,区间,链上,深度,test,操作,节点,dp
From: https://www.cnblogs.com/Simon-Gao/p/18450167

相关文章

  • AtCoder Beginner Contest 374
    ABC374A-Takahashisan2题目传送门代码(签到题)#include<cstdio>#include<cctype>#include<cstring>#include<cmath>#include<queue>usingnamespacestd;intiut(){ intans=0,f=1;charc=getchar(); while(!isdigit(c))f=(c==&......
  • test
    测试代码高亮:<head><metacharset="<?phpechoget_bloginfo('charset');?>"><metaname="viewport"content="width=device-width,initial-scale=1.0"><metahttp-equiv="X-UA-Compat......
  • The 10th Shandong Provincial Collegiate Programming Contest
    A-Sekiro题意初始有\(n\)个金币,死了\(m\)次,死一次\(n=\lceil\fracn2\rceil\)。求最后的金币数。思路模拟。代码点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ intn,m; cin>>n>>m; while(m--......
  • 2024.10.6训练记录
    下午cfA到!B签到题,考场还是写挂了,今天码力差。挂在while动指针的时候没有判右边界,似。唐诗程度不亚于数组开小。C1猜出来结论是第一次出现需要按照一开始的顺序就能过。C2把一开始的排列映射到[1,n]。修改时用set动态维护每个数第一次出现的位置。把第一次出现位置的......
  • 2024.10 做题记录 /
    CF2004E套用SG函数的结论,我们先打单个游戏的表再异或即可得到答案。首先对于一个大小为\(i\)的堆有\(SG[i]=\text{mex}_{j\boti}\{SG[i-j]\}\),容易暴力dp。intSG[N];intf(intx){ if(SG[x]!=-1)returnSG[x]; if(x==0)returnSG[0]=0; vector<int>g; up(i,1,x......
  • AtCoder Beginner Contest 374
    省流版A.判断末三位即可B.逐位判断即可C.枚举所有分组情况即可D.枚举线段顺序、端点顺序即可E.二分答案,发现贵的机器数量不超过\(100\),枚举求最小花费看是否可行即可F.朴素DP,复杂度分析得到有效时刻不超过\(O(n^2)\)而非\(O(s_i)\),直接\(DP\)即可A-Takahashi......
  • 团队训练记录2024.10.5
    这次double精度上卡了,赛时和学校强队差两题题目链接:https://codeforces.com/gym/104023/problemA.Dunai队友写的,答案在总冠军位人数和位置上冠军加非冠军人数最小取min?#include<bits/stdc++.h>#definetest(i)cout<<#i<<""<<i<<""<<endl;#defin......
  • 2024.10.1 近期练习
    CF1993F2Dyn-scriptedRobot(HardVersion)这个题非常的一眼,首先翻转路径的操作可以转化为翻转矩形。也就是,如果触碰了边界不改变行走的路径,而是继续走下去,只不过对应的位置需要对称回去。那么,计算走到\((0,0)\)的次数,也就是在反转后的坐标系里的\((2k_1w,2k_2h)\)的位置......
  • 2024.10.5 LGJ Round
    A给定\(n\)个区间,你要选出最多区间对数,使得每一对的区间都不交。\(n\le4e5\)。反悔贪心,我们将所有区间按\(l_i\)从小到大排序,一个一个加入,加入的时候有两种情况。1.之前的区间中存在未匹配的区间,且可以跟当前区间匹配。我们随便选择一个区间跟当前区间匹配即可。2.找不到......
  • 2024.10.5 LGJ Round
    A给定\(n\)个区间,你要选出最多区间对数,使得每一对的区间都不交。\(n\le4e5\)。反悔贪心,我们将所有区间按\(l_i\)从小到大排序,一个一个加入,加入的时候有两种情况。1.之前的区间中存在未匹配的区间,且可以跟当前区间匹配。我们随便选择一个区间跟当前区间匹配即可。2.找不到......