动态规划 - Page 8

「BZOJ1177」[Apio2009] Oil
Description采油区域Siruseri政府决定将石油资源丰富的Navalur省的土地拍卖给私人承包商以建立油井。被拍卖的整块土地为一个矩形区域，被划分为M×N个小块。Siruseri地质调查局有关于Navalur土地石油储量的估测数据。这些数据表示为M×N个非负整数，即对每一小块土地石油储量的估计值。为了避免出现垄断，政府规定每一个承包商只能承包一个由K×K块相连的土地构成的正方形区域。AoE石油联合公司由三个承包商组成，他们...
22015年4月8日6,924递推与动规

「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,615递推与动规,排列组合
「BZOJ3522」[POI2014] Hotel
Description有一个树形结构的宾馆，n个房间，n-1条无向边，每条边的长度相同，任意两个房间可以相互到达。吉丽要给他的三个妹子各开（一个）房（间）。三个妹子住的房间要互不相同（否则要打起来了），为了让吉丽满意，你需要让三个房间两两距离相同。有多少种方案能让吉丽满意？Input第一行一个数n。接下来n-1行，每行两个数x,y，表示x和y之间有一条边相连。Output让吉丽满意的方案数。SampleInput7125725235645SampleOutp...
02015年4月2日4,975树形动规
「NOIP模拟赛」小奇的仓库
原题：「East!_XI」第一个问题2015年10月4日hzwer改写了题面「题目背景」小奇采的矿实在太多了，它准备在喵星系建个矿石仓库。令它无语的是，喵星系的货运飞船引擎还停留在上元时代！「问题描述」喵星系有n个星球，星球以及星球间的航线形成一棵树。从星球a到星球b要花费[dis(a,b)XorM]秒。（dis（a,b）表示ab间的航线长度，Xor为位运算中的异或）为了给仓库选址，小奇想知道，星球i（1<=i<=n）到其它所有星球花费的时...
62015年3月30日5,771树形动规
「BZOJ1875」[SDOI2009] HH去散步
DescriptionHH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地点A走到给定地点B共有多少条符合条件的路径Input第一...
02015年3月28日5,055递推与动规,矩阵乘法
「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,534递推与动规
「BZOJ3208」花神的秒题计划Ⅰ
Description背景「backboard」： Memphis等一群蒟蒻出题中，花神凑过来秒题……描述「discribe」：花花山峰峦起伏，峰顶常年被雪，Memphis打算帮花花山风景区的人员开发一个滑雪项目。我们可以把风景区看作一个n*n的地图，每个点有它的初始高度，滑雪只能从高处往低处滑「严格大于」。但是由于地势经常变动「比如雪崩、滑坡」，高度经常变化；同时，政府政策规定对于每个区域都要间歇地进行保护，防止环境破坏。现在，滑雪...
02015年3月25日4,435记忆化搜索
「CFgym100541」ATM withdrawal
VinhworksforanATMmachinemanufacturingcompany.ThebasicfunctionalityofanATMmachineiscashwithdrawal.WhenauserrequestsacashwithdrawalofWVND(VietnameseDong),theATMhastodispenseNmoneynotessuchthattheysumuptoW.ForthenextgenerationofATMmachine,VinhisworkingonanalgorithmtominimizethenumberNofmoneynotesforeachcashwithdrawaltransaction.YourtaskistohelpVinhtodohisjobgiventhatthemon...
02015年3月14日3,105递推与动规
「CFgym100541」Treasure Box
Yourteamwasexploringanancientcity.Suddenlyyoufoundanoldscrollwith2integernumbersNandK,whichencryptsthesecretcodetoopenatreasurebox.ConsideringatransformationonanintegerXdescribedasfollows:X = X + X mod 100,thesecretcodecanbeobtainedbyapplyingtheabove-describedtransformationKtimessuccessivelytoN.InputTheinputfileconsistsofseveraldatasets.Thefirstlineoftheinputfilecontainsthenumb...
02015年3月14日3,069记忆化搜索
「BZOJ2796」[POI2012] Fibonacci Representation
DescriptionFib数列0,1,1,2,3,5,8,13,21。给出一个数字，用FIB数列各项加加减减来得到。例如10=5+519=21-217=13+5-11070=987+89-5-1InputInthefirstlineofthestandardinputasinglepositiveintegerisgiven（1<=P<=10）thatdenotesthenumberofqueries.ThefollowinglinesholdasinglepositiveintegerKeach1<=K<=10^17.OutputForeachqueryyourprogramshouldprintonthestandardoutputtheminimumnumberofFibona...
12015年3月12日3,848STL,记忆化搜索
「codechef」January Lunchtime 2015
Pieceofcake 统计每个字母出现次数，取最大值，判断其是否等于l/2[crayon-690bab8845ff7745978146/]Justmultiply 乘法快速乘即可，但乘方由于M过大。。使用欧拉函数降幂比较麻烦。。发现a^(10b+c)=(a^b)^10*a^c然后就能On算出表达式了^10可以看做常数[crayon-690bab8846002528078656/]Candidatewalk状压一下，转移显然[crayon-690bab884600b416034482/]Manybananas这一题比较有意思将宗族大小分为<=300和>300用数组统...
02015年3月1日4,318模拟,状压动规,树状数组,快速幂
「CF519X」Codeforces Round #294 (Div. 2)
「cf519A」AandBandChess模拟[crayon-690bab88465d8330880499/]「cf519B」AandBandCompilationErrors排序，双指针对比用个hash/map统计下元素出现次数[crayon-690bab88465e3930237694/]「cf519C」AandBandTeamTraining实际上答案是min(n,m,(m+n)/3)我分类讨论了TAT还是很好yy的[crayon-690bab88465e8491853465/]「cf519D」AandBandInterestingSubstringsa[i][j]表示前缀和为i，字母j为末尾的前缀数量每次查询...
12015年2月28日4,522模拟,STL,树形动规,树上倍增,最近公共祖先