递推与动规 - Page 5

「codechef」April Challenge 2015
BROKPHON模拟[crayon-674430330895c222543524/]CHEFLCM所有约数和[crayon-6744303308965603553494/]PIANO1暴力TT[crayon-6744303308969563192793/]CSEQl~r之间每个数的使用次数当作一个变量。。那么就相当于求方程组sigma(xi)(l<=i<=r)=n的非负整数解数。。然后就是排列组合求和[crayon-674430330896d904271052/]CARLOS先用并查集将能够相互转化的并在一起dpf(i,j)表示前i个末尾为j的最小改...
22015年4月12日4,882递推与动规,模拟,ST表,并查集,排列组合,乘法逆元

「BZOJ1177」[Apio2009] Oil
Description采油区域Siruseri政府决定将石油资源丰富的Navalur省的土地拍卖给私人承包商以建立油井。被拍卖的整块土地为一个矩形区域，被划分为M×N个小块。Siruseri地质调查局有关于Navalur土地石油储量的估测数据。这些数据表示为M×N个非负整数，即对每一小块土地石油储量的估计值。为了避免出现垄断，政府规定每一个承包商只能承包一个由K×K块相连的土地构成的正方形区域。AoE石油联合公司由三个承包商组成，他们...
22015年4月8日6,364递推与动规
「ch18」fff的诅咒
$「ch18」fff的诅咒$
背景06年的浙江考生还是很不服，于是我再水了一题。描述设A,B是两个非空集合，如果存在一法则f，使得对A中的每个元素按法则f在B中有唯一确定的元素与之对应，则称f为从A到B的映射，记作f:A→B，映射在数学及相关的领域经常等同于函数。设s是由1到n的所有正整数组成集合，定义映射f:A→B。已知n，求满足的映射f有多少个？这个数可能很大，你只需要给出答案对质数p取模的值即可。输入格式三个空格隔开的正整数n,k,p。输出格...
22015年4月3日3,269递推与动规,排列组合
「BZOJ1875」[SDOI2009] HH去散步
DescriptionHH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地点A走到给定地点B共有多少条符合条件的路径Input第一...
02015年3月28日4,626递推与动规,矩阵乘法
「BZOJ1962」模型王子
DescriptionInput输入数据共一行，两个整数N，K，用一个空格隔开，具体意义如题目中所述。Output输出数据共一行，为最少所需要的时间S。SampleInput53SampleOutput5HINT对于全部的数据，1<=K<=100，1<=N<=10^5题解http://wenku.baidu.com/link?url=o0CPVzuBDLJMt0_7Qph1T7TtdFOzu7O-apIpvaWbIYMz8ZWqBneGqI8LGtLdqpuK5fbQ_v-H01zHwPXDsPrioR5xjCDHjqJn_boYO...
02015年3月26日3,325递推与动规
「CFgym100541」ATM withdrawal
VinhworksforanATMmachinemanufacturingcompany.ThebasicfunctionalityofanATMmachineiscashwithdrawal.WhenauserrequestsacashwithdrawalofWVND(VietnameseDong),theATMhastodispenseNmoneynotessuchthattheysumuptoW.ForthenextgenerationofATMmachine,VinhisworkingonanalgorithmtominimizethenumberNofmoneynotesforeachcashwithdrawaltransaction.YourtaskistohelpVinhtodohisjobgiventhatthemon...
02015年3月14日2,887递推与动规
「BZOJ3036」绿豆蛙的归宿
Description随着新版百度空间的下线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为1/K。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？Input第一行:两个整数NM，代表图中有N个点、M条边第...
22015年2月27日5,360递推与动规,概率与期望
「fjWC2015」圣诞树
「题目描述」用m种颜色的彩球装点n层的圣诞树。圣诞树的第i层恰由l[i]个彩球串成一行，且同一层内的相邻彩球颜色不同，同时相邻两层所使用彩球的颜色集合不同。求有多少种装点方案，答案对p取模。只要任一位置上的彩球颜色不同，就算作不同的方案。「输入格式」第一行三个整数n,m,p，表示圣诞树的层数、彩球的颜色数和取模的数。接下来一行包含n个整数，表示l[i]。「输出格式」一个整数表示答案。「样例输入」321000312「样例输出」...
02015年2月4日3,693递推与动规,排列组合
「CF398B」Painting The Wall
Useraintadecidedtopaintawall.Thewallconsistsofn2tiles,thatarearrangedinann × ntable.Sometilesarepainted,andtheothersarenot.Ashewantstopaintitbeautifully,hewillfollowtherulesbelow.Firstlyuseraintalooksatthewall.Ifthereisatleastonepaintedcelloneachrowandatleastonepaintedcelloneachcolumn,hestopscoloring.Otherwise,hegoestostep2.Useraintachooseanytileonthewallwithuniformprobability.Ifthetil...
02015年2月1日4,041递推与动规,概率与期望
「CF83E」Two Subsequences
OnanITlessonValerastudieddatacompression.Theteachertoldaboutanewmethod,whichweshallnowdescribetoyou.Let{a1, a2, ..., an}bethegivensequenceoflinesneededtobecompressed.Hereandbelowweshallassumethatalllinesareofthesamelengthandconsistonlyofthedigits0and1.Let'sdefinethecompressionfunction:f(emptysequence) = emptystringf(s) = s.f(s1, s2) = thesmallestinlengthstring,whichhasoneofthepre...
292015年2月1日4,864递推与动规
「BZOJ3173」[TJOI2013] 最长上升子序列
Description给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？Input第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）OutputN行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。SampleInput3002Samp...
62015年1月29日8,097递推与动规,treap
「CF506A」Mr. Kitayuta, the Treasure Hunter
TheShusekiIslandsareanarchipelagoof30001smallislandsintheYutampoSea.Theislandsareevenlyspacedalongaline,numberedfrom0to30000fromthewesttotheeast.Theseislandsareknowntocontainmanytreasures.TherearengemsintheShusekiIslandsintotal,andthei-thgemislocatedonislandpi.Mr.Kitayutahasjustarrivedatisland0.Withhisgreatjumpingability,hewillrepeatedlyperformjumpsbetweenislandstotheeastaccordingtoth...
02015年1月19日3,362递推与动规