算法 - Page 29 - hzwer.com

「CF509A」Maximum in Table
Ann × ntableaisdefinedasfollows:Thefirstrowandthefirstcolumncontainones,thatis:ai, 1 = a1, i = 1foralli = 1, 2, ..., n.Eachoftheremainingnumbersinthetableisequaltothesumofthenumberaboveitandthenumbertotheleftofit.Inotherwords,theremainingelementsaredefinedbytheformulaai, j = ai - 1, j + ai, j - 1.Theseconditionsdefineallthevaluesinthetable.Youaregivenanumbern.Younee...
02015年1月31日2,920模拟

「BZOJ1998」[HNOI2010] Fsk物品调度
Description现在找工作不容易，Lostmonkey费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有n个位置，从0到n-1依次编号，一开始0号位置空，其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。规则由5个数描述，q，p，m，d，s，s表示空位的最终位置。首先生成一个序列c，c0=0，ci+1=(ci*q+p)modm。接下来从第一个盒子开始依次生成每个盒子的最终位置posi，posi=(ci+d*xi+yi)modn，xi,yi是为了...
02015年1月31日5,026置换,并查集
「BZOJ2004」[HNOI2010] Bus 公交线路
Description小Z所在的城市有N个公交车站，排列在一条长(N-1)km的直线上，从左到右依次编号为1到N，相邻公交车站间的距离均为1km。作为公交车线路的规划者，小Z调查了市民的需求，决定按下述规则设计线路：1．设共K辆公交车，则1到K号站作为始发站，N-K+1到N号台作为终点站。2．每个车站必须被一辆且仅一辆公交车经过（始发站和终点站也算被经过）。3．公交车只能从编号较小的站台驶往编号较大的站台。4．一辆公交车经过...
02015年1月31日4,968状压动规
「BZOJ1997」[HNOI2010] Planar
DescriptionInputOutput题解用平面图m<=3n-6的性质剪枝条若两条边在圆内相交，则他们在圆外也是相交的，即若a,b不能同时取，a’,b’也不能同时取按2-sat建模缩点后判断合法性[crayon-6911581fb2914381271854/] ...
32015年1月31日5,9532-SAT
「BZOJ3173」[TJOI2013] 最长上升子序列
Description给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？Input第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）OutputN行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。SampleInput3002Samp...
62015年1月29日9,000递推与动规,treap
「BZOJ2229」[ZJOI2011] 最小割
Description小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话：“对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割”现给定一张无向图，小白有若干个形如“图中有多少对点它们的最...
72015年1月28日9,466最小割
「BZOJ3162」独钓寒江雪
Description题解参照2007杨弋论文vfk的博客http://vfleaking.blog.163.com/blog/static/17480763420134452440444/太神了orzorzorz[crayon-6911581fb44f6507236346/]
72015年1月28日5,413树形动规,哈希表
「CF508C」Anya and Ghosts
Anyalovestowatchhorrormovies.Inthebesttraditionsofhorror,shewillbevisitedbymghoststonight.Anyahaslotsofcandlespreparedforthevisits,eachcandlecanproducelightforexactlytseconds.Ittakesthegirlonesecondtolightonecandle.Moreformally,Anyacanspendonesecondtolightonecandle,thenthiscandleburnsforexactlytsecondsandthengoesoutandcannolongerbeused.ForeachofthemghostsAnyaknowsthetimeatwhichitcomes:thei...
02015年1月28日3,494贪心
「CF508A」Pasha and Pixels
Pashaloveshisphoneandalsoputtinghishairup...Butthehairisnowirrelevant.Pashahasinstalledanewgametohisphone.Thegoalofthegameisfollowing.Thereisarectangularfieldconsistingofnrowwithmpixelsineachrow.Initially,allthepixelsarecoloredwhite.Inonemove,Pashacanchooseanypixelandcoloritblack.Inparticular,hecanchoosethepixelthatisalreadyblack,thenaftertheboy'smovethepixeldoesnotchange,thatis,itremains...
02015年1月28日2,418模拟
「CF508E」Arthur and Brackets
Noticethatthememorylimitisnon-standard.RecentlyArthurandSashahavestudiedcorrectbracketsequences.Arthurunderstoodthistopicperfectlyandbecomesoamazedaboutcorrectbracketsequences,soheevengothimselfafavoritecorrectbracketsequenceoflength2n.UnlikeArthur,Sashaunderstoodthetopicverybadly,andbrokeArthur'sfavoritecorrectbracketsequencejusttospitehim.AllArthurremembersabouthisfavoritesequenceisfo...
02015年1月28日4,189构造
「BZOJ3772」精神污染
Description兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。兵库县官方也大力发展旅游，为了方便...
02015年1月27日6,553dfs序,主席树
「vijos1459」车展
描述遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1，2，…，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子：L1R1L2R2…LmRm单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。为了更加美观，展览时需要调整展台的高度，使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有...
02015年1月25日4,720treap