单调队列 - hzwer.com

2017ACM萧山训练第2场(NWERC 2008)
A:EquilibriumMobile最终天平平衡的状态下，每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数[crayon-69cf7bdb02335080103353/]B:ProvingEquivalences答案是max{入度为0的连通块个数，出度为0的连通块个数}特判连通块为1的情况每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环[crayon-69cf7bdb02341884655104/]C:Catvs.Dog找出所有相互不兼容的人，将他们连边...
12017年8月8日6,747递推与动规,贪心,单调队列,图的连通,二分图匹配,扩展欧几里得算法

程序设计实习实验班2017推荐习题
区间众数问题这题写莫队是最容易的，可以对于每种出现次数的数字维护一个堆，用于删除时维护答案[crayon-69cf7bdb03a16636316547/]「BZOJ3659」WhichDreamedIt 神奇钥匙求以1为起点的欧拉回路的个数乘1的度数BESTtheorem[crayon-69cf7bdb03a24127560147/]「bzoj4031」[HEOI2015]小Z的房间矩阵树定理推荐阅读算法合集之《欧几里得算法的应用》[crayon-69cf7bdb03a2c474065889/]POJ2373DividingthePath用dp(i)...
12017年6月24日9,636递推与动规,STL,快速幂,单调队列,莫队算法,高斯消元
NOI2005瑰丽华尔兹
Description你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼•布德曼•T.D.•柠檬•1900，朋友们都叫他1900。1900在20世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上，很不幸他刚出生就被抛弃了，成了孤儿。1900孤独的成长在弗吉尼亚号上，从未离开过这个摇晃的...
02015年6月29日8,024递推与动规,单调队列
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日8,405点分治,二分法,单调队列
「BZOJ2276」[POI2011] Temperature
DescriptionTheByteotianInstituteofMeteorology(BIM)measurestheairtemperaturedaily.Themeasurementisdoneautomatically,anditsresultimmediatelyprinted.Unfortunately,theinkintheprinterhaslongdriedout...TheemployeesofBIMhoweverrealisedthefactonlyrecently,whentheByteotianOrganisationforMeteorology(BOM)requestedaccesstothatdata.AneagerinternbythenameofByteasarsavedtheday,ashesystemati...
02014年11月27日4,589单调队列
「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日6,966STL,单调队列
「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日3,825单调队列
「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）同时出现在前两个的简单回路里。另外，第三张图也...
22014年10月10日11,827递推与动规,单调队列,仙人掌
「BZOJ1047」[HAOI2007] 理想的正方形
Description有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。Input第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。Output仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。SampleInput5421256017160161721210211222SampleOutput1问题规模...
12014年9月1日6,360单调队列
「BZOJ1012」[JSOI2008] 最大数maxnumber
Description现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：QL功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：An功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有...
42014年6月15日12,056线段树,单调栈,单调队列
「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只连续的奶牛，...
92014年5月24日7,385递推与动规,单调队列
「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日5,581递推与动规,单调队列