算法 - Page 19 - hzwer.com

「CF538X」Codeforces Round #300
A.CuttingBanner枚举切掉中间部分匹配[crayon-678133089e11c665204938/]B.QuasiBinary用最少的只包含01的数凑出n每次贪心在非0位上取1[crayon-678133089e125706300894/]C.Tourist'sNotes根据每俩个的时间及高度差可计算答案[crayon-678133089e12b259804657/]D.WeirdChess暴力暴力暴力[crayon-678133089e130720403000/]E.DemiurgesPlayAgain考虑进入某个根，最终会取得子树第几小的叶子[crayon-678133089e136518075...
02015年4月27日6,766模拟,贪心,主席树,调和级数

「BZOJ3700」「FJ2014集训」发展城市
Description 众所周知，Hzwer学长是一名高富帅，他打算投入巨资发展一些小城市。Hzwer打算在城市中开N个宾馆，由于Hzwer非常壕，所以宾馆必须建在空中，但是这样就必须建立宾馆之间的连接通道。机智的Hzwer在宾馆中修建了N-1条隧道，也就是说，宾馆和隧道形成了一个树形结构。Hzwer有时候会花一天时间去视察某个城市，当来到一个城市之后，Hzwer会分析这些宾馆的顾客情况。对于每个顾客，Hzwer用三个数值描述他：（S，...
32015年4月26日5,117最近公共祖先
「BZOJ1478」Sgu282 Isomorphism
Description给定一个N个结点的无向完全图（任意两个结点之间有一条边），现在你可以用M种颜色对这个图的每条边进行染色，每条边必须染一种颜色。若两个已染色的图，其中一个图可以通过结点重新编号而与另一个图完全相同，就称这两个染色方案相同。现在问你有多少种本质不同的染色方法，输出结果modP。P是一个大于N的质数。Input仅一行包含三个数，N、M、P。Output仅一行，为染色方法数modP的结果。SampleInput3497S...
32015年4月25日4,807深度搜索,置换,快速幂
「POJ2154」Color
DescriptionBeadsofNcolorsareconnectedtogetherintoacircularnecklaceofNbeads(N<=1000000000).Yourjobistocalculatehowmanydifferentkindsofthenecklacecanbeproduced.YoushouldknowthatthenecklacemightnotuseupalltheNcolors,andtherepetitionsthatareproducedbyrotationaroundthecenterofthecircularnecklaceareallneglected.YouonlyneedtooutputtheanswermoduleagivennumberP.InputThefirstlineoftheinputisa...
02015年4月24日4,364置换,筛法,快速幂,欧拉函数
「POJ2409」Let it Bead
Description"LetitBead"companyislocatedupstairsat700CanneryRowinMonterey,CA.Asyoucandeducefromthecompanyname,theirbusinessisbeads.TheirPRdepartmentfoundoutthatcustomersareinterestedinbuyingcoloredbracelets.However,over90percentofthetargetaudienceinsiststhatthebraceletsbeunique.(Justimaginewhathappenediftwowomenshowedupatthesamepartywearingidenticalbracelets!)It'sagoodthingthatbracele...
02015年4月24日3,709置换,快速幂
「BZOJ2154」Crash的数字表格
Description今天的数学课上，Crash小朋友学习了最小公倍数(LeastCommonMultiple)。对于两个正整数a和b，LCM(a,b)表示能同时被a和b整除的最小正整数。例如，LCM(6,8)=24。回到家后，Crash还在想着课上学的东西，为了研究最小公倍数，他画了一张N*M的表格。每个格子里写了一个数字，其中第i行第j列的那个格子里写着数为LCM(i,j)。一个4*5的表格如下：1234522641036312154412420看着这个表格，Crash想到了很多可以思...
22015年4月24日6,487莫比乌斯反演
「BZOJ3624」[Apio2008] 免费道路
DescriptionInputOutputSampleInput572130451320531430121421 SampleOutput320430531121题解优先加1做生成树，得出必须添加的0的边反过来，将0的边加至K条，再放1的边[crayon-67813308a0483421977051/] ...
02015年4月24日5,429贪心,并查集
「BZOJ2811」[Apio2012] Guard
DescriptionInputOutputSampleInput534121341440451SampleOutput35HINT在这个样例中，有两种可能的安排方式：1，3，5 或者 2，3，5。即 3 和 5后面必然躲着一个忍者。考虑第一个灌木丛，存在一种安排方案使得它的后面躲着忍者，但也存在一种安排方案使得它后面没有躲忍者，因此不应该输出 1。同理，不应该输出 2。题解首先先将0的区间去除，可以用线段树TT如果去除0剩下的坐标编号等于忍者数，则所有剩下的坐标...
122015年4月24日7,732贪心,二分法,线段树
「BZOJ3676」[Apio2014] 回文串
Description考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。Input输入只有一行，为一个只包含小写字母(a-z)的非空字符串s。Output输出一个整数，为逝查回文子串的最大出现值。SampleInput「样例输入l」abacaba「样例输入2]wwwSampleOutput「样例输出l」7「样例输出2]4HINT一个串是回文的，当且仅当它从左到右读和从右到...
182015年4月23日11,221后缀自动机,manacher
「BZOJ4002」[JLOI2015] 有意义的字符串
Description B君有两个好朋友，他们叫宁宁和冉冉。有一天，冉冉遇到了一个有趣的题目：输入b;d;n，求((b+sqrt(D)/2)^N的整数部分，请输出结果Mod7528443412579576937之后的结果吧。Input一行三个整数b;d;nOutput 一行一个数表示模7528443412579576937之后的结果。SampleInput159SampleOutput76HINT 0<b^2<d<(b+1)2<10^18。题解http://blog.csdn.net/popoqqq/article/details/45148309为什么我不知道...
12015年4月23日4,825矩阵乘法
「BZOJ3990」[SDOI2015] 排序
Description 小A有一个1-2^N的排列A[1..2^N],他希望将A数组从小到大排序,小A可以执行的操作有N种,每种操作最多可以执行一次,对于所有的i(1<=i<=N),第i中操作为将序列从左到右划分为2^{N-i+1}段,每段恰好包括2^{i-1}个数,然后整体交换其中两段.小A想知道可以将数组A从小到大排序的不同的操作序列有多少个,小A认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同). 下面...
32015年4月23日6,066深度搜索
「BZOJ3210」花神的浇花集会
Description在花老师的指导下，每周4都有一个集会活动，俗称“浇水”活动。具体浇水活动详情请见BZOJ3153但这不是重点花神出了好多题，每道题都有两个参考系数：代码难度和算法难度花神为了准备浇花集会的题，必须找一道尽量适合所有人的题现在花神知道每个人的代码能力x和算法能力y，一道题（代码难度X算法难度Y）对这个人的不适合度为 Max(abs(X–x),abs(Y–y))也就是说无论太难还是太简单都会导致题目不适合做（...
02015年4月23日3,448其它