2020-04-04 21:45 已编辑山东大学计算机类

关注

【题解】牛客OI周赛15-提高组

环球旅行

题意就是给出一棵带边权的树。删除上面的一条边，使分成的两棵树中较大的直径尽量小。求该直径。

【20分做法】

枚举删除哪条边，计算直径。复杂度 $O(n^2)$

【30分做法】

对于菊花图，删除最长边即可。

【40分做法】

对于一条链， $O(n)$ 枚举删边，可以直接算出剩下两条链的直径。

【60分做法】

对于 $n\le10^5$ 且数据随机的部分，答案肯定是删除直径上的某条边。随机数据树的直径不会很长，所以只枚举删除直径上的边。计算剩下的最长直径即可。

【100分做法】

将直径扯平。从左向右依次计算删除上面某条边后左边子树的直径。
图片说明
如图，删除红色边之后，左边子树的直径就是max(删除蓝色边时的答案，经过x但不经过y的最长链+蓝色边长度+y子树中与y相连的最长链长度)。
用同样的方法从右往左依次计算删除某条边后右边子树的直径。然后就可以统计出删除每条边之后的代价。
我们直接分别以直径的两个端点为根，用树形dp的方法求出每棵子树的直径。最后统计一遍答案即可。

恢复数列

【30分做法】

爆搜

【50分做法】

出题人也不知道怎么写233，但是鉴于这是OI赛制，就留给选手发挥吧。

【100分做法】

首先有一个结论：原题有解的充要条件是 $(x-1)|(n-2)$ 。这个的证明放到后面。
题目保证有解，所以全部数据都是满足这个性质的。
设 $n-2=k(x-1)$ 。
有一种可行的构造方法是让 $a_1=$ k。然后在 $a_2,a_3···,a_n$ 中，取 $x$ 个为 $0$ , $x-1$ 个为 $1$ , $x-1$ 个为 $2···x-1$ 个为 $k-1$ 。
这样左侧就是 $x+(x-1)(x^1+x^2+···+x^{k-1} )=x+(x-1)×\frac{x(x^{k-1}-1)}{x-1}=x^k$
恰好等于右侧。
关于上方结论的证明：
对原式两边 $mod(x-1)$ ，得到一个必要条件为 $1^{a_1}≡\sum\limits_{i=2}^n1^{a_i}(mod~ x-1)$
即 $1≡n-1(mod~x-1)⇒n-2≡0(mod ~x-1)⇒(x-1)|(n-2)$
再加上上方的构造方法，可以得出 $(x-1)|(n-2)$ 是原式有解的充要条件。

回到过去

$n$ 个物品，想要权值和为 $m$ 。当哪些种类的物品不选时，一定不能使权值和为 $m$ 。

【20分做法】

爆搜。

【40分做法】

f[i][j][k]表示前i个物品权值和为j，不选择第k种，是否可行。转移即可。
复杂度 $O(n^2 m)$

【60分做法】

对于每种时光胶囊只有一个的情况， $f[i][j]$ 表示前i个物品权值和为j是否可行。 $g[i][j]$ 表示后 $i$ 个物品权值和为 $j$ 是否可行。枚举不选的种类。然后将 $f$ 数组和 $g$ 数组合并一下即可。

【100分做法】

注意到不同种类的胶囊权值之和不超过 $10^5$ 所以胶囊的种类不超过450种，然后用和上面类似的方法二进制优化分组背包dp一下。复杂度 $O(\sqrt{n}log\sqrt{n}m)$ 。仍然过不去。发现dp值只有0和1。Bitset优化一下即可。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43362152

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43362161

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43362163

全部评论

推荐最新楼层

C++

分治不需要bitset优化/cy

1

送花回复

发布于 2020-04-04 22:37

全栈开发

T3 另一种思路 f(i)表示权值和为i的方案数(两种方案不同当且仅当至少有一种权值的物品选取数量不同),这步需要O(m√m). 然后可以O(m/a)求出去掉权值为a的物品时的f(m).这步需要O(mlogm).

1

送花回复

发布于 2020-04-04 23:22

秋招专场

校招火热招聘中

官网直投

C++

那个T2,假设左直径点R1,右直径点R2。那么R1到x的距离>=x的子树的最长链吧。

点赞

送花回复

发布于 2020-04-04 22:06

华中农业大学自动化类

所以第一题的意思是先算出每个子树的直径，然后枚举总直径上的每一个边？

点赞

送花回复

发布于 2020-04-04 22:07

祖龙娱乐_navi_ue4客户端开发工程师

第三题可以解释一下题解代码这段什么意思吗 for(int j = 1;j <= tmp;tmp -= j,j <<= 1,k <<= 1) f[i] |= f[i] << k; f[i] |= f[i] << (a[i] * tmp);

点赞

送花回复

发布于 2020-04-05 00:01

05-27 11:44

已编辑

华为_高级工程师

【急招】华为视频会议部门急招实习生

【我们是谁】视讯与协作行业领导者，领跑中国市场，连续八年市场份额第一，去年利润增长60%+，现业务发展，急招多名实习生，有转正名额招聘岗位：通用软件工程师、音频算法工程师 【岗位职责】投入视频会议领域音频、AI等算法、软件等创新技术的预研、算法开发及技术原型设计，助力技术点实际落地到具体的业务场景，构筑产品竞争力！ 【岗位要求】1、了解机器学习、深度学习、信号处理等一个或多个技术领域; 2、计算机、软件或者电子通信等相关专业; 3、熟悉C/C++/JAVA/Python至少一种开发语言，熟悉Linux操作系统;4、985、211本科或以上学历5、实习时间3个月以上（重点）【实习地点】东莞（首选...

投递华为等公司10个岗位 >

点赞评论收藏

转发

05-29 21:21

测试工程师

孤独的自学

依旧稀里糊涂的混日子本身高考成绩垃圾，不想上大学勉强挨到大学，一堆打游戏的，睡觉都睡不着猪都知道，LOL的程序员自己根本不玩这个在鸡群呆久了，🦅也只会跑忍了一学期，最后忍出幻听，休学在家细细翻了程序员从业资格管理者都是NOIP或CCF,要求10年经验该行业技术更新快，要求自学能力强开发需求是什么，没人清晰告诉我官方平台老推荐Google，可是谁把Google墙了Git-hub也登陆不了一些网站用过几次也莫名其妙无法访问免费版AI容斥原理计算错误家里人只会吐口水，扔垃圾，天天还要我帮忙用手机，又不是老年人跟着一群混吃等死，杂乱无章的人在一起混只能乱七八糟的草率一生孤独的在脏水里游，何处是岸

点赞评论收藏

转发

我要当架构师

05-26 08:51

University of California Irvine 计算机类

首次公开简历，望锐评！

#简历#先说一说我自己的想法，很多人都很排斥苍穹外卖，认为没什么技术点和含金量，但实际上我觉得恰恰相反，苍穹外卖虽然代码本身并不是你自身能力的证明，但是是作为一个新人学习时很好的跳板和原始框架，在这个框架上进行的改进可以很好的辐射到你自己的个人成果上，并作为你和面试官聊天的筹码大多数人的苍穹外卖只写增删改查，千篇一律，吸引不了面试官，所以这才让大家误以为只要是苍穹外卖就不要写进简历里这种误区，但实际上如果你在原有的层面上进行改进，并作为你的项目亮点和面试官介绍，告诉他你的苍穹外卖和别人的有什么不同，增加了哪些技术难点，这才显得你是完全自己理解了这个项目，并且有自己动手实践项目的能力，而不是就看了个课程就以为自己会了，就当成自己的了，如此一来，这反而成为你的加分项苍穹外卖为什么看的人最多，说明它好啊，如果它不好，为什么看的人还这么多，想清楚这个逻辑，我觉得要做的最重要的事，就是如何在原有框架上进行改进提效，比起听其他人的话重新搞一个项目性价比高得多，而且我亲测项目并没有成为我找到工作的阻碍，我投的大厂一大半都给我面试了，而且很多不止一个部门，退一万步说，当你手头没有其他项目的时候，有苍穹外卖总比什么都没有的好很多，不需要因为苍穹外卖有任何心理负担关于简历的任何部分都欢迎大家提意见，十分感谢大家，祝大家找实习+秋招顺利上岸，offer拿到手软#简历中的项目经历要怎么写##我的上岸简历长这样##最后再改一次简历##简历##简历被挂麻了，求建议#

简历中的项目经历要怎么写我的上岸简历长这样

点赞评论收藏

转发

昨天 18:05

已编辑

前端工程师

前端开发求职-一个延毕双非厦门某渣硕--0offer求救帖

个人背景：里扣刷了几十道题，前端开发，延毕半年，今年春季毕业的双非渣硕计算机，本科嵌入式，现在转码找工作.......前端开发，做过一个demo，现在正在补一个项目后台管理系统，无实习经验cvte今天前端一面，hr面，聊天切入1：你这是在学校吗，我说是延毕的，问了为什么，解答一下因为不让送审因为没有小论文发表。。。。。背景：目前有收获offer吗？我诚实的说还没有，还在等待offer，0offer还在等待面试通知。。。。。问题1：说说你项目最深刻的映象？答复：根据一个教程结合宿舍选房做了一个，感觉xxxA/B/c/d/e/fxxx个技术细节看教程的时候是一个样，但是自己写从拿数据到展示这个界面...

查看2道真题和解析牛客解忧铺

点赞评论收藏

转发

1 收藏评论

全站热榜

正在热议

# 和牛牛一起刷题打卡 #

9369次浏览 818人参与

# 机械制造薪资爆料 #

347889次浏览 4099人参与

# 牛客帮帮团来啦！有问必答 #

1054418次浏览 15973人参与

# 通信硬件薪资爆料 #

250208次浏览 2359人参与

# 面试中，你被问过哪些奇葩问题？ #

19243次浏览 149人参与

# 你收到了团子的OC了吗 #

524915次浏览 6235人参与

# 毕业租房也有小确幸 #

38220次浏览 3141人参与

# 你怎么评价今年的春招？ #

9228次浏览 159人参与

# 提前批和秋招有什么区别 #

28807次浏览 695人参与

# 我想象的工作vs实际工作 #

104095次浏览 1681人参与

# 晒一晒我的offer #

3723596次浏览 57513人参与

# 春招你拿到offer了吗 #

397700次浏览 5744人参与

# 秋招开了，你想投哪些公司呢 #

132306次浏览 3423人参与

# 实习生应该准时下班吗 #

88167次浏览 649人参与

# 来选选带哪个offer回家过年 #

191571次浏览 1836人参与

# 你的秋招进行到哪一步了 #

392543次浏览 6640人参与

# 腾讯工作体验 #

151114次浏览 1475人参与

# 百度工作体验 #

28520次浏览 286人参与

# 如何写一份好简历 #

309003次浏览 4408人参与

# 担心入职之后被发现很菜怎么办 #

37231次浏览 311人参与

牛客网
牛客企业服务