首页 > 其他分享 >2024.9.20 近期练习

2024.9.20 近期练习

时间:2024-09-22 21:03:03浏览次数:7  
标签:cnt 路径 20 2024.9 练习 考虑 节点 dp dis

CF461E Appleman and a Game

我们可以先建出 SAM,设 \(dp_{i,u}\) 表示当前处理到 \(i\) 位,SAM 上到 \(u\) 节点当前最小答案。
由于答案具有单调性,考虑二分答案,也就是二分 \(mid\),考虑如何检验最短的串是否不超过 \(\le n\)。
考虑把 SAM 修改一下,若某点不存在 \(c\) 的出边就将其连向根到 \(c\) 的节点。
现在问题转化为:给你一张有向图(即修改完的 SAM),满足上面有 \(4\) 个特殊点。
你从根开始走,每经过一条边则 \(cnt_1\) 加一,每到达一个特殊点则 \(cnt_2\) 加一。
当 \(cnt_2\) 为 \(mid\) 时过程终止。 你可以任意安排你走的路径,需要求出终止时 \(cnt_1\) 的最小值。
那么我们可以 dp,设 \(dp_{i,c}\) 表示当前走了 \(cnt_2=i\),走到了第 \(c\) 个特殊点的最小答案。
考虑最短路求出特殊点之间的最小的 \(cnt_2\)。最后 dp 明显可以用矩阵快速幂优化。非常好一个题。
之所以想到可以二分答案是因为“最小值最大”;还有随着 \(n\) 增大答案不降,所以答案增大,\(n\) 也不降。
可以二分转倍增优化复杂度。

CF1442E Black, White and Grey Tree

发现颜色相同且相邻的点可以缩点起来,一定是一起被操作的。
我们假设只有一条链,且只有黑色和白色的点,发现最小的操作次数为 \(len/2+1\),\(/2\) 需要向上取整。
把链推广到树上,贪心地,考虑每次删掉叶子节点,因为如果删成了多个连通块一定不优。
如果只有黑色和白色的点,把颜色不同的点之间的边设为 \(0/1\),那么 \(len\) 就是树的直径。
考虑灰色的点,由于灰色的点一定是跟白色或黑色一起删掉,所以可以把灰色的点看做是黑色或白色。
那么我们考虑树形 dp 即可。转移的话对于儿子合并上来的时候取儿子两种颜色最小值。
这个题的话,是一个从链到树的直径跟贪心的结合。每次删叶子的思想比较常见。

CF2004F Make a Palindrome

我们先要考虑一个数组最小操作多少次使得其变成回文。首先上限是 \(n-1\),只需要全部合并。
经过猜测,我们认定将一个数分裂成两份是没有用的,所以我们考虑最大化最后剩下的数的个数。
结论:所以一个数组考虑做前缀/后缀和,最后能剩下的个数,是前缀和与后缀和所有数中相等的个数。考虑拆贡献,也就是求区间和相等对数。把所有区间的和存进桶里,桶里两两可以做贡献。

CF1687D Cute number

我们观察到,合法的段是诸如 \([w^2,w^2+w]\) 这种情况。合法与不合法交替,长度为 \(2,1,3,2,4,3,5,4...\)
称 \([w^2,w^2+w]\) 为第 \(w\) 段,到第 \(V=a_n\) 段后,所有的数一定在一个段里。
不妨枚举 \(a_1+k\) 所在的段,只有 \(V\) 种段。我们令 \(a_1+k\) 紧贴左边,算后面要合法会使 \(k\) 增大多少。
因为合法的段长度最多比后面不合法的段长度大 \(1\),所以,每个 \(a_i+k\) 满足条件时 \(k\) 是一个区间。
然后把 \(k\) 的取值范围求交集,于是乎我们得到了一个 \(O(nV)\) 的做法。
观察到:如果当前从小到大枚举到第 \(w\) 段,若 \(a_{i+1}-a_i\le w\),那么他们一定在一个段中。
在一个段中的我们可以合并他们。考虑两个端点即可。
枚举到第 \(w\) 段时,在不同段的只有 \(\frac{V}{w}\) 种,复杂度调和级数。

CF1984E Shuffle

考虑转化题意,考虑最后流程结束时树被删成什么样。显然此时每个连通块大小为 \(1\)。
因为这些连通块大小为 \(1\),他们一定是叶子节点。这些没被删的点相当于一个独立集。
相当于求树的最大独立集。但是这样有一个问题,就是被删的点不一定不是叶子。
如果一个原来的叶子是第一个被删除的,那么其最后一定还是叶子节点。
所以设计一个 \(dp_{u,0/1,0/1}\) 表示当前节点选/不选,其子树有无叶子第一个被删除的答案,转移平凡。
转化为独立集模型确实精妙。

CF627D Preorder Test

显然地,我们需要二分答案,考虑如何检验答案 \(mid\),考虑把 \(< mid\) 的点都删掉,形成若干连通块。
在每个连通块中可能有若干个点连向 \(<mid\) 的点,这代表什么?代表这个点无法回溯,称为黑点。
如果走进一个无法回溯的点的子树里,那么一定会在该子树终结。
所以,我们 dfs 遍历的 \(k\) 个点中如果存在有黑点,其一定连成一条路径。
相当于我们选两个黑点出来,其路径上所有点的儿子的,且不存在黑点的子树大小的和使其 \(\ge k\)。
考虑 dp,维护 \(f_u\) 表示 \(u\) 连向其子树里某个点最大的贡献,(不考虑 \(u\) 子树外的贡献)。
特判不存在黑点的情况。

CF1976F Remove Bridges

我们要让割边最少,且原来树上不是割边的边连接成包含根节点的一个连通块。
我们连接 \(u\to v\) 时,可以使树上 \(u,v\) 路径上所有边都不是割边,此时可以将 \(u\to v\) 的边全部删去。
这是划分子任务的思想。我们有了一个贪心的策略,每次删除最长的一条路径,且与根节点联通的。
如果存在一个很长的路径 \(u\to O\to v\),需要先删 \(1\to O\) 才能到达;不妨先删除 \(1\to u\),再删 \(O\to v\)。
这证明了贪心是正确的。考虑如何表示一条路径,拆分成两条到 \(1\) 的路径,\(dis_u+dis_v\)。
当我们删了一条路径时,考虑对 \(dis\) 产生什么影响,这里需要把 \(dis_u\) 定义成删 \(u\) 会减少多少割边。
假设 \((x, fa_x)\) 是被删除的一条边且第一次被删,那么 \(x\) 子树里所有的 \(dis\) 都会减少 \(1\)。
由于每条边只会被删除一次,删除的时候直接执行子树减,同时维护出 \(dis\) 的最大值即可。
关于删除 \(u\to v\) ,需先找出 \(u\),然后设 \(u\) 向上跳 \(dis_u-1\) 的位置是 \(Q\),找非 \(Q\) 子树里最大的 \(v\) 即可。
经过实践发现上面是错的,我们需要给贪心加上“反悔”。
也就是,除了第一次操作,不需要找非 \(Q\) 子树里最大的 \(v\),因为可以通过交换使得其满足条件。

标签:cnt,路径,20,2024.9,练习,考虑,节点,dp,dis
From: https://www.cnblogs.com/Simon-Gao/p/18425845

相关文章

  • 小美的数组合并(美团20240427年暑期实习笔试真题)
    题目:小美的数组合并小美拿到了一个数组,她每次操作可以将两个相邻元素ai合并为一个元素,合并后的元素为原来两个元素之和。小美希望最终数组的最小值不小于k。她想知道有多少种不同的合并结果?输入描述第一行输入两个正整数n,k,代表数组大小和数组的最大值。第二行输入个正整数ai,......
  • 2024 CSP-S 游记
    CSP-S第一轮(初赛)摘自Shadow-Dragon9.20(day0)疯狂星期五,狂砍10节奥赛,直接爽了上午第二节到第五节都是奥赛,来机房以后发现网没开,消费股:看同学们初赛都准备得挺辛苦的,给你们安排一场模拟赛可能是觉得初赛太容易我们没人过不了遂安排了一场模拟赛,像是消费股能干出来的赛时......
  • c练习初学者初学者
    c语言输入成绩评等级  if(条件){  内容}elseif{   内容}else{    内容}1#include<stdio.h>2intmain(){34floatscore;5while(1){6printf("Pleaseenteryourscore:");7scanf("%f",&score);8if(score>=90&am......
  • [CVPR2024]DeiT-LT Distillation Strikes Back for Vision Transformer Training on L
    在长尾数据集上,本文引入强增强(文中也称为OOD)实现对DeiT的知识蒸馏的改进,实现尾部类分类性能的提升。动机ViT相较于CNN缺少归纳偏置,如局部性(一个像素与周围的区域关系更紧密)、平移不变性(图像的主体在图像的任意位置都应该一样重要)。因此需要大型数据集进行预训练。长尾数据学习......
  • CSP-S 2024 提高组初赛解析(更新至单项选择)
    单项选择1在Linux系统中,如果你想显示当前工作目录的路径,应该使用哪个命令?ApwdBcdClsDechopwd:printworkingdirectorycd:跳转到指定目录ls:列出当前目录的所有子文件和子文件夹echo:输出指定内容2假设一个长度为n的整数数组中每个元索值互不相同,且......
  • CSP-S 2024一轮邮寄
    目录2024/9/21SatDay1BeforeWhileAfter2024/9/21SatDay1Before早上起来感觉有点不舒服,但是没在意。没跑操,早读,吃饭,然后上whk。不过第五节课是体活,爽了。先去超市买东西,然后直奔食堂,发现已经吃不进去饭了。勉强吃完了米饭,然后回宿舍躺平。狠快人多了,开始打狼。大概是这......
  • [20240920]跟踪library cache lock library cache pin使用gdb.txt
    [20240920]跟踪librarycachelocklibrarycachepin使用gdb.txt--//前一阵子,写的使用gdb跟踪librarycachelocklibrarycachepin的脚本有一个小问题,无法获得lockaddress以及pinaddress--//地址,有一点点小缺陷,尝试修改完善看看。--//按照https://nenadnoveljic.com/blog/tr......
  • 2024睿抗机器人开发者大赛CAIP-编程技能赛-本科组(省赛) RC-u5 工作安排详解
    本文参考https://www.cnblogs.com/Kescholar/p/18306136这一题可能对高手来说就能轻而易举的看出是个01背包,但是对于我这种小白还是要经过详细的分析才可以理解。我们题目要求的是获得的最大报酬,题目的影响因素有三个:工作时长、工作截止时间、对应的报酬,那么怎么样合理的去......
  • 优秀的拆分(csp2020入门级1)
    一般来说,一个正整数可以拆分成若干个正整数的和。例如,1=1,10=1+2+3+4等。 对于正整数n的一种特定拆分,我们称它为“优秀的”,当且仅当在这种拆分下,n被分解为了若干个不同的2的正整数次幂。注意,一个数x能被表示成2的正整数次幂,当且仅当x能通过正整数个2相乘在一起得到。 例如,10......
  • [NOIP2013 提高组] 转圈游戏
    [NOIP2013提高组]转圈游戏\(n\)个小伙伴(编号从\(0\)到\(n-1\))围坐一圈玩游戏。按照顺时针方向给\(n\)个位置编号,从\(0\)到\(n-1\)。最初,第\(0\)号小伙伴在第\(0\)号位置,第\(1\)号小伙伴在第\(1\)号位置,……,依此类推。游戏规则如下:每一轮第\(0\)号位置上的小......