首页 > 其他分享 >2024.2.20闲话——luogu5021随机选取边的正确性

2024.2.20闲话——luogu5021随机选取边的正确性

时间:2024-02-20 21:45:22浏览次数:30  
标签:局面 2024.2 20 从小 luogu5021 选取 正确性 匹配

推歌:生きる (feat. 可不)——水野あつ

这首歌听完之后接着转去咖喱乌冬了,歌词甚至能接上,没绷住。

刚刚写证明中间把 wxy 的杯子碰倒洒键盘上了,抢救键盘的过程中碰到缝就有水,有点涩。
但是这个键盘里面怎么这么脏啊?

下面来证 luogu5021 在菊花树中以任何顺序选取边并采取贪心策略的正确性。

从小的边来选取边并采取贪心策略的正确性证明

如果不是从小的边开始选取,那某边的匹配会出现三种情况。

  1. 匹配的边长度比较小,那么剩下的局面将不劣于从小的边开始选取的局面。
  2. 匹配的边长度不变,那么剩下的局面与从小的边开始选取的局面相同。
  3. 匹配的边长度比较大,说明比较小的边已经匹配完成,所以剩下的局面将不劣于从小的边开始选取的局面。

怎么感觉像是不大对的亚子。

标签:局面,2024.2,20,从小,luogu5021,选取,正确性,匹配
From: https://www.cnblogs.com/LiJoQiao/p/18024112

相关文章

  • luogu5021题解
    形式化题意:在一棵树上找\(m\)条没有重复边的路径,使得最短的路径最大,求这个最短路径的最大值。看到这个最大值就想二分答案。\(1\lem\len-1\),我们可以将长度的下限为最短的那条边,此时所有边都是符合要求的路径。长度的上限为所有路径的长度除以\(m\),向下取整。我们在判断......
  • 【闲话】2024.2.20
    年前yspm让我写闲话,我说文笔不好且没啥可写的,今天确实有很多想写一下的,看int_R等人今天都写闲话了,比较蠢蠢欲动。昨天莫名放电影了,四机房自然是从自己找若干电影中公投一个下载,这次的选择范围是整个豆瓣TOP250!最终《看不见的客人》在《幸福终点站》《被解救的姜戈》《小丑......
  • 2024.2.20 横渡海峡 年轻的人
    数学很难。头一次感觉非常罚坐,但是细细思考还是很有收获的。ARC172F需要尝试对操作找出一个优秀的描述。手玩一下操作,偷一张题解的图:仅看这一段,可以发现我们的操作形如:插入一个字符,然后删除一个字符。做到这里已经是提高组题目了,令\(f_{i,j}\)表示\(S\)匹配到\(i\),\(T......
  • log4cplus在VS2022使用
    在VS2022使用vcpkg编译的log4cplus遇到以下错误:21:08:14:646 1>player.lib(player_manager.obj):errorLNK2001:无法解析的外部符号"void__cdecllog4cplus::detail::macro_forced_log(classlog4cplus::Loggerconst&,int,classstd::basic_string<wchar_t,structstd::ch......
  • 2024.2.20 近期练习
    P4766不难发现时间的先后顺序是不重要的。所以把时间转化到数轴上。数据范围提示区间dp,设\(f_{l,r}\)表示\([l,r]\)时间里面全部消除的代价。\(f_{l,r}=\max(f_{l,k}+f_{k,r}+d_{l,k,r})\),其中\(d_{l,k,r}\)表示跨越\(k\)的,且在\([l,r]\)里最远的距离。然而\(d\)......
  • #15 2024.2.19
    604.xsy5339怎么有人(why)605.xsy5340NOIP(noip)得到的结论是,动态凸包水太深,别碰,你把握不住。叉随机化叉了一万年,然后发现std是假的。遇到这种题来个猫树分治得了。傻逼。大粪模拟赛/tuu。606.qoj8224CaughtintheMiddle607.qoj1071The2022ICPCAsiaHan......
  • UESTC 2024 寒假集训 - Day4
    Preface万恶的psk搬的全是Atcoder上的题目,然后理所当然的后面题目全是CountingProblem了作为计数苦手直接当场暴毙,3h写完前面的8个题然后直接跑路AtCoderarc148_amodM开场差点被签到腐乳了,没发现答案不是\(1\)就是\(2\)直接傻掉了由于\(M=2\)时答案至多为\(2\),因此只需......
  • 闲话2.20
    又是听不懂的一天......
  • 2024年2月20号题解
    P5594【XR-4】模拟赛解题思路重点是怎么判断是不是同一套模拟题用一个数组来标记是不是同一套题代码实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<time.h>#include<stdbool.h>#defi......
  • 2.20 鲜花
    【数据删除】被收了,原因:大义灭亲开状压了但是讲解视频的模糊程度和二十年前的电视剧不相上下\(B\)互不侵犯状压模板状态转移方程为$dp_{i,j,k}=\sum\limits_{x=1}^{cnt}dp_{i-1,x,k-sta_j}$,其中(sit[j]&sit_[x]==0)&&((sit[j]<<1)&sit[x]==0)&&(sit_[j]&(sit[x]}<<1)==0......