首页 > 其他 > 详细

10-1测试

时间:2017-10-01 18:30:02      阅读:226      评论:0      收藏:0      [点我收藏+]

今天水了~~

一句话题意:

T1:给n个点和k张门票,每次随机踢掉一个点,问1个人拿到门票的概率。1<=k<=n<=10^9

T2:给定一个数字三角形,可以从(i,j)走到(i+1,j)或(i+1,j+1),每次ban掉1个点,求从左上到最后一行的最大权值和。n<=1000,操作数<=10^5

T3:给定一颗区间二叉树,父亲的区间由儿子组成,询问[l,r]由多少个区间组成(最少),n<=10^5,询问数<=10^5

Solution:

T1:不难发现每个人都是公平竞争的,答案就是k/n了

T2:可以发现每一行都必须取1个点,然后算出从起点到每个点的最大取值和这个点到终点的最大取值,预处理出每行的最优决策点和次优决策点,若ban掉的这个点为最优决策点则输出次优方案,否则输出最优方案。n^2+m.

T3:这里有个重要的小技巧,[l,r]中根节点的个数=区间长度-非叶子节点个数=(r-l+1)-非叶子节点个数。将询问与所有节点代表的区间按l排序,线扫时维护一下区间在[l,r]中的非叶子节点的个数即可。

10-1测试

原文:http://www.cnblogs.com/dancer16/p/7617541.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!