• 【bzoj3158】千钧一发

    【bzoj3158】千钧一发

    DescriptionInput第一行一个正整数N。第二行共包括N个正整数,第个正整数表示Ai。第三行共包括N个正整数,第个正整数表示Bi。Output共一行,包括一个正整数,表示在合法的选择条件下,可以获得的能量值总和的最大值。SampleInput43451298309SampleOutput39HINT1<=N<=1000,1<=Ai,Bi<=10^6题解可以证明,任意两个偶数满足2两个奇数满足1(2a+1)^2+(2b+1)^2=2(2a^2+2b^2+2a+2b+1)一定不是完全平方数所以...

    12014年12月15日1,328最小割
  • 【NOIP模拟赛】花园的守护之神

    【NOIP模拟赛】花园的守护之神

    题目描述看着正在被上古神兽们摧残的花园,花园的守护之神――小Bug同学泪流满面。然而,FZOI不相信眼泪,小bug与神兽们的战争将进行到底!通过google,小Bug得知,神兽们来自遥远的戈壁。为了扭转战局,小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂,由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie,而且可以...

    32014年10月28日1,134最小割,STL,dijkstra
  • 【bzoj1324】Exca王者之剑

    【bzoj1324】Exca王者之剑

    Description Input第一行给出数字N,M代表行列数.N,M均小于等于100下面N行M列用于描述数字矩阵Output输出最多可以拿到多少块宝石SampleInput221221SampleOutput4题解最小割[crayon-58afad91d88b4494305657/]  ...

    02014年8月26日1,209最小割
  • 【bzoj2561】最小生成树

    【bzoj2561】最小生成树

    Description 给定一个边带正权的连通无向图G=(V,E),其中N=|V|,M=|E|,N个点从1到N依次编号,给定三个正整数u,v,和L(u≠v),假设现在加入一条边权为L的边(u,v),那么需要删掉最少多少条边,才能够使得这条边既可能出现在最小生成树上,也可能出现在最大生成树上?Input  第一行包含用空格隔开的两个整数,分别为N和M;接下来M行,每行包含三个正整数u,v和w表示图G存在一条边权为w的边(u,v)。最后一行包含用...

    02014年7月19日2,339最小割
  • 【bzoj1532】[POI2005]Kos-Dicing

    【bzoj1532】[POI2005]Kos-Dicing

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

    02014年6月15日1,119最小割,二分法
  • 网络流&费用流模板

    网络流&费用流模板

    网络流dinic[crayon-58afad91d9cd6320376744/]最小费用最大流spfa[crayon-58afad91d9cec516935341/]zkw费用流[crayon-58afad91d9cf7132347840/] 

    132014年5月1日3,114最小割,费用流,最大流
  • 【bzoj3275】Number

    【bzoj3275】Number

    Description有N个正整数,需要从中选出一些数,使这些数的和最大。若两个数a,b同时满足以下条件,则a,b不能同时被选1:存在正整数C,使a*a+b*b=c*c2:gcd(a,b)=1Input第一行一个正整数n,表示数的个数。第二行n个正整数a1,a2,?an。Output最大的和。SampleInput534567SampleOutput22HINTn<=3000。题解将所有点拆成2个0向i连权为a[i]的边,a[i]向T连权为a[i]的边有关系的点互相连边,权为inf答案是tot-ans/2[crayon-5...

    52014年5月1日1,342最小割
  • 【bzoj2768】[JLOI2010]冠军调查

    【bzoj2768】[JLOI2010]冠军调查

    Description一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰,英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查,调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者,大家齐聚一堂,各抒己见。每一位参与者都将发言,阐述自己的看法。参与者的心里都有一个看法,比如FireDancer认为切尔西不可能夺冠,而W...

    02014年4月30日1,367最小割
  • 【bzoj1391】[Ceoi2008]order

    【bzoj1391】[Ceoi2008]order

    Description有N个工作,M种机器,每种机器你可以租或者买过来.每个工作包括若干道工序,每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。现在给出这些参数,求最大利润Input第一行给出N,M(1<=N<=1200,1<=M<=1200)下面将有N块数据,每块数据第一行给出完成这个任务能赚到的钱(其在[1,5000])及有多少道工序接下来若干行每行两个数,分别描述完成工序所需要的机器编号及租用它的费用(其在[1,20000]...

    42014年4月13日1,588最小割
  • 【bzoj2127】happiness

    【bzoj2127】happiness

    Description高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大。Input第一行两个正整数n,m。接下来是六个矩阵第一个矩阵为n行m列此矩阵的第i行第j列的数字...

    22014年3月31日2,503最小割
  • 【bzoj2132】圈地计划

    【bzoj2132】圈地计划

    Description最近房地产商GDOI(GroupofDumbbellsOrIdiots)从NOI(NutsOldIdiots)手中得到了一块开发土地。据了解,这块土地是一块矩形的区域,可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境,每块小区域建造商业区和工业区能取得不同的经济价值。更具体点,对于第i行第j列的区域,建造商业区将得到Aij收益,建造工业区将得到Bij收益。另外不同的区域连在一起...

    12014年3月31日2,074最小割
  • 【bzoj1934】[Shoi2007]Vote 善意的投票

    【bzoj1934】[Shoi2007]Vote 善意的投票

    Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小?Input第一行只有两个整数n,m,保证有2...

    22014年3月17日1,269最小割
  • 【bzoj1412】[ZJOI2009]狼和羊的故事

    【bzoj1412】[ZJOI2009]狼和羊的故事

    Description“狼爱上羊啊爱的疯狂,谁让他们真爱了一场;狼爱上羊啊并不荒唐,他们说有爱就有方向......”Orez听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干!Orez的羊狼圈可以看作一个n*m个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼,它们总是对羊垂涎三尺,那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。...

    02014年3月16日2,377最小割