二分法 - Page 7

「BZOJ1650」[Usaco2006 Dec] River Hopscotch 跳石子
DescriptionEveryyearthecowsholdaneventfeaturingapeculiarversionofhopscotchthatinvolvescarefullyjumpingfromrocktorockinariver.Theexcitementtakesplaceonalong,straightriverwitharockatthestartandanotherrockattheend,Lunitsawayfromthestart(1<=L<=1,000,000,000).Alongtheriverbetweenthestartingandendingrocks,N(0<=N<=50,000)morerocksappear,eachatanintegraldistanceDifromthestart(0<Di...
22014年7月23日3,821贪心,二分法

「fj夏令营」解释器
「题目描述」小呆同学热爱计算机科学。他最近对Python这种语言非常感兴趣，不仅希望学会怎么写Python的脚本，更希望搞清楚Python的解释器是怎么实现的，他找到了你，希望你可以编写一个简单的Python解释器。你被要求实现Python解释器中两种简单的功能：语句类型格式解释赋值语句A=B把B的值赋给A，这里的B是一个合法的Python表达式。forexample:>>>a=1//a=1>>>b=a+100//b=101输出语句print(A1[,A2,....
32014年7月20日4,223模拟,二分法
「czy系列赛」czy的后宫6
czy的后宫6题目描述众所周知的是丧尸czy有很多妹子（虽然很多但是质量不容乐观QAQ），今天czy把n个妹子排成一行来检阅。但是czy的妹子的质量实在……所以czy看不下去了。检阅了第i个妹子会增加czya[i]的肾虚值，他打算在检阅过程中最多休息m次（一开始检阅算0次休息，就是说czy最多可以检阅m+1次），每次休息过后czy又会龙精虎猛的继续检阅。问怎样分配才能使得czy在检阅过程中的最大肾虚值最小。当然这么简单的问题czy早就会做...
02014年7月19日3,692递推与动规,二分法
「NOIP模拟赛」笨笨的电话网络
多年以后，笨笨长大了，成为了电话线布置师。由于地震使得某市的电话线全部损坏，笨笨是负责接到震中市的负责人。该市周围分布着N(1≤N≤1000)根据1…n顺序编号的废弃的电话线杆，任意两根线杆之间没有电话线连接，一共有p(0≤p≤10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。第i对电线杆的两个端点分别是ai，bi，它们的距离为li(1≤li≤1000000)。数据中每对(ai，bi)只出现一次。编号为1的电话杆已经接入了全国的电...
02014年7月8日4,516spfa,二分法
「NOIP模拟赛」魔术球问题弱化版
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，…的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4根柱子上最多可放11个球。对于给定的n，计算在n根柱子上最多能放多少个球。输入描述第1行有1个正整数n，表示柱子数。输出描述一行表示可以放的最大球数4样例输出。样例输入11题目限制（...
02014年7月3日4,263二分法,最大流
「BZOJ1532」[POI2005] Kos – Dicing
DescriptionDicing是一个两人玩的游戏,这个游戏在Byteotia非常流行.甚至人们专门成立了这个游戏的一个俱乐部.俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.Input第一行两个整数n和m,1<=n<=10000,0<=m<=...
02014年6月15日4,942最小割,二分法
「BZOJ1146」[CTSC2008] 网络管理Network
DescriptionM公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通...
22014年6月13日8,186treap,树套树,线段树,二分法,树链剖分
「BZOJ2388」旅行规划
DescriptionOIVillage是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl决定修建了一条铁路将当地n个最著名的经典连接起来，让游客可以通过火车从铁路起点（1号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl为每一个景区都哦赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变化，某些景点的美观度也会发生变化。xkszlt...
42014年5月29日5,949二分法,分块
「BZOJ1196」[HNOI2006] 公路修建问题
DescriptionOIisland是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多。然而，由于该岛屿刚刚开发不久，所以那里的交通情况还是很糟糕。所以，OIERAssociation组织成立了，旨在建立OIisland的交通系统。OIisland有n个旅游景点，不妨将它们从1到n标号。现在，OIERAssociation需要修公路将这些景点连接起来。一条公路连接两个景点。公路有，不妨称它们为一级公路和二级公路。一级公路上的车速快，但是修路的花...
02014年5月27日4,791二分法
「BZOJ1717」[Usaco2006 Dec] Milk Patterns 产奶的模式
Description农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如12323231中2323出现了两次。当K=2时，这个长度为4。Input*Line1:两个整...
52014年5月20日6,671二分法,后缀数组
「BZOJ1863 / 3761」[ZJOI2006] trouble 皇帝的烦恼
Description经过多年的杀戮，秦皇终于统一了中国。为了抵御外来的侵略，他准备在国土边境安置n名将军。不幸的是这n名将军羽翼渐丰，开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。秦皇已经准备好了秘密处决这些无礼的边防大将。不过为防兵变，他决定先授予这些将军一些勋章，为自己赢得战略时间。将军们听说他们即将被授予勋章都很开心，他们纷纷上书表示感谢。第i个将军要求得到ai枚不同颜色的勋章。但是这些将军...
02014年5月1日4,113二分法
「CF425D」Sereja and Squares
Serejahaspainted n distinctpointsontheplane.Thecoordinatesofeachpointareintegers.Nowheiswondering:howmanysquaresaretherewithsidesparalleltothecoordinateaxesandwithpointspaintedinallitsfourvertexes?Helphim,calculatethisnumber.InputThefirstlinecontainsinteger n (1 ≤ n ≤ 105).Eachofthenext n linescontainstwointegers xi, yi (0 ≤ xi, yi ≤ 105),theintegersrepresentthecoordin...
02014年4月28日4,570二分法