算法 - Page 47 - hzwer.com

「BZOJ1567」[JSOI2008] Blue Mary的战役地图
DescriptionBlueMary最近迷上了玩Starcraft(星际争霸)的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。由于BlueMary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此BlueMary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。具体来说...
12014年11月13日4,717二分法,哈希表

「BZOJ2730」[HNOI2012] 矿场搭建
Description煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。Input输入文件有若干组数据，每组数据的第一行是一个正整数N（N≤500）...
12014年11月13日6,287图的连通
「BZOJ2734」[HNOI2012] 集合选数
Description《集合论与图论》这门课程有一道作业题，要求同学们求出{1,2,3,4,5}的所有满足以下条件的子集：若x在该子集中，则2x和3x不能在该子集中。同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数n≤100000，如何求出{1,2,...,n}的满足上述约束条件的子集的个数（只需输出对1,000,000,001取模的结果），现在这个问题就交给你了。Input 只有一行，其中有一个正整数n，30%的数据满足n≤20。O...
62014年11月13日6,801状压动规
「BZOJ1193」[HNOI2006] 马步距离
DescriptionInput只包含4个整数，它们彼此用空格隔开，分别为xp,yp,xs,ys。并且它们的都小于10000000。Output含一个整数，表示从点p到点s至少需要经过的马步移动次数。SampleInput1279SampleOutput5题解大范围贪心，然后小范围暴力[crayon-684d1e768ad8b749022530/] ...
22014年11月13日5,715贪心,广度搜索
「BZOJ2659」[BJ WC2012] 算不出的算式
Description算不出的算式背景：曾经有一个老掉牙的游戏放在我面前，我没有珍惜。直到这个游戏停产才追悔莫及。人世间最痛苦的事情莫过于此，如果上天给我一个再玩一次的机会，我一定要，通关！题目描述：如果你真的很想玩这个游戏，那么就先看看我的题目吧，搞不定这些的话是没办法通关的哟。第一关其实很简单，只有一个关闭的有密码锁的大门。这大门上写着一个奇怪的算式，估计是要你利用它算出密码来开门吧（果然是老掉牙的情节...
02014年11月12日3,485其它
「考后欢乐赛」最小公倍数
题目描述给定两个正整数，求他们的最小公倍数。样例输入2812样例输出84数据范围对于40%数据：1<=a,b<=10^9对于60%的数据：1<=a,b<=10^12对于100%数据：1<=a,b<=10^100 提示：为了略微降低题目难度，增加以下条件：输入数据保证a>=b输入数据保证a、b没有前导0输入数据保证除了在两个正整数a、b之间的空格和行末换行符以外，不存在其他非数字字符最后友情提醒：高精除高精写二分做法风味更佳对...
02014年11月12日5,024高精度,最大公约数与最小公倍数
「BZOJ1978」[BJ2010] 取数游戏 game
Description小C刚学了辗转相除法，正不亦乐乎，这小P又出来捣乱，给小C留了个难题。给N个数，用a1,a2…an来表示。现在小P让小C依次取数，第一个数可以随意取。假使目前取得aj，下一个数取ak(k>j)，则ak必须满足gcd(aj,ak)≥L。到底要取多少个数呢？自然是越多越好！不用多说，这不仅是给小C的难题，也是给你的难题。Input第一行包含两个数N和L。接下来一行，有N个数用空格隔开，依次是a1,a2…an。Output仅包含一行...
02014年11月12日3,590其它
「CF486D」Valid Sets
Asyouknow,anundirectedconnectedgraphwithnnodesandn - 1edgesiscalledatree.Youaregivenanintegerdandatreeconsistingofnnodes.Eachnodeihasavalueaiassociatedwithit.WecallasetSoftreenodesvalidiffollowingconditionsaresatisfied:Sisnon-empty.Sisconnected.Inotherwords,ifnodesuandvareinS,thenallnodeslyingonthesimplepathbetweenuandvshouldalsobepresentedinS..Yourtaskistocountthenumberofvalidsets.S...
02014年11月12日3,796树形动规
「CF486C」Palindrome Transformation
Namisplayingwithastringonhiscomputer.ThestringconsistsofnlowercaseEnglishletters.Itismeaningless,soNamdecidedtomakethestringmorebeautiful,thatistomakeitbeapalindromebyusing4arrowkeys:left,right,up,down.Thereisacursorpointingatsomesymbolofthestring.Supposethatcursorisatpositioni(1 ≤ i ≤ n,thestringuses1-basedindexing)now.Leftandrightarrowkeysareusedtomovecursoraroundthestring.Thestri...
02014年11月12日3,263贪心
「CF486B」OR in Matrix
Let'sdefinelogicalORasanoperationontwologicalvalues(i.e.valuesthatbelongtotheset{0, 1})thatisequalto1ifeitherorbothofthelogicalvaluesissetto1,otherwiseitis0.WecandefinelogicalORofthreeormorelogicalvaluesinthesamemanner:whereisequalto1ifsomeai = 1,otherwiseitisequalto0.NamhasamatrixAconsistingofmrowsandncolumns.Therowsarenumberedfrom1tom,columnsarenumberedfrom1ton.Elementatrowi(1 ≤ ...
02014年11月12日2,529其它
「CF486A」Calculating Function
Forapositiveintegernlet'sdefineafunctionf:f(n) = - 1 + 2 - 3 + .. + ( - 1)nnYourtaskistocalculatef(n)foragivenintegern.InputThesinglelinecontainsthepositiveintegern(1 ≤ n ≤ 1015).OutputPrintf(n)inasingleline.Sampletest(s)input[crayon-684d1e768ceb6802146930/]output[crayon-684d1e768cebe583732731/]input[crayon-684d1e768cec1305561223/]output[crayon-684d1e768cec4300629542/]N...
02014年11月12日2,832其它
「BZOJ3555」[Ctsc2014] 企鹅QQ
DescriptionPenguinQQ是中国最大、最具影响力的SNS（SocialNetworkingServices）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。小Q是PenguinQQ网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析，小Q发现同一个人注册的账户名称总是很相似的，例如Penguin1，Penguin2，P...
82014年11月11日6,497哈希表