贪心 - Page 7 - hzwer.com

「CF500B」New Year Permutation
Useraintahasapermutationp1, p2, ..., pn.AstheNewYeariscoming,hewantstomakehispermutationasprettyaspossible.Permutationa1, a2, ..., anisprettierthanpermutationb1, b2, ..., bn,ifandonlyifthereexistsanintegerk(1 ≤ k ≤ n)wherea1 = b1, a2 = b2, ..., ak - 1 = bk - 1andak < bkallholds.Asknown,permutationpissosensitivethatitcouldbeonlymodifiedbyswappingtwodistinctele...
02014年12月31日3,790贪心,并查集

「BZOJ3105」[CQOI2013] 新Nim游戏
Description传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样...
22014年12月20日7,694贪心,高斯消元
「BZOJ3166」[HEOI2013] Alo
DescriptionWelcometoALO(ArithmeticandLogisticOnline)。这是一个VRMMORPG ，如名字所见，到处充满了数学的谜题。现在你拥有n颗宝石，每颗宝石有一个能量密度，记为ai，这些宝石的能量密度两两不同。现在你可以选取连续的一些宝石（必须多于一个）进行融合，设为 ai,ai+1,…,a j，则融合而成的宝石的能量密度为这些宝石中能量密度的次大值与其他任意一颗宝石的能量密度按位异或的值，即，设该段宝石能量密度次...
22014年12月18日8,151贪心,可持久化字典树
「CF497C」Distributing Parts
Youareanassistantdirectorinanewmusicalplay.Theplayconsistsofnmusicalparts,eachpartmustbeperformedbyexactlyoneactor.Afterthecastingthedirectorchosemactorswhocantakepartintheplay.Yourtaskistoassignthepartstoactors.However,thereareseverallimitations.First,eachactorhasacertainvoicerangeandtherearesomepartsthathecannotsing.Formally,therearetwointegersforeachactor,cianddi(ci ≤ di) —thepitcho...
02014年12月18日4,167贪心
「CF497A」Removing Columns
Youaregivenann × mrectangulartableconsistingoflowercaseEnglishletters.Inoneoperationyoucancompletelyremoveonecolumnfromthetable.Theremainingpartsarecombinedforminganewtable.Forexample,afterremovingthesecondcolumnfromthetable[crayon-690e66c337a28895211515/]weobtainthetable:[crayon-690e66c337a30778052999/]Atableiscalledgoodifitsrowsareorderedfromtoptobottomlexicographically,i.e.eachrowislex...
02014年12月18日2,956贪心
「BZOJ3261」最大异或和
Description给定一个非负整数序列{a}，初始长度为N。有 M个操作，有以下两种操作类型：1、Ax：添加操作，表示在序列末尾添加一个数x，序列的长度N+1。2、Qlrx：询问操作，你需要找到一个位置p，满足l<=p<=r，使得：a[p]xora[p+1]xor...xora[N]xorx最大，输出最大是多少。Input第一行包含两个整数N ，M，含义如问题描述所示。第二行包含N个非负整数，表示初始的序列A。接下来M行，每行描述一个操作，格式如题...
102014年12月16日12,121贪心,可持久化字典树
「BZOJ1954」Pku3764 The xor – longest Path
Description给定一棵n个点的带权树，求树上最长的异或和路径InputTheinputcontainsseveraltestcases.Thefirstlineofeachtestcasecontainsanintegern(1<=n<=100000),Thefollowingn-1lineseachcontainsthreeintegersu(0<=u<n),v(0<=v<n),w(0<=w<2^31),whichmeansthereisanedgebetweennodeuandvoflengthw.OutputForeachtestcaseoutputthexor-lengthofthexor-longestpath.SampleInput4123234246Samp...
02014年12月16日4,935贪心,字典树
「CF494A」Treasure
Malekhasrecentlyfoundatreasuremap.Whilehewaslookingforatreasurehefoundalockeddoor.Therewasastringswrittenonthedoorconsistingofcharacters'(',')'and'#'.Belowtherewasamanualonhowtoopenthedoor.AfterspendingalongtimeMalekmanagedtodecodethemanualandfoundoutthatthegoalistoreplaceeach'#'withoneormore')'characterssothatthefinalstringbecomesbeautiful.Belowtherewasalsowrittenthatastringiscalledbeautif...
22014年12月14日3,341贪心
「BZOJ2802」[POI2012] Warehouse Store
Description有一家专卖一种商品的店，考虑连续的n天。第i天上午会进货Ai件商品，中午的时候会有顾客需要购买Bi件商品，可以选择满足顾客的要求，或是无视掉他。如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。Input第一行一个正整数n(n<=250,000)。第二行n个整数A1,A2,...An(0<=Ai<=10^9)。第三行n个整数B1,B2,...Bn(0<=Bi<=10^9)。Output第一行一个正整数k，表示最多...
02014年12月7日3,410贪心,STL
「BZOJ1528」[POI2005] sam – Toy Cars
DescriptionJasio是一个三岁的小男孩,他最喜欢玩玩具了,他有n个不同的玩具,它们都被放在了很高的架子上所以Jasio拿不到它们.为了让他的房间有足够的空间,在任何时刻地板上都不会有超过k个玩具.Jasio在地板上玩玩具.Jasio'的妈妈则在房间里陪他的儿子.当Jasio想玩地板上的其他玩具时,他会自己去拿,如果他想玩的玩具在架子上,他的妈妈则会帮他去拿,当她拿玩具的时候,顺便也会将一个地板上的玩具放上架子使得地板上有足够的空间...
02014年12月6日4,737STL,贪心,堆
「CF492C」Vanya and Exams
Vanyawantstopassnexamsandgettheacademicscholarship.Hewillgetthescholarshipiftheaveragegrademarkforalltheexamsisatleastavg.Theexamgradecannotexceedr.Vanyahaspassedtheexamsandgotgradeaiforthei-thexam.Toincreasethegradeforthei-thexamby1point,Vanyamustwritebiessays.Hecanraisetheexamgrademultipletimes.WhatistheminimumnumberofessaysthatVanyaneedstowritetogetscholarship?InputThefirstlinecontai...
22014年12月2日3,658贪心
「BZOJ1052」[HAOI2007] 覆盖问题
Description某人在山上种了N棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定用3个L*L的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系，设第i棵小树的坐标为（Xi,Yi），3个L*L的正方形的边要求平行与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求L最小值。Input...
22014年12月1日6,599贪心