hzwer.com - Page 46

「BZOJ1010」[HNOI2008] 玩具装箱toy
DescriptionP教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第...
72014年11月28日25,664斜率优化,决策单调性

「BZOJ2276」[POI2011] Temperature
DescriptionTheByteotianInstituteofMeteorology(BIM)measurestheairtemperaturedaily.Themeasurementisdoneautomatically,anditsresultimmediatelyprinted.Unfortunately,theinkintheprinterhaslongdriedout...TheemployeesofBIMhoweverrealisedthefactonlyrecently,whentheByteotianOrganisationforMeteorology(BOM)requestedaccesstothatdata.AneagerinternbythenameofByteasarsavedtheday,ashesystemati...
02014年11月27日4,256单调队列
「BZOJ3781」小B的询问
Description小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。Input第一行，三个整数N、M、K。第二行，N个整数，表示小B的序列。接下来的M行，每行两个整数L、R。OutputM行，每行一个整数，其中第i行的整数表示第i个询问的答案。SampleInput64313211314263556S...
12014年11月27日5,862莫队算法
「BZOJ2793」[POI2012] Vouchers
Description考虑正整数集合，现在有n组人依次来取数，假设第i组来了x人，他们每个取的数一定是x的倍数，并且是还剩下的最小的x个。正整数中有m个数被标成了幸运数，问有哪些人取到了幸运数。Input第一行一个正整数m(m<=1,000,000)，下面m行每行一个正整数x(x<=1,000,000)，表示x是一个幸运数。接下来一行一个正整数n(n<=1,000,000)，下面n行每行一个正整数x(x<=1,000,000)，表示这一组来了x个人。Output第一行输出一...
02014年11月27日3,059其它
「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,138STL,单调队列
「BZOJ2407」探险
Description探险家小T好高兴！X国要举办一次溶洞探险比赛，获奖者将得到丰厚奖品哦！小T虽然对奖品不感兴趣，但是这个大振名声的机会当然不能错过！比赛即将开始，工作人员说明了这次比赛的规则：每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路，也有可能没有，但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发，并再次回到这个大溶洞。如果就这么点限制，那么问题就太简单了，可是举办方又...
12014年11月27日5,103STL,dijkstra
「BZOJ2259」[Oibh] 新型计算机
DescriptionTim正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数——自然数包括0），计算机先读取第一个数字S1，然后顺序向后读入S1个数字。接着再读一个数字S2，顺序向后读入S2个数字……依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处...
02014年11月25日4,684STL,dijkstra
「BZOJ3226」[SDOI2008] 校门外的区间
Description　　受校门外的树这道经典问题的启发，A君根据基本的离散数学的知识，抽象出5种运算维护集合S(S初始为空)并最终输出S。现在，请你完成这道校门外的树之难度增强版——校门外的区间。　　5种运算如下：UTS∪TITS∩TDTS－TCTT－SSTS⊕T　　基本集合运算如下：A∪B{x:xÎAorxÎB}A∩B{x:xÎAandxÎB}A－B{x:xÎAandxÏB}A⊕B(A－B)∪(B－A)Input　　输入共M行。　　每行的格...
02014年11月25日4,291线段树
「BZOJ3252」攻略
Description题目简述：树版[k取方格数]众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。今天他得到了一款新游戏《XX半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观...
12014年11月25日6,178STL,贪心
OI省选算法汇总
简单列了一点1.1基本数据结构1.数组2.链表，双向链表3.队列，单调队列，双端队列4.栈，单调栈1.2中级数据结构1.堆2.并查集与带权并查集3.hash表自然溢出双hash1.3高级数据结构1.树状数组2.线段树，线段树合并3.平衡树 Treap随机平衡二叉树 Splay伸展树 *ScapegoatTree替罪羊树4.块状数组，块状链表5.*树套树线段树套线段树线段树套平衡树 *平衡树套线段树6.可并堆左偏树 *配对堆7.*KDtre...
282014年11月24日72,336算法
「BZOJ3043」IncDec Sequence
Description给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。Input第一行一个正整数n接下来n行,每行一个整数,第i+1行的整数表示ai。。Output第一行输出最少操作次数第二行输出最终能得到多少种结果SampleInput41122SampleOutput12HINT对于100%的数据，n=1000...
02014年11月23日3,806贪心
「BZOJ1017」[JSOI2008] 魔兽地图DotR
DescriptionDotR(DefenseoftheRobots)Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA(DefenseoftheAncients)Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备...
42014年11月23日7,367树形动规