递推与动规 - Page 8

「NOIP模拟赛」小象涂色
题目描述：小象喜欢为箱子涂色。小象现在有c种颜色，编号为0~c-1；还有n个箱子，编号为1~n，最开始每个箱子的颜色为1。小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择[L，R]这个区间里的一些箱子（不选看做选0个），为之涂上随机一种颜色。若一个颜色为a的箱子被涂上b色，那么这个箱子的颜色会变成（a*b）modc。请问在k次涂色后，所有箱子颜色的编号和期望为多少？输入描述：第一行为T，表示有T组测...
02014年10月31日2,831递推与动规

「NOIP模拟赛」Incr
「题目描述」数列A1,A2,...,AN，修改最少的数字，使得数列严格单调递增。「输入格式」第1行，1个整数N第2行，N个整数A1,A2,...,AN「输出格式」1个整数，表示最少修改的数字「样例输入」3132「样例输出」1「数据范围」对于50%的数据，N≤10^3对于100%的数据，1≤N≤10^5,1≤Ai≤10^9题解暴力可以用f[i][j]表示前i个最后一个改为j的方案[crayon-664862eb59dd8097242582/]ai减去下标求最长上升子序列ans。。。答案是n-an...
02014年10月30日2,717递推与动规
「BZOJ2708」[Violet 1] 木偶
DescriptionInputOutputSampleInput121542893123256603595957351555951232448770813445055585961234566123345812334254922235261393814017SampleOutput00010001002221HINTSourcef[i]=f[j]+cal(j+1,i)cal(x,y)计算x-y互相匹配最多可扔掉几个枚举可以扔掉的数量k，判断剩下的能否相互匹配，不能返回k-1以及被扔掉的能否相互匹配，能匹配返回k-1[crayon-664862eb5a17d922181171/] ...
02014年10月26日3,068递推与动规,贪心
「NOIP模拟赛」土豪聪要请客
众所周知，聪哥(ndsf)是个土豪，不过你们不知道的是他的MZ和他的RMB一样滴多……某天土豪聪又赚了10^10000e的RMB，他比较开心，于是准备请客。他在自己在XX星上的别墅里面大摆酒席，想要邀请尽可能多的MZ来参加他的宴会。他将会同MZ一起坐在一个巨大的长方形桌子上。这个桌子能坐下的人数等于他的边长。聪哥要求他的桌子能够放进他的别墅，并且桌子的边必须与别墅的边界平行。给定别墅的平面图，请你求出聪哥最多可以...
32014年10月23日3,787递推与动规
「JoyOI1097」MM不哭
描述Description在一个数轴上,有n个MM(绝非恐龙!)在哭泣(5555~一直哭).tcboy也在这个数轴上,并恰好看到了这一幕,由于每个MM哭都会让tcboy损失一定的rp,于是tcboy有必要去安慰她们.(真命苦啊 T.T)开始时，tcboy站在k号MM的旁边.现在知道第i个MM哭泣每秒钟会使tcboy降低 w[i]的rp (单位rp/s).而tcboy的行走速度很慢只有1m/s .tcboy安慰MM的方式很特别(怎么安慰随便大家YY了..#@$%^%$#@),不需要花费时间.请计算tcb...
02014年10月22日2,413递推与动规
「BZOJ2091」The Minima Game
Description给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下，最终A的得分减去B的得分为多少。Input第一行一个正整数N(N<=1,000,000)，第二行N个正整数（不超过10^9）。Output一个正整数，表示最终A与B的分差。SampleInput3131SampleOutput2HINT第一次A...
02014年10月20日2,177递推与动规
「CF480C」Riding in a Lift
Imaginethatyouareinabuildingthathasexactlynfloors.Youcanmovebetweenthefloorsinalift.Let'snumberthefloorsfrombottomtotopwithintegersfrom1ton.Nowyou'reonthefloornumbera.Youareverybored,soyouwanttotakethelift.Floornumberbhasasecretlab,theentryisforbidden.However,youalreadyareinthemoodanddecidetomakekconsecutivetripsinthelift.Letussupposethatatthemomentyouareonthefloornumberx(initially,youwere...
02014年10月20日2,356递推与动规
「CF100506」Pachinko
PachinkoisaJapanesegameplayedforamusementandprizes,andissimilartopinball.Thegameisverysimple:youshootsmallmetalballsintothemachineandtheyfalldown,bouncingofftheobstaclesuntiltheyfallintoagate.Thegateintowhichyourballfallsdeterminesthewinnings.Sinceyoucanmoreorlessdeterminethecolumnintowhichtheballisdropped(bysettingitsinitialspeedanddirection),youcaninfluenceyourwinchances.Youaretocalculatey...
02014年10月18日2,873递推与动规
「CF478D」Red – Green Towers
Therearerredandggreenblocksforconstructionofthered-greentower.Red-greentowercanbebuiltfollowingnextrules:Red-greentowerisconsistingofsomenumberoflevels;Letthered-greentowerconsistofnlevels,thenthefirstlevelofthistowershouldconsistofnblocks,secondlevel—ofn - 1blocks,thethirdone—ofn - 2blocks,andsoon—thelastlevelofsuchtowershouldconsistoftheoneblock.Inotherwords,eachsuccessivelevelshould...
02014年10月17日3,697递推与动规
「CF477C」Dreamoon and Strings
Dreamoonhasastringsandapatternstringp.Hefirstremovesexactlyxcharactersfromsobtainingstrings'asaresult.Thenhecalculatesthatisdefinedasthemaximalnumberofnon-overlappingsubstringsequaltopthatcanbefoundins'.Hewantstomakethisnumberasbigaspossible.Moreformally,let'sdefineasmaximumvalueofoveralls'thatcanbeobtainedbyremovingexactlyxcharactersfroms.Dreamoonwantstoknowforallxfrom0to|s|where|s|denotest...
02014年10月13日4,515递推与动规
「BZOJ1023」[SHOI2008] cactus仙人掌图
Description如果某个无向连通图的任意一条边至多只出现在一条简单回路（simplecycle）里，我们就称这张图为仙人图（cactus）。所谓简单回路就是指在图上不重复经过任何一个顶点的回路。举例来说，上面的第一个例子是一张仙人图，而第二个不是——注意到它有三条简单回路：（4，3，2，1，6，5，4）、（7，8，9，10，2，3，7）以及（4，3，7，8，9，10，2，1，6，5，4），而（2，3）同时出现在前两个的简单回路里。另外，第三张图也...
22014年10月10日9,989递推与动规,单调队列,仙人掌
「BZOJ1093」[ZJOI2007] 最大半连通子图
DescriptionInput第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。接下来M行，每行两个正整数a,b，表示一条有向边(a,b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。Output应包含两行，第一行包含一个整数K。第二行包含整数CModX.SampleInput6620070603122113245664SampleOutput33HINT对于100%的数据，N≤100000,M≤1000000；对于100%的数据，X≤...
22014年10月8日7,222递推与动规,拓扑排序,图的连通