算法 - Page 66 - hzwer.com

「NOIP模拟赛」工资
聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）输入第一行2个数n,m接下来n行，每行一个数，代表Vi.输出最小的最大钱数。样例输入751...
22014年9月6日3,360二分法

「BZOJ1655」[Usaco2006 Jan] Dollar Dayz 奶牛商店
DescriptionFarmerJohngoestoDollarDaysatTheCowStoreanddiscoversanunlimitednumberoftoolsonsale.Duringhisfirstvisit,thetoolsaresellingvariouslyfor$1,$2,and$3.FarmerJohnhasexactly$5tospend.Hecanbuy5toolsat$1eachor1toolat$3andanadditional1toolat$2.Ofcourse,thereareothercombinationsforatotalof5differentwaysFJcanspendallhismoneyontools.Heretheyare:1@US$3+1@US$21@US$3+2@US$11@US$...
02014年9月5日4,604背包动规,高精度
「BZOJ1857」[SCOI2010] 传送带
Description在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间Input输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy第三行是3个整数，分别是P，Q...
12014年9月5日5,175三分法
「BZOJ2251」[2010BJ Wc] 外星联络
Description小P在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高低电平将接收到的信号改写为由0和1构成的串，并坚信外星人的信息就隐藏在其中。他认为，外星人发来的信息一定会在他接受到的01串中重复出现，所以他希望找到他接受到的01串中所有重复出现次数大...
32014年9月4日5,175后缀数组
「JoyOI1860」后缀数组
描述Description我们定义一个字符串的后缀suffix(i)表示从s[i]到s[length(s)]这段子串。后缀数组（Suffix array）SA[i]中存放着一个排列，满足suffix(sa[i])<suffix(sa[i+1]) 按照字典序方式比较定义height[i]表示suffix(sa[i])与suffix(sa[i-1])之间的最长公共前缀长度，其中height[1]=0你的任务就是求出SA和height这两个数组。字符串长度<=200000输入格式InputFormat一行，为描述中的字符串（仅会出现小写字母）...
62014年9月4日4,830后缀数组
「BZOJ3695」「FJ2014集训」滑行
Description 首长NOI惨跪，于是去念文化课了。现在，他面对一道物理题。现在有一个小滑块可以在地面上滑行，地面上被划分成不同的区域，使得小滑块在不同的区域内部有一个不同的速度上限。小滑块在(0，0)点，我们现在要推动小滑块到目标点（x,y）。地面上有N层区域，每层区域都是矩形，现在给你一个序列{Hi}表示每层区域的高度，覆盖的地面横坐标范围是0～X，第i个区域的限速是vi。注：Y=Sigma(Hi)其中i从1到N其它...
02014年9月4日3,395二分法
「BZOJ2783」[JLOI2012] 树
Description第一行是两个整数N和S，其中N是树的节点数。第二行是N个正整数，第i个整数表示节点i的正整数。接下来的N-1行每行是2个整数x和y，表示y是x的儿子。输出格式：输出路径节点总和为S的路径数量。输入样例：输出样例：3312312132 数据范围：对于30%数据，N≤100；对于60%数据，N≤1000；对于100%数据，N≤100000，所有权值以及S都不超过1000。======================================================...
02014年9月3日4,937STL,深度搜索
「BZOJ1598」[Usaco2008 Mar] 牛跑步
DescriptionBESSIE准备用从牛棚跑到池塘的方法来锻炼.但是因为她懒,她只准备沿着下坡的路跑到池塘,然后走回牛棚.BESSIE也不想跑得太远,所以她想走最短的路经.农场上一共有M(1<=M<=10,000)条路,每条路连接两个用1..N(1<=N<=1000)标号的地点.更方便的是,如果X>Y,则地点X的高度大于地点Y的高度.地点N是BESSIE的牛棚;地点1是池塘.很快,BESSIE厌倦了一直走同一条路.所以她想走不同的路...
02014年9月3日6,312dijkstra
「BZOJ1069」[SCOI2007] 最大土地面积
Description在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。Input第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。Output最大的多边形面积，答案精确到小数点后3位。SampleInput5001011010.50.5SampleOutput1.000HINT数据范围n<=2000,|x|,|y|<=100000题解n=2000。。。所以可以枚举一条对角线然后在两边分别找一个...
12014年9月3日6,939凸包,旋转卡壳
「BZOJ1044」[HAOI2008] 木棍分割
Description有n根木棍,第i根木棍的长度为Li,n根木棍依次连结了一起,总共有n-1个连接处.现在允许你最多砍断m个连接处,砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小,并且输出有多少种砍的方法使得总长度最大的一段长度最小.并将结果mod10007。。。Input输入文件第一行有2个数n,m.接下来n行每行一个正整数Li,表示第i根木棍的长度.Output输出有2个数,第一个数是总长度最大的一段的长度最小值,第二个数是有多少种...
02014年9月2日5,504递推与动规
「BZOJ1034」[ZJOI2008] 泡泡堂BNB
Description 第XXXX届NOI期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由n名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手，二号选手……，n号选手捉对厮杀，共进行n场比赛。每胜一场比赛得2分，平一场得1分，输一场不得分。最终将双方的...
02014年9月2日5,666贪心
「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,214单调队列