贪心 - Page 5 - hzwer.com

「BZOJ4029」[HEOI2015] 定价
Description 在市场上有很多商品的定价类似于999元、4999元、8999元这样。它们和1000元、5000元和9000元并没有什么本质区别，但是在心理学上会让人感觉便宜很多，因此也是商家常用的价格策略。不过在你看来，这种价格十分荒谬。于是你如此计算一个价格p（p为正整数）的荒谬程度：1、首先将p看做一个由数字组成的字符串（不带前导0）；2、然后，如果p的最后一个字符是0，就去掉它。重复这一过程，直到p的最后一个字符不是0；3、记...
02015年4月28日4,614贪心

「BZOJ4027」[HEOI2015] 兔子与樱花
Description很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成，编号从0到n-1，这n个分叉点由n-1个树枝连接，我们可以把它看成一个有根树结构，其中0号节点是根节点。这个树的每个节点上都会有一些樱花，其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m，对于每一个节点i，它的儿子节点的个数和i节点上樱花个数之和不能超过m，即so...
02015年4月27日7,011贪心,树形动规
「CF538X」Codeforces Round #300
A.CuttingBanner枚举切掉中间部分匹配[crayon-674300c11b9cf415897386/]B.QuasiBinary用最少的只包含01的数凑出n每次贪心在非0位上取1[crayon-674300c11b9db296649782/]C.Tourist'sNotes根据每俩个的时间及高度差可计算答案[crayon-674300c11b9ed176727515/]D.WeirdChess暴力暴力暴力[crayon-674300c11b9f3313046482/]E.DemiurgesPlayAgain考虑进入某个根，最终会取得子树第几小的叶子[crayon-674300c11b9f9258226...
02015年4月27日6,633模拟,贪心,主席树,调和级数
「BZOJ3624」[Apio2008] 免费道路
DescriptionInputOutputSampleInput572130451320531430121421 SampleOutput320430531121题解优先加1做生成树，得出必须添加的0的边反过来，将0的边加至K条，再放1的边[crayon-674300c11bfb6859929737/] ...
02015年4月24日5,300贪心,并查集
「BZOJ2811」[Apio2012] Guard
DescriptionInputOutputSampleInput534121341440451SampleOutput35HINT在这个样例中，有两种可能的安排方式：1，3，5 或者 2，3，5。即 3 和 5后面必然躲着一个忍者。考虑第一个灌木丛，存在一种安排方案使得它的后面躲着忍者，但也存在一种安排方案使得它后面没有躲忍者，因此不应该输出 1。同理，不应该输出 2。题解首先先将0的区间去除，可以用线段树TT如果去除0剩下的坐标编号等于忍者数，则所有剩下的坐标...
122015年4月24日7,603贪心,线段树,二分法
UOJ Round #2
http://vfleaking.blog.uoj.ac/blog/38「UR#2」猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-674300c11cf55038379570/]下面俩题怎么这么恶心TT「UR#2」跳蚤公路负环能影响一个点v当其与1，v都连通，这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k，枚举j，取整范围求并就能得出所能影响的点的x取值范围，x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...
52015年4月15日4,305贪心,spfa,floyd,点分治
「CF534X」Codeforces Round #298 (Div. 2)
「cf534A」Examyy个奇怪的构造TT[crayon-674300c11d953399083799/]「cf534B」CoveredPathd很小，最大速度就很小，dp即可[crayon-674300c11d95b063253340/]「cf534C」Polycarpus'Dice对于每个骰子，得出其它骰子的和sum则它的最小值为A-sum，最大值为A-n+1[crayon-674300c11d961099999058/]「cf534D」Handshakes尽量大的能处理则处理[crayon-674300c11d965277057499/]「cf534E」BerlandLocalPositioningSystem非...
02015年4月13日3,486递推与动规,贪心,深度搜索,构造,状压动规
「CF526X」ZeptoLab Code Rush 2015
懒得开多篇了，深夜口胡TAT现在是凌晨4点。。。A：KingofThieves枚举起始点模拟[crayon-674300c11defc684667751/]B：OmNomandDarkPark算出最大值，从最高层开始贪心，能加尽量加[crayon-674300c11df04558754481/]C：OmNomandCandies设hb/wb为小于ha/wa即a的单位质量价值高分类讨论若wb很大，则可以枚举b取了多少个否则a取的数量一定与c/wa相差不超过wb分类暴力TAT[crayon-674300c11df09044937394/]D： OmNom...
32015年4月5日3,378模拟,贪心,二分法,哈希表,调和级数
「East!_XVI」不祥之刃
Background卡特琳娜又要怒拿五杀了,怎么办啊?某无良设计师伊泽瑞尔笑了笑:“基兰,断网,重赛!”Description卡特琳娜要从1到N依次通过这N个李青[小学僧/盲僧],并最终击杀第N+1个李青[Dopa僧]。对于[小学僧],卡特琳娜可以击杀他得到一点法强和数量等同于该[小学僧]权值的金币;对于[盲僧],如果卡特琳娜当前法强大于等于该[盲僧]的权值,就会被该[盲僧]击杀。现在卡特琳娜要击杀[Dopa僧],就必须得到大于等于其权值的法强。问卡特琳...
02015年4月4日3,210贪心,STL
「BC35」DZY Loves Topological Sorting
问题描述一张有向图的拓扑序列是图中点的一个排列，满足对于图中的每条有向边(u→v)从u到v，都满足u在排列中出现在v之前。现在，DZY有一张有向无环图(DAG)。你要在最多删去k条边之后，求出字典序最大的拓扑序列。输入描述输入有多组数据。(TestCase≤5)第一行，三个正整数n,m,k(1≤n,m≤105,0≤k≤m).接下来m行，每行两个正整数u,v(u≠v,1≤u,v≤n),代表一条有向边(u→v).输出描述对于每组测试数据，输出一行字典序最大的拓...
02015年3月30日3,269STL,贪心,拓扑排序
「BZOJ3850」ZCC Loves Codefires
DescriptionThoughZCChasmanyFans,ZCChimselfisacrazyFanofacoder,called"Memset137".ItwasonCodefires(CF),anonlinecompetitiveprogrammingsite,thatZCCknewMemset137,andimmediatelybecamehisfan.Butwhy?BecauseMemset137cansolveallprobleminrounds,withoutunsuccessfulsubmissions;hisestimationoftimetosolvecertainproblemissoaccurate,thathecansurelygetanAcceptedthesecondhehaspredicted.Hesoon...
02015年3月23日2,990贪心
「CF529B」Group Photo 2(online mirror version)
Manyyearshavepassed,andnfriendsmetatapartyagain.Technologieshaveleapedforwardsincethelastmeeting,cameraswithtimerappearedandnowitisnotobligatoryforoneofthefriendstostandwithacamera,and,thus,beingabsentonthephoto.Simplyspeaking,theprocessofphotographingcanbedescribedasfollows.Eachfriendoccupiesarectangleofpixelsonthephoto:thei-thoftheminastandingstateoccupiesawipixelswideandahipixelshighrectang...
02015年3月23日2,633贪心,STL