动态规划 - Page 5

「CF317X」Codeforces Round #188 (Div. 1)
A.PerfectPair每次把小的那个变成两个的和，注意考虑负数[crayon-69604f5228692675897992/]B.Ants蚂蚁的活动范围不太大，所以依然是暴力QAQ[crayon-69604f522869d710611088/]C.Balance每次从缺水的地方出发，找一条能送水过来的路径a->b，要保证a是路径上符合要求的第一个容器运送量\(d=min(b_b-a_b,a_a-b_a)\)，找n次若没有容量限制，每次从b到a扫，找当前水量超过d的往b方向运由于有容量限制，把d拆成d/2和d-d/2分两...
12015年6月22日5,332构造,深度搜索,状压动规,博弈论

「CF325X」MemSQL start[c] up Round 1
A.SquareandRectangles模拟题[crayon-69604f5229d66787598330/]B.StadiumandGames\[(2^k-1)m+m(m-1)/2=n\]枚举k二分得出m[crayon-69604f5229d74304314403/]C.MonstersandDiamonds此题比较恶心QAQ求最短用个类似dijkstra的东西，如果一种u->{v}的转移所有mn[v]都确定了，把这个转移放进堆或者是某个转移的代价被更新了求最长用记忆化搜索，走出环就是inf[crayon-69604f5229d7d523294480/]D.Reclamation把图扩展成r...
12015年6月16日4,551STL,深度搜索,并查集,二分法,记忆化搜索
「CF293X」Croc Champ 2013 – Round 2
A.WeirdGame两个人都应该采取贪心策略根据规则，先取0而对方不取0则败，所以有1则取1，当然尽量取对方也是1的那些取0的时候同理，尽量取对方是1的那些我们模拟游戏进程得出两个人的最终序列比较即可[crayon-69604f525a094009536543/]B.DistinctPaths容易发现，n+m-1>K时是无解的，那么有解的棋盘就很小了，状压使用的颜色+dfs然而这样的状态还是太多，我们发现dfs到一个格子的时候，所有未在棋盘上出现的颜色并无差别，所...
22015年6月11日5,814贪心,深度搜索,数学,点分治,状压动规,概率与期望
「百度之星」大搬家
ProblemDescription近期B厂组织了一次大搬家，所有人都要按照指示换到指定的座位上。指示的内容是坐在位置i上的人要搬到位置j上。现在B厂有N个人，一对一到N个位置上。搬家之后也是一一对应的，改变的只有位次。在第一次搬家后，度度熊由于疏忽，又要求大家按照原指示进行了一次搬家。于是，机智的它想到：再按这个指示搬一次家不就可以恢复第一次搬家的样子了。于是，B厂史无前例的进行了连续三次搬家。虽然我们都知道度度...
02015年6月8日2,432递推与动规
「百度之星」最强密码
ProblemDescription由于近来密码库被盗的现象层出不穷，度度熊决定为自己的账号找一个最强密码。在研究了密码库很久之后，它总结出了一个规律：密码库中的所有密码都是一个“密码生成串”的子序列（某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列）。经过强大的计算集群夜以继日的工作，度度熊得到了这个“密码生成串”。现在它希望找到一个“最强密码”，不是这个“密码...
32015年6月8日4,070递推与动规
PKUSC 2014 #2
A:QuadTiling对于某一层来说，状态只有6种，所以手推下转移方程，矩阵乘法加速即可[crayon-69604f525b968854087234/]B:Garden傻逼线段树[crayon-69604f525b972710611046/]D:One-movecheckmate枚举一下皇后能一步到达的位置，然后判一下是否将死注意细节较多具体见discuss[crayon-69604f525b97a826379965/]E:ATP二分答案后，从比赛最后阶段往前考虑当然是每场给每个人分配一个可以打败的最NB的人。。。贪心判解的可行性...
02015年6月1日4,121递推与动规,模拟,贪心,二分法,线段树,矩阵乘法
usaco 刷水。。。
2017:[Usaco2009Nov]硬币游戏f(i,j)表示考虑最后i枚，前一次对手取j枚，自己的最大获益[crayon-69604f525bf49360183417/][Usaco2005Feb]RiggingtheBovineElection竞选划区爱怎么暴力怎么暴力[crayon-69604f525bf53964635843/]1661:[Usaco2006Nov]BigSquare巨大正方形狗眼瞎了wa了n发。。。枚举一条边暴力即可[crayon-69604f525bf5a219381830/]1654:[Usaco2006Jan]TheCowProm奶牛舞会有向图强连通分量。。。[crayon...
02015年5月26日4,758递推与动规,深度搜索,图的连通
POJ训练记录5
3074.Sudoku数独。。dancinglink经典题[crayon-69604f525c630157668414/]3252.RoundNumbers简单数位dpf(i,j,x,y)表示最高的i位，0比1多j个，是否已小于n，高位是否有1然后转移显然。。。[crayon-69604f525c642808962557/]1665.Biker'sTripOdometer阅读题[crayon-69604f525c64b325532151/]1930.DeadFraction丧心病狂。。枚举循环节[crayon-69604f525c64f150147727/]1970.TheGame[crayon-69604f525c655683518429/]1185.炮兵...
02015年5月25日5,096模拟,状压动规,数位动规
「CF512X」Codeforces Round #290 (Div. 1)
做了俩题就丧失了动力A.FoxAndNames建图完拓扑排序[crayon-69604f525cc66728627511/]B.FoxAndJumping记忆化暴力QAQ[crayon-69604f525cc71825598202/]
02015年5月24日4,101拓扑排序,记忆化搜索
PKUSC 2013 #2
A:TheSettlersofCatan枚举起点dfs[crayon-69604f525d1aa451746373/]B:Nim傻逼记忆化搜索我竟然清空错数组QAQ[crayon-69604f525d1b4804234744/]C:TraditionalBINGO纯阅读题[crayon-69604f525d1b9970108190/]D:TraditionalBINGO排序后广搜更新每个点能到达的最高点。。。一通乱搞感觉并查集也可以就是很麻烦？[crayon-69604f525d1bf064810824/] ...
02015年5月22日3,560深度搜索,广度搜索,博弈论,记忆化搜索
CERC 2012 填坑计划(4 / 11)
A-Kingdoms把所有破产状态状压dp[crayon-69604f525d788507778646/]C-Chemist'svows无聊的抄表题。。。[crayon-69604f525d792743696473/]H-Darts模拟题[crayon-69604f525d798223046920/]J-Conservation怀疑数据是不是有问题。。。贪心+拓扑排序[crayon-69604f525d7a1222723958/] ...
02015年5月22日4,447模拟,贪心,STL,状压动规,拓扑排序
POJ训练记录4
1694.AnOldStoneGamef[x]表示x为根的树至少需要的石头，把子树按f排序后贪心即可[crayon-69604f525ddd1678771932/]poj1738.AnoldStoneGame参见discuss的神算法，据说是knuth提出的？[crayon-69604f525de08743206906/]1737.ConnectedGraph跪大爷http://blog.csdn.net/PoPoQQQ/article/details/43525019[crayon-69604f525de12413276164/]1742.Coins二进制拆分+bitset竟然过不了...我被题解骗了突然一想这不是以前做过...
02015年5月20日5,041模拟,递推与动规,贪心,背包动规,树形动规,几何,排列组合