<span>noi前第十七场 题解</span>

##A. 黑白沙漠 考虑这样一个做法,对于每个点处理出左侧和右侧分别的最优决策点,然后比较二者谁更优即可。 当然这样的点可以表示为若干个区间,对于其中每个区间,左右侧谁更优是单调的,可以通过二分求解。

所以问题就是如何处理出这样的若干个区间。 可以想到这个最优决策点就是上凸包会切到的点。 所以写一个单调栈维护就好了。

  ##B. 荒野聚餐 学习了一下如何做线性规划对偶,大概可以这样做: 首先将对偶的式子化为标准型,最小化变量,约束条件为一些变量 \(\geq\) 常量,并且每个变量 \(\geq 0\)。 对每个约束条件设置一个对偶变量,对偶问题就是用这些对偶变量尽量去表示出一个下界,切到原来最小化的东西。 所以其对偶问题就是最大化对偶变量,满足每个对偶变量 \(\geq 0\),并且对偶变量满足在每个原变量上的系数和 \(\geq\) 原变量的该系数。

本题可以写为

\(\text{minimize}\ \sum \limits_{i=1}^n x_i+\sum \limits_{i=1}^ny_i+s\) \(\text{st}.\forall_{i,j}\ x_i+y_j+\frac{s}{c}\geq a_{i,j}\)

\(\forall_{i} x_i \geq 0,\forall_{i} y_i \geq 0,s \geq 0\)

对偶一下就是

\(\text{maximize}\ \sum \limits_{i,j}a_{i,j}d_{i,j}\) \(\text{st.}\forall_{i} \sum \limits_{j=1}^n d_{i,j} \leq 1\) \(\forall_{j} \sum \limits_{i=1}^n d_{i,j} \leq 1\) \(\sum \limits_{i,j}\frac{d_{i,j}}{c}\leq 1\)

将最后一个式子中的 \(c\) 乘到右面去,可以发现问题就是匹配个数 \(\leq c\) 的最大带权匹配。 所以写一个 SPFA 费用流,卡卡常就能通过了。

  ##C. 火星在住 因为可以用费用流去做,所以这个函数显然是凸的。 所以链分治然后写个类似闵可夫斯基和的东西合并答案就完事了。 具体来说,每次分治合并一条重链,对于上面每个点的轻边信息,通过另外一个分治来处理就好了。

全部评论

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:33
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务