北方高校联合训练第一周D-数学题-二分+尺取+单调性

奇奇怪怪的第一次北方高校联合训练,比赛时候只写出来一题……太惨了……这题看了题解后还想了半天……真的太菜了……
最近在写一个奇怪的py,本来这周不准备写题解想专心把奇怪的py写出来,不过这题很有意思,还是写个题解吧
题目链接

题意:有两个集合A,B(每个集合元素个数<=1e5)。集合C的定义是{c∣c=a/b,a∈A,b∈B}(其中/是小数除法)。现在给你集合A,B,问C中第k大的数是几,精确到两位小数。

codeforces 777E-Hanoi Factory 排序+树状数组+dp

题意:有n个圆环,每个圆环有一个外直径b、一个内直径a和一个高度h。一个圆环能放在另外一个圆环上面有两个条件,一是上面圆环的外直径b1小于等于下面圆环的外直径b2,二是上面圆环的外直径b1大于下面圆环的内直径a2。现在让你选出其中的一些圆盘,使得他们能叠的最高。

codeforces-768-d-Jon and Orbs-概率dp

题目链接

感觉最近几场cf的后面几题都是树,而且大同小异……博客里面树太多了……放道dp压压惊……这场cf很是惨淡啊……c题跟b题一样注意到了数据范围的奇特性,但是还是强行猜测有循环节……果不其然的gg了……b题被特判坑数据fst了……还是太菜了……其实当时应该开这个D题的,这个题目并不难,自己推推也就一会的事……不该跟风去看什么E博弈论的……

题意:不知名的男主有个东西,那个东西每天会下一个球。男主为了抵御白学家(原文是white walkers……第一眼真的看成了white leaners……大限将至了……)需要有k(k<=1e3)种不同颜色的球每个至少一个。已知男主的那个东西每天下的球是k种颜色之一,且每种颜色等可能。现有q(q<=1e3)次询问,每次询问一个数pi,问多少天以后男主能抵御白学家的概率大于等于(pi-1e-7)/2000

codeforces-760e-Nikita and stack-线段树

题目链接

日常抄题解系列……

题意:这个题目的题意有点难懂,他的样例给的太特殊了……一个健忘症儿童有一个栈并进行了m次操作,操作有两种,一是pop,一是push(x)。因为他有健忘症,所以他不能按顺序记出操作的顺序。他每次能回忆出一个操作的操作种类,是第几步的操作,如果是push还能回忆出x。没当他回忆出一个操作后,请你根据他已经回忆出的所有操作给出到最后一步的栈顶元素,如果栈为空那么输出-1。

hdu6012-Lotus and Horticulture-离散化+前缀和

诶,又是好久没有更新,放假之后感觉就没做过什么题
一场bc的b题,并不是很难,但是想法感觉挺重要的

题目链接

题意:现在有n个植物,每个植物有个最佳温度区间,低于温度区间的产出是ci,高于温度区间的产出是bi,处于温度区间的产出是ai。现在让你选择一个温度是的产出最大,输出最大产出。

hdu5988 Coding Contest 2016青岛 费用流

大雾霾天,不想出去……
好久没写博客了,最近好懒呀……数分大物即将挂科……含参量积分简直就是噩梦……大物什么都记不得……
补了一下青岛的网络流,对图论完全无能的我只能抄题解了(还好当时没去青岛,去的北京,要不然又要打铁了……)……算是当做费用流的模板题吧……