hzwer.com - Page 36

「CF498D」Traffic Jams in the Land
Somecountryconsistsof(n + 1)cities,locatedalongastraighthighway.Let'snumberthecitieswithconsecutiveintegersfrom1ton + 1intheordertheyoccuralongthehighway.Thus,thecitiesareconnectedbynsegmentsofthehighway,thei-thsegmentconnectscitiesnumberiandi + 1.Everysegmentofthehighwayisassociatedwithapositiveintegerai > 1—theperiodoftrafficjamsappearanceonit.Inordertogetfromcityxtocityy(x <...
12014年12月25日4,714线段树

「CF498B」Name That Tune
ItturnsoutthatyouareagreatfanofrockbandAC/PE.Peterlearnedthatandstartedthefollowinggame:heplaysthefirstsongofthelistofnsongsofthegroup,andyouhavetofindoutthenameofthesong.Afteryoutellthesongname,Peterimmediatelyplaysthefollowingsonginorder,andsoon.Thei-thsongofAC/PEhasitsrecognizabilitypi.Thismeansthatifthesonghasnotyetbeenrecognizedbyyou,youlistentoitforexactlyonemoresecondandwithpr...
12014年12月25日3,730递推与动规,概率与期望
「BZOJ3190」[JLOI2013] 赛车
Description这里有一辆赛车比赛正在进行，赛场上一共有N辆车，分别称为个g1，g2……gn。赛道是一条无限长的直线。最初，gi位于距离起跑线前进ki的位置。比赛开始后，车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中，如果一辆赛车曾经处于领跑位置的话（即没有其他的赛车跑在他的前面），这辆赛车最后就可以得奖，而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度，你的任务就是算出那些赛车将会得...
42014年12月25日4,569半平面交
「CF498C」Array and Operations
Youhavewrittenonapieceofpaperanarrayofnpositiveintegersa[1], a[2], ..., a[n]andmgoodpairsofintegers(i1, j1), (i2, j2), ..., (im, jm).Eachgoodpair(ik, jk)meetsthefollowingconditions:ik + jkisanoddnumberand1 ≤ ik < jk ≤ n.Inoneoperationyoucanperformasequenceofactions:takeoneofthegoodpairs(ik, jk)andsomeintegerv(v > 1),whichdividesbothnumbersa[ik]anda[jk];dividebothnum...
02014年12月25日4,540最大流
「BZOJ1185」[HNOI2007] 最小矩形覆盖
Description题解首先有一个结论，矩形的一条边一定在凸包上！！！枚举凸包上的边用旋转卡壳在凸包上找矩形另外三点。。。注意精度问题[crayon-67b8c5dd8f60a901321492/] ...
72014年12月24日8,382凸包,旋转卡壳
「BZOJ1082」[SCOI2005] 栅栏
Description农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格...
02014年12月24日5,937深度搜索,二分法
「BZOJ1078」[SCOI2008] 斜堆
Description斜堆(skewheap)是一种常用的数据结构。它也是二叉树，且满足与二叉堆相同的堆性质：每个非根结点的值都比它父亲大。因此在整棵斜堆中，根的值最小。但斜堆不必是平衡的，每个结点的左右儿子的大小关系也没有任何规定。在本题中，斜堆中各个元素的值均不相同。在斜堆H中插入新元素X的过程是递归进行的：当H为空或者X小于H的根结点时X变为新的树根，而原来的树根（如果有的话）变为X的左儿子。当X大于H的根结点...
22014年12月24日6,960可并堆
「BZOJ2405」数字
DescriptionInput第一行一个整数T，表示数据组数。以下每一行两个数L、R（保证区间合法），代表询问[L,R]。Output输出T行，每行一个数，表示在这个区间内小D喜欢的数出现了多少次。你的输出当且仅当和标准输出一样才能得该测试点满分。SampleInput3153988SampleOutput220HINTL,R<=10^18,T<=20题解显然D(x)=D(x+9)观察下列式子1*D(1)=110*D(10)=1019*D(19)=19...即被1*9除余1的数都被喜欢2*D(2)=4...
32014年12月24日3,247其它
「BZOJ2333」[SCOI2011] 棘手的操作
Description有N个节点，标号从1到N，这N个节点一开始相互不连通。第i个节点的初始权值为a[i]，接下来有如下一些操作：U x y:加一条边，连接第x个节点和第y个节点A1 x v:将第x个节点的权值增加vA2 x v:将第x个节点所在的连通块的所有节点的权值都增加vA3 v:将所有节点的权值都增加vF1 x:输出第x个节点当前的权值F2 x:输出第x个节点所在的连通块中，权值最大的节点的权值F3:输出所有节点中，权值最大的节点的权值...
92014年12月23日7,900STL,可并堆
「BZOJ2822」[AHOI2012] 树屋阶梯
Description暑假期间，小龙报名了一个模拟野外生存作战训练班来锻炼体魄，训练的第一个晚上，教官就给他们出了个难题。由于地上露营湿气重，必须选择在高处的树屋露营。小龙分配的树屋建立在一颗高度为N+1尺（N为正整数）的大树上，正当他发愁怎么爬上去的时候，发现旁边堆满了一些空心四方钢材（如图1.1），经过观察和测量，这些钢材截面的宽和高大小不一，但都是1尺的整数倍，教官命令队员们每人选取N个空心钢材来搭建一个总...
02014年12月23日4,924高精度,卡特兰数
「BZOJ1485」[HNOI2009] 有趣的数列
Description 我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件： (1)它是从1到2n共2n个整数的一个排列{ai}； (2)所有的奇数项满足a1<a3<…<a2n-1，所有的偶数项满足a2<a4<…<a2n； (3)任意相邻的两项a2i-1与a2i(1≤i≤n)满足奇数项小于偶数项，即：a2i-1<a2i。现在的任务是：对于给定的n，请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大，所以只要求输...
12014年12月23日5,450递推与动规,卡特兰数
「BZOJ1486」[HNOI2009] 最小圈
题解分数规划，二分答案用dfs版的spfa判负环[crayon-67b8c5dd924a3253565786/]
02014年12月23日6,075spfa,二分法