• 「NOIP模拟赛」笨笨的电话网络

    「NOIP模拟赛」笨笨的电话网络

    多年以后,笨笨长大了,成为了电话线布置师。由于地震使得某市的电话线全部损坏,笨笨是负责接到震中市的负责人。该市周围分布着N(1≤N≤1000)根据1…n顺序编号的废弃的电话线杆,任意两根线杆之间没有电话线连接,一共有p(0≤p≤10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。第i对电线杆的两个端点分别是ai,bi,它们的距离为li(1≤li≤1000000)。数据中每对(ai,bi)只出现一次。编号为1的电话杆已经接入了全国的电...

    02014年7月8日1,667spfa,二分法
  • 「NOIP模拟赛」魔术球问题弱化版

    「NOIP模拟赛」魔术球问题弱化版

    假设有n根柱子,现要按下述规则在这n根柱子中依次放入编号为1,2,3,…的球。(1)每次只能在某根柱子的最上面放球。(2)在同一根柱子中,任何2个相邻球的编号之和为完全平方数。试设计一个算法,计算出在n根柱子上最多能放多少个球。例如,在4根柱子上最多可放11个球。对于给定的n,计算在n根柱子上最多能放多少个球。输入描述第1行有1个正整数n,表示柱子数。输出描述一行表示可以放的最大球数4样例输出。样例输入11题目限制(...

    02014年7月3日1,564二分法,最大流
  • 「BZOJ1532」[POI2005] Kos – Dicing

    「BZOJ1532」[POI2005] Kos - Dicing

    DescriptionDicing是一个两人玩的游戏,这个游戏在Byteotia非常流行.甚至人们专门成立了这个游戏的一个俱乐部.俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.Input第一行两个整数n和m,1<=n<=10000,0<=m<=...

    02014年6月15日1,953最小割,二分法
  • 「BZOJ1146」[CTSC2008] 网络管理Network

    「BZOJ1146」[CTSC2008] 网络管理Network

    DescriptionM公司是一个非常庞大的跨国公司,在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作,公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器,部门局域网内的所有机器都联向这个路由器,然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通...

  • 「BZOJ2388」旅行规划

    「BZOJ2388」旅行规划

    DescriptionOIVillage是一个风景秀美的乡村,为了更好的利用当地的旅游资源,吸引游客,推动经济发展,xkszltl决定修建了一条铁路将当地n个最著名的经典连接起来,让游客可以通过火车从铁路起点(1号景点)出发,依次游览每个景区。为了更好的评价这条铁路,xkszltl为每一个景区都哦赋予了一个美观度,而一条旅行路径的价值就是它所经过的景区的美观度之和。不过,随着天气与季节的变化,某些景点的美观度也会发生变化。xkszlt...

    42014年5月29日2,975二分法,分块
  • 「BZOJ1196」[HNOI2006] 公路修建问题

    「BZOJ1196」[HNOI2006] 公路修建问题

    DescriptionOIisland是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多。然而,由于该岛屿刚刚开发不久,所以那里的交通情况还是很糟糕。所以,OIERAssociation组织成立了,旨在建立OIisland的交通系统。OIisland有n个旅游景点,不妨将它们从1到n标号。现在,OIERAssociation需要修公路将这些景点连接起来。一条公路连接两个景点。公路有,不妨称它们为一级公路和二级公路。一级公路上的车速快,但是修路的花...

    02014年5月27日2,675二分法
  • 「BZOJ1717」[Usaco2006 Dec] Milk Patterns 产奶的模式

    「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日3,576二分法,后缀数组
  • 「BZOJ1863 / 3761」[ZJOI2006] trouble 皇帝的烦恼

    「BZOJ1863 / 3761」[ZJOI2006] trouble 皇帝的烦恼

    Description经过多年的杀戮,秦皇终于统一了中国。为了抵御外来的侵略,他准备在国土边境安置n名将军。不幸的是这n名将军羽翼渐丰,开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。秦皇已经准备好了秘密处决这些无礼的边防大将。不过为防兵变,他决定先授予这些将军一些勋章,为自己赢得战略时间。将军们听说他们即将被授予勋章都很开心,他们纷纷上书表示感谢。第i个将军要求得到ai枚不同颜色的勋章。但是这些将军...

    02014年5月1日2,241二分法
  • 「CF425D」Sereja and Squares

    「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日1,518二分法
  • 「BZOJ2120」数颜色

    「BZOJ2120」数颜色

    Description墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令:1、QLR代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。2、RPCol把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗?Input第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。第...

    12014年4月26日4,619二分法,分块
  • 「BZOJ2453」维护队列

    「BZOJ2453」维护队列

    Description你小时候玩过弹珠吗?小朋友A有一些弹珠,A喜欢把它们排成队列,从左到右编号为1到N。为了整个队列鲜艳美观,小朋友想知道某一段连续弹珠中,不同颜色的弹珠有多少。当然,A有时候会依据个人喜好,替换队列中某个弹珠的颜色。但是A还没有学过编程,且觉得头脑风暴太浪费脑力了,所以向你来寻求帮助。Input输入文件第一行包含两个整数N和M。第二行N个整数,表示初始队列中弹珠的颜色。接下来M行,每行的形式为...

    52014年4月26日4,772二分法,分块
  • 「BZOJ3343」教主的魔法

    「BZOJ3343」教主的魔法

    Description教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N。每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高)CYZ、光哥...

    22014年4月26日4,968二分法,分块