hzwer.com - Page 30

「BZOJ1997」[HNOI2010] Planar
DescriptionInputOutput题解用平面图m<=3n-6的性质剪枝条若两条边在圆内相交，则他们在圆外也是相交的，即若a,b不能同时取，a’,b’也不能同时取按2-sat建模缩点后判断合法性[crayon-68462ab59dcca564380193/] ...
32015年1月31日5,8662-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日8,532递推与动规,treap
「BZOJ2229」[ZJOI2011] 最小割
Description小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话：“对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点s,t不在同一个部分中，则称这个划分是关于s,t的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而s,t的最小割指的是在关于s,t的割中容量最小的割”现给定一张无向图，小白有若干个形如“图中有多少对点它们的最...
72015年1月28日9,165最小割
「BZOJ3162」独钓寒江雪
Description题解参照2007杨弋论文vfk的博客http://vfleaking.blog.163.com/blog/static/17480763420134452440444/太神了orzorzorz[crayon-68462ab59f57d600811713/]
72015年1月28日5,114树形动规,哈希表
「CF508C」Anya and Ghosts
Anyalovestowatchhorrormovies.Inthebesttraditionsofhorror,shewillbevisitedbymghoststonight.Anyahaslotsofcandlespreparedforthevisits,eachcandlecanproducelightforexactlytseconds.Ittakesthegirlonesecondtolightonecandle.Moreformally,Anyacanspendonesecondtolightonecandle,thenthiscandleburnsforexactlytsecondsandthengoesoutandcannolongerbeused.ForeachofthemghostsAnyaknowsthetimeatwhichitcomes:thei...
02015年1月28日3,268贪心
「CF508A」Pasha and Pixels
Pashaloveshisphoneandalsoputtinghishairup...Butthehairisnowirrelevant.Pashahasinstalledanewgametohisphone.Thegoalofthegameisfollowing.Thereisarectangularfieldconsistingofnrowwithmpixelsineachrow.Initially,allthepixelsarecoloredwhite.Inonemove,Pashacanchooseanypixelandcoloritblack.Inparticular,hecanchoosethepixelthatisalreadyblack,thenaftertheboy'smovethepixeldoesnotchange,thatis,itremains...
02015年1月28日2,344模拟
「CF508E」Arthur and Brackets
Noticethatthememorylimitisnon-standard.RecentlyArthurandSashahavestudiedcorrectbracketsequences.Arthurunderstoodthistopicperfectlyandbecomesoamazedaboutcorrectbracketsequences,soheevengothimselfafavoritecorrectbracketsequenceoflength2n.UnlikeArthur,Sashaunderstoodthetopicverybadly,andbrokeArthur'sfavoritecorrectbracketsequencejusttospitehim.AllArthurremembersabouthisfavoritesequenceisfo...
02015年1月28日4,051构造
「BZOJ3772」精神污染
Description兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。兵库县官方也大力发展旅游，为了方便...
02015年1月27日6,440dfs序,主席树
「vijos1459」车展
描述遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1，2，…，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子：L1R1L2R2…LmRm单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。为了更加美观，展览时需要调整展台的高度，使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有...
02015年1月25日4,598treap
「BZOJ3876」[Ahoi2014] 支线剧情
Description「故事背景」宅男JYY非常喜欢玩RPG游戏，比如仙剑，轩辕剑等等。不过JYY喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在JYY想花费最少的时间看完所有的支线剧情。「问题描述」JYY现在所玩的RPG游戏中，一共有N个剧情点，由1到N编号，第i个剧情点可以根据JYY的不同的选择，而经过不同的支线剧情，前往Ki种不同的新的剧情点。当然如果为0...
92015年1月25日7,280费用流,有上下界网络流
「POJ2187」Beauty Contest
DescriptionBessie,FarmerJohn'sprizecow,hasjustwonfirstplaceinabovinebeautycontest,earningthetitle'MissCowWorld'.Asaresult,BessiewillmakeatourofN(2<=N<=50,000)farmsaroundtheworldinordertospreadgoodwillbetweenfarmersandtheircows.Forsimplicity,theworldwillberepresentedasatwo-dimensionalplane,whereeachfarmislocatedatapairofintegercoordinates(x,y),eachhavingavalueintherange-10,000...1...
12015年1月25日8,366凸包,旋转卡壳
「CF403C」Strictly Positive Matrix
Youhavematrixaofsizen × n.Let'snumbertherowsofthematrixfrom1tonfromtoptobottom,let'snumberthecolumnsfrom1tonfromlefttoright.Let'suseaijtorepresenttheelementontheintersectionofthei-throwandthej-thcolumn.Matrixameetsthefollowingtwoconditions:foranynumbersi, j(1 ≤ i, j ≤ n)thefollowinginequalityholds:aij ≥ 0;.Matrixbisstrictlypositive,ifforanynumbersi, j(1 ≤ i, j ≤ n)theine...
02015年1月24日5,202图的连通