• 2017ACM萧山训练第2场(NWERC 2008)

    2017ACM萧山训练第2场(NWERC 2008)

    A:EquilibriumMobile最终天平平衡的状态下,每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x]),答案是叶子数减去出现次数最多的个数[crayon-5a2e8662a52b1919113711/]B:ProvingEquivalences答案是max{入度为0的连通块个数,出度为0的连通块个数}特判连通块为1的情况每个连通块,出度0的点,向其它入度为0的连边,使得形成一个环[crayon-5a2e8662a52c9189786663/]C:Catvs.Dog找出所有相互不兼容的人,将他们连边...

  • 程序设计实习实验班2017推荐习题

    程序设计实习实验班2017推荐习题

    区间众数问题这题写莫队是最容易的,可以对于每种出现次数的数字维护一个堆,用于删除时维护答案[crayon-5a2e8662a99a2351006559/]【BZOJ3659】WhichDreamedIt 神奇钥匙求以1为起点的欧拉回路的个数乘1的度数BESTtheorem[crayon-5a2e8662a99e0829520537/]【bzoj4031】[HEOI2015]小Z的房间矩阵树定理推荐阅读算法合集之《欧几里得算法的应用》[crayon-5a2e8662a99f8924276876/]POJ2373DividingthePath用dp(i)...

  • NOI2005瑰丽华尔兹

    NOI2005瑰丽华尔兹

    Description你跳过华尔兹吗?当音乐响起,当你随着旋律滑动舞步,是不是有一种漫步仙境的惬意?众所周知,跳华尔兹时,最重要的是有好的音乐。但是很少有几个人知道,世界上最伟大的钢琴家一生都漂泊在大海上,他的名字叫丹尼•布德曼•T.D.•柠檬•1900,朋友们都叫他1900。1900在20世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上,很不幸他刚出生就被抛弃了,成了孤儿。1900孤独的成长在弗吉尼亚号上,从未离开过这个摇晃的...

    02015年6月29日2,855递推与动规,单调队列
  • WC2010重建计划

    WC2010重建计划

    DescriptionInput第一行包含一个正整数N,表示X国的城市个数.第二行包含两个正整数L和U,表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案,每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi其中城市由1..N进行标号Output输出最大平均估值,保留三位小数SampleInput423121132143SampleOutput2.500HINT20%的数据,N<=500030%的数据,N<=100000,原有方案恰...

    22014年12月3日3,109点分治,二分法,单调队列
  • 【bzoj2276】[Poi2011]Temperature

    【bzoj2276】[Poi2011]Temperature

    DescriptionTheByteotianInstituteofMeteorology(BIM)measurestheairtemperaturedaily.Themeasurementisdoneautomatically,anditsresultimmediatelyprinted.Unfortunately,theinkintheprinterhaslongdriedout...TheemployeesofBIMhoweverrealisedthefactonlyrecently,whentheByteotianOrganisationforMeteorology(BOM)requestedaccesstothatdata.AneagerinternbythenameofByteasarsavedtheday,ashesystemati...

    02014年11月27日1,990单调队列
  • 【bzoj2096】[Poi2010]Pilots

    【bzoj2096】[Poi2010]Pilots

    DescriptionTz又耍畸形了!!他要当飞行员,他拿到了一个飞行员测试难度序列,他设定了一个难度差的最大值,在序列中他想找到一个最长的子串,任意两个难度差不会超过他设定的最大值。耍畸形一个人是不行的,于是他找到了你。Input输入:第一行两个有空格隔开的整数k(0<=k<=2000,000,000),n(1<=n<=3000,000),k代表Tz设定的最大值,n代表难度序列的长度。第二行为n个由空格隔开的整数ai(1<=ai<=2000,000...

    12014年11月27日2,556STL,单调队列
  • 【NOIP模拟赛】滑动的窗户

    【NOIP模拟赛】滑动的窗户

    【题目描述】在一个包含n个元素的数组上,有一个长度为k的窗户在从左向右滑动。窗户每滑动到一个位置,我们都可以看到k个元素在窗户中。如下的例子所示,假设数组为 [1 3 -1 -3 5 3 6 7],而k等于3:窗户位置最小值最大值[1  3  -1] -3  5  3  6  7-131 [3  -1  -3] 5  3  6  7-331  3 [-1  -3  5] 3  6  7-351  3  -1 [-3  5  3] 6  7-351  3  -1  -3 [5  3  ...

    02014年11月4日1,519单调队列
  • 【bzoj1023】[SHOI2008]cactus仙人掌图

    【bzoj1023】[SHOI2008]cactus仙人掌图

    Description如果某个无向连通图的任意一条边至多只出现在一条简单回路(simplecycle)里,我们就称这张图为仙人图(cactus)。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。举例来说,上面的第一个例子是一张仙人图,而第二个不是——注意到它有三条简单回路:(4,3,2,1,6,5,4)、(7,8,9,10,2,3,7)以及(4,3,7,8,9,10,2,1,6,5,4),而(2,3)同时出现在前两个的简单回路里。另外,第三张图也...

    02014年10月10日5,263递推与动规,单调队列,仙人掌
  • 【bzoj1047】[HAOI2007]理想的正方形

    【bzoj1047】[HAOI2007]理想的正方形

    Description有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。Input第一行为3个整数,分别表示a,b,n的值第二行至第a+1行每行为b个非负整数,表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。Output仅一个整数,为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。SampleInput5421256017160161721210211222SampleOutput1问题规模...

    12014年9月1日2,837单调队列
  • 【bzoj1012】[JSOI2008]最大数maxnumber

    【bzoj1012】[JSOI2008]最大数maxnumber

    Description现在请求你维护一个数列,要求提供以下两种操作:1、查询操作。语法:QL功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。限制:L不超过当前数列的长度。2、插入操作。语法:An功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。限制:n是非负整数并且在长整范围内。注意:初始时数列是空的,没有...

    42014年6月15日4,766线段树,单调栈,单调队列
  • 【bzoj2442】[Usaco2011 Open]修剪草坪

    【bzoj2442】[Usaco2011 Open]修剪草坪

    Description在一年前赢得了小镇的最佳草坪比赛后,FJ变得很懒,再也没有修剪过草坪。现在,新一轮的最佳草坪比赛又开始了,FJ希望能够再次夺冠。然而,FJ的草坪非常脏乱,因此,FJ只能够让他的奶牛来完成这项工作。FJ有N(1<=N<=100,000)只排成一排的奶牛,编号为1...N。每只奶牛的效率是不同的,奶牛i的效率为E_i(0<=E_i<=1,000,000,000)。靠近的奶牛们很熟悉,因此,如果FJ安排超过K只连续的奶牛,...

    62014年5月24日2,795递推与动规,单调队列
  • 【bzoj1233】[Usaco2009Open]干草堆tower

    【bzoj1233】[Usaco2009Open]干草堆tower

    Description奶牛们讨厌黑暗。为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡。一共有N大包的干草(1<=N<=100000)(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个宽度W_i(1<=w_i<=10000)。所有的干草包的厚度和高度都为1.Bessie必须利用所有N包干草来建立起干草堆,并且按照他们进牛棚的顺序摆放。她可以相放多少包就放多少包来建立起tower的地基(当然是紧紧的放在...

    12014年5月20日2,425递推与动规,单调队列
  • 【bzoj1293】[SCOI2009]生日礼物

    【bzoj1293】[SCOI2009]生日礼物

    Description小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮,小西希望这一段彩带中能包含所有种类的彩珠。同时,为了方便,小西希望这段彩带尽可能短,你能帮助小西计算这个最短的长度么...

    12014年5月12日3,521单调队列