NAIPC 2017补题

D

给定一棵 n ( n ≤ 2 e 5 ) n(n\le 2e5) n(n2e5)个点的有根树,每个点有点权,选出一些点,使得这些点的满足大根堆
的性质,求最多可以选多少点。

如果是一条链,就是求LIS,做法是维护一个单调队列。
树的话,其实也可以用单调队列,不过需要对不同儿子节点的队列进行合并。
可以考虑用multiset,进行启发式合并。

E

n ( n ≤ 2 e 5 ) n(n\le 2e5) n(n2e5)个点,其中 s s s个是特殊点。有 m ( m ≤ 5 e 5 ) m(m\le 5e5) m(m5e5)条候选边。需要求一棵最小生成树,使得恰好有 w w w条边是普通点和特殊点之间的。

其实就是边有两类,每一类选的边数固定,求最小生成树。
如果直接Kruskal,遇到一类边选满后跳过的话,是有问题的。
考虑带权二分,即把其中一类边统一加上一个权值,然后跑Kruskal,直到每一类选的边数恰好符合要求。
不需要每次都把边混在一起排序,可以用two-pointers。

G

有一个 n × m ( n , m ≤ 50 ) n\times m(n,m\le 50) n×m(n,m50)的矩阵,每个格子里有一定量的苹果(每个苹果1元)。有 k ( k ≤ 1 e 5 ) k(k\le 1e5) k(k1e5)个顾客,每个顾客带了一定数量的钱,且只能在一个子矩阵内购买苹果。求最大总消费量。

网络流,但直接建图边数是 O ( n m k ) O(nmk) O(nmk)的,会MLE。
可以考虑二维线段树优化建图,把边数减少到 O ( n m + k log ⁡ n m ) O(nm+k\log nm) O(nm+klognm)

H

有一个 n n n个点的完全图,每条边有一个颜色。该图满足:任意一个简单环上必定存在一对相邻边同色。
定义 f ( S ) f(S) f(S)为点集 S S S中最大同色(即图中所有点间的边颜色相同)子图的大小。
∑ S ⊆ [ 1 , n ] f ( S ) \sum_{S\subseteq [1,n]}f(S) S[1,n]f(S)

可以证明图中必定有一个点的所有出边颜色相同。
去掉这个点后剩下的图依然满足。
因此可以转化成一个长为 n n n的序列。
然后搞dp

全部评论

相关推荐

星辰再现:裁员给校招生腾地方
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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