单调栈 - hzwer.com

2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-673f6d2531056611805603/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-673f6d2531064352916537/]D.Factors爆搜前16个素数[crayon-673f6d2531071281076730/]F.LowPower二分答案贪心检验[crayon-673f6d2531077890926611/]H:М...
12017年8月9日8,257STL,区间动规,贪心,深度搜索,二分法,最大流,几何,单调栈,最短路,排列组合

「BZOJ3238」[Ahoi2013] 差异
DescriptionInput一行，一个字符串SOutput一行，一个整数，表示所求值SampleInputcacaoSampleOutput54HINT2<=N<=500000,S由小写英文字母组成题解显然后缀数组不是正确姿势。。。不过还是说说后缀数组的做法吧，bzoj总时限20s是能过的SA+rmq求lcp应该烂大街了，这题还不用rmq。。。首先求出h数组考虑h[i]在哪些区间内会成为最小值，这个用两次单调栈很容易就能解决还要处理一下由于h[i]可能相同造成的重复计数...
62015年4月9日6,131后缀数组,单调栈
「BZOJ2086」[POI2010] Blocks
Description给出N个正整数a[1..N]，再给出一个正整数k，现在可以进行如下操作：每次选择一个大于k的正整数a[i]，将a[i]减去1，选择a[i-1]或a[i+1]中的一个加上1。经过一定次数的操作后，问最大能够选出多长的一个连续子序列，使得这个子序列的每个数都不小于k。总共给出M次询问，每次询问给出的k不同，你需要分别回答。Input第一行两个正整数N(N<=1,000,000)和M(M<=50)。第二行N个正整数，第i个正整数表示a[i](a[i...
02015年3月23日3,794单调栈
「NOIP模拟赛」chenzeyu97要请客
题目背景众所周知，哲♂学家chenzeyu97由于在前面的许多场比赛中都取得了优♂异成绩！所以他在这场赛后要请客！题目描述chenzeyu97的家可以看成是一个n*m的矩阵，每块区域都有独一无二的海拔高度h（h>0）！其最大值为n*m。现在他要选择一个子矩阵摆放一张桌子，在他眼里，这样摆放桌子的美观度为这个子矩阵的最小值，他想知道，如果他要求摆放桌子的美观度为i，那么可以选择多少种子矩阵呢？对于所有可能的i值（1<=i<=n*m...
02014年10月18日4,121单调栈
「codecomb2093」牛宫
DescriptionHzgd神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。胡张想让他的宫殿的平均海拔在海平面之上（假设海平面的高度是0，平均数都会算吧？）。而且，胡张希望他的宫殿是个矩形且尽量大，能够容纳更多的人来膜拜他。请问胡张的宫殿最后会有多大？Input Format第一行为N和M。之后N行，每行M个数，描述的空地的海拔。Output Format输出一行,表示宫殿最...
02014年10月15日3,758二分法,单调栈
「BZOJ2364」城市美化
Description城市A需要美化市容市貌，现在有n个楼房排成一列，每个楼房的高都在[1,1000]的范围内。市长请了一批工程师来对其中一些楼房进行修建，使楼房高度得到上升（不能让楼房高度下降），对一栋楼房修建，使其高度上升x，需要x2的费用。当所有修建完成后，我们把相邻两楼高度的绝对值乘以c(0<=c<=1000)，得到的就是城市损失的钱，我们把它同样看作是费用。现在想请你合理安排修建楼房的方案，使得所需费用最小。Input第...
32014年9月13日3,949递推与动规,单调栈
「BZOJ3401」[Usaco2009 Mar] Look Up 仰望
Description约翰的N(1≤N≤105)头奶牛站成一排，奶牛i的身高是Hi(l≤Hi≤1,000,000)．现在，每只奶牛都在向左看齐．对于奶牛i，如果奶牛j满足i<j且Hi<Hj，我们可以说奶牛i可以仰望奶牛j．求出每只奶牛离她最近的仰望对象．Input 第1行输入N，之后每行输入一个身高．Output 共N行，按顺序每行输出一只奶牛的最近仰望对象．如果没有仰望对象，输出0．SampleInput6326112SampleOutput3306...
02014年9月10日3,333单调栈
善良的hzwer
同公主的工作由于本题难度太高，善良的hzwer说：“为了方便旅客串门，还是将他们的房间安排为相邻的一排为好233。”对于每一天输出一行依次代表选取的房间高度,房间必须相邻,若不能安排则输出Impossible。(为了减少输出所需时间，只需输出第一个数即可)因为在做wulala的神模拟赛的时候题目看错了就出了这么一题TT做法是求出每个点为开头向后的连续上升序列长度然后可以搞一个答案数组TT，比如以字典序最小的数x1开头的长度为a...
02014年8月17日2,972贪心,单调栈
「BZOJ1683」[Usaco2005 Nov] City skyline 城市地平线
DescriptionInput第1行：2个用空格隔开的整数N和W.第2到N+1行：每行包括2个用空格隔开的整数x,y，其意义如题中所述．输入中的x严格递增，并且第一个z总是x．Output输出一个整数，表示城市中最少包含的建筑物数量．SampleInput10261122516381110152173202221INPUTDETAILS:ThecasementionedaboveSampleOutput6题解同1628[crayon-673f6d2535cd0929534600/] ...
02014年7月28日3,445单调栈
「BZOJ1628」[Usaco2007 Demo] City skyline
DescriptionThebestpartofthedayforFarmerJohn'scowsiswhenthesunsets.Theycanseetheskylineofthedistantcity.Bessiewondershowmanybuildingsthecityhas.Writeaprogramthatassiststhecowsincalculatingtheminimumnumberofbuildingsinthecity,givenaprofileofitsskyline.Thecityinprofileisquitedullarchitecturally,featuringonlybox-shapedbuildings.Theskylineofacityonthehorizonissomewherebetween1andWunitswide(1&...
02014年7月23日3,296单调栈
「BZOJ1012」[JSOI2008] 最大数maxnumber
Description现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：QL功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：An功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有...
42014年6月15日10,185线段树,单调栈,单调队列
「BZOJ1657」[Usaco2006 Mar] Mooo 奶牛的歌声
DescriptionFarmerJohn'sN(1<=N<=50,000)cowsarestandinginaverystraightrowandmooing.Eachcowhasauniqueheighthintherange1..2,000,000,000nanometers(FJreallyisasticklerforprecision).Eachcowmoosatsomevolumevintherange1..10,000.This"moo"travelsacrosstherowofcowsinbothdirections(exceptfortheendcows,obviously).Curiously,itisheardonlybytheclosestcowineachdirectionwhoseheightisstrictlylargerth...
02014年4月10日3,369单调栈