BZOJ1076 [SCOI2008]奖励关

MayFlyyh | DP, 期望 | 2018-07-12
BZOJ 1076: [SCOI2008]奖励关 Time Limit: 10 Sec Memory Limit: 128 MB Description   你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物, 每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。 宝物一共有n种,系统每次抛... [阅读全文]

BZOJ1415 [Noi2005]聪聪和可可

MayFlyyh | DP, 期望 | 2018-07-12
BZOJ1415 [Noi2005]聪聪和可可
BZOJ1415 [Noi2005]聪聪和可可 首先要预处理处当前聪聪在i点,可可在j点的时候聪聪下一步要走到哪里(这我都没想出来。。。 然后就比较简单了,根据套路,这个聪聪在x节点的期望应该是可可在j节点走到各种地方后,聪聪跟上的期望,当然也要算出可可留在原地,聪聪跑两步的期望。最后一加就好了。 一开始是这么想的,可害怕转移的东西互相依赖就没... [阅读全文]

【网络流24题】软件补丁问题

MayFlyyh | 网络流 | 2018-06-29
【网络流24题】软件补丁问题 T 公司发现其研制的一个软件中有 n 个错误,随即为该软件发放了一批共 m 个补丁程序。每一个补丁程序都有其特定的适用环境,某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时,往往会加入另一些错误。 换句话说,对于每一个补丁 i,都有 2 个与之相应的错误... [阅读全文]

【网络流24题】汽车加油行驶问题

MayFlyyh | 网络流 | 2018-06-29
【网络流24题】汽车加油行驶问题
【网络流24题】汽车加油行驶问题 给定一个N×N 的方形网格,设其左上角为起点◎,坐标 (1,1),X轴向右为正,Y 轴向下为正,每个方格边长为 11 ,如图所示。 一辆汽车从起点◎出发驶向右下角终点▲,其坐标为 (N,N)(N,N) 。 在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则: 汽车只能沿网... [阅读全文]

BZOJ4196 [NOI2015]软件包管理器

MayFlyyh | 树链剖分 | 2018-06-29
BZOJ4196 [NOI2015]软件包管理器 Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu使用的apt-get,Fedora/CentOS使用的yum,以及OSX... [阅读全文]

Luogu P1377 [TJOI2011]树的序

MayFlyyh | 其他 | 2018-06-26
Luogu P1377 [TJOI2011]树的序 不知道为什么bzoj上没这道题。。 题目描述 众所周知,二叉查找树的形态和键值的插入顺序密切相关。准确的讲:1、空树中加入一个键值k,则变为只有一个结点的二叉查找树,此结点的键值即为k;2、在非空树中插入一个键值k,若k小于其根的键值,则在其左子树中插入k,否则在其右子树中插入k。 我们将一棵二叉... [阅读全文]

动态最值

MayFlyyh | 线段树 | 2018-06-16
动态最值 题目描述 有一个包含n个元素的数组,要求实现以下操作: DELETE k:删除位置k上的数。右边的数往左移一个位置。 QUERY i j:查询位置i~j上所有数的最小值和最大值。 例如有10个元素: 位置 1 2 3 4 5 6 7 8 9 10 元素 1 5 2 6 7 4 9 3 1 5 QUERY 2 8的结果为2 9。 依次执行DELETE 3和DELETE 6(注... [阅读全文]

BZOJ 2763 [JLOI2011]飞行路线

MayFlyyh | 最短路 | 2018-06-16
BZOJ 2763 [JLOI2011]飞行路线 1579: [Usaco2009 Feb]Revamping Trails 道路升级 Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在 n 个城市设有业务,设这些城市分别标记为 0 到 n-1 ,一共有 m 种航线,每种航线连接两个城市,并且航线有一定的价格。 Alice和Bob现在要从一个城市沿着航线到达另一个城市,... [阅读全文]

BZOJ 1593[Usaco2008 Feb]Hotel 旅馆

MayFlyyh | 线段树 | 2018-06-16
参考样例,第一行输入n,m ,n代表有n个房间,编号为1---n,开始都为空房,m表示以下有m行操作,以下 每行先输入一个数 i ,表示一种操作: 若i为1,表示查询房间,再输入一个数x,表示在1--n 房间中找到长度为x的连续空房,输出连续x个房间中左端的房间号,尽量让这个房间号最小,若找不到长度为x的连续空房,输出0。 若i为2,表示退房,... [阅读全文]

静态主席树

MayFlyyh | 学习笔记 | 2018-06-16
静态主席树 维护区间查某个数的存在次数或者第k大以及更多 可持久化线段树+权值线段树 可持久化线段树,每次修改logn个节点包含当前需要修改的点x的区间,从前一个中继承剩下无需修改的区间 主席树查询:用区间下标root[r]-区间下标root[l-1]的结果查询 比如一个数在r以内的出现次数为x,在l-1以内的出现次数为y 那么在l-r区间内出现的次数就是x-... [阅读全文]
Ɣ回顶部