递推与动规 - Page 3

「CF261X」Codeforces Round #160 (Div. 1)
A.MaximandDiscounts挑要求最小的优惠方案啦，最贵的那几个显然要花钱买，赠品当然也是选最贵的。。。恩变成了子问题[crayon-5d5b699281d48359725794/]B.MaximandRestaurantf(i,j,k)表示前i个人，选了j个，消耗为k的方案数然后枚举选的人数+组合数学，注意不重复统计答案[crayon-5d5b699281d51631516651/]C.MaximandMatrix发现第m+1行的和就是2^(m二进制1的个数+1)则t是2的幂次才有解，求<=n的ans数量从大到小枚举每一...
32015年6月25日1,923递推与动规,贪心,深度搜索,排列组合

「CF332X」Codeforces Round #193 (Div. 2)
A.DowntheHatch!阅读+模拟题[crayon-5d5b699282678770664804/]B.MaximumAbsurdity每K个的和求出来以后，就是找距离超过K的两个数相加的最大值[crayon-5d5b699282681726183474/]C.Students'Revengehttp://m.blog.csdn.net/blog/u010638776/10044315[crayon-5d5b699282687187354097/]D.TheftofBlueprintswmd神犇：http://blog.csdn.net/wmdcstdio/article/details/44755115[crayon-5d5b69928268c603951231/]E.Binary...
02015年6月25日1,671递推与动规,模拟,堆,贪心,记忆化搜索
「CF360X」Codeforces Round #210 (Div. 1)
A.LevkoandArrayRecovery求出每个位置初始值的最大值，然后check一下[crayon-5d5b699282c73535813182/]B.LevkoandArray二分答案，f(i)表示前i个的最小修改次数，且i不修改，枚举上一个不修改的位置转移[crayon-5d5b699282c83092724970/]C.LevkoandStringsf(i,j)表示前i个字母，beauty值为j的合法方案，\(t_k=s_k\)(k>j)1.在第i位放一个比s[i]大的字母，枚举上一个位置i-k-1满足\(s_{i-k-1}!=t_{i-k-1}\)产生的新的bea...
12015年6月23日2,208递推与动规,贪心,spfa,二分法,最大公约数与最小公倍数
「CF335X」MemSQL start[c] up Round 2 – online version
A.Banana枚举sheet数，找到第一个不能用已有sticker凑出的[crayon-5d5b699283577692174457/]B.Palindromef(i,j)表示末尾在i之前，长度为j的回文序列的最大头位置[crayon-5d5b699283582931495074/]C.MoreReclamation用(len,x,y)表示一个游戏状态，2*len的完整格子，左端的状态为x，右端的状态为yx，y=0/1/2分别表示（完整），（左侧/右侧第一行第一格不可删），（左侧/右侧第二行第一格不可删）边界情况：len=0时sg值为0len=...
12015年6月23日1,998递推与动规,模拟,贪心,STL,博弈论,记忆化搜索,概率与期望
「百度之星」大搬家
ProblemDescription近期B厂组织了一次大搬家，所有人都要按照指示换到指定的座位上。指示的内容是坐在位置i上的人要搬到位置j上。现在B厂有N个人，一对一到N个位置上。搬家之后也是一一对应的，改变的只有位次。在第一次搬家后，度度熊由于疏忽，又要求大家按照原指示进行了一次搬家。于是，机智的它想到：再按这个指示搬一次家不就可以恢复第一次搬家的样子了。于是，B厂史无前例的进行了连续三次搬家。虽然我们都知道度度...
02015年6月8日1,267递推与动规
「百度之星」最强密码
ProblemDescription由于近来密码库被盗的现象层出不穷，度度熊决定为自己的账号找一个最强密码。在研究了密码库很久之后，它总结出了一个规律：密码库中的所有密码都是一个“密码生成串”的子序列（某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列）。经过强大的计算集群夜以继日的工作，度度熊得到了这个“密码生成串”。现在它希望找到一个“最强密码”，不是这个“密码...
32015年6月8日2,258递推与动规
PKUSC 2014 #2
A:QuadTiling对于某一层来说，状态只有6种，所以手推下转移方程，矩阵乘法加速即可[crayon-5d5b69929e398876510649/]B:Garden傻逼线段树[crayon-5d5b69929e3a8582687455/]D:One-movecheckmate枚举一下皇后能一步到达的位置，然后判一下是否将死注意细节较多具体见discuss[crayon-5d5b69929e3b4388149994/]E:ATP二分答案后，从比赛最后阶段往前考虑当然是每场给每个人分配一个可以打败的最NB的人。。。贪心判解的可行性...
02015年6月1日1,707模拟,递推与动规,贪心,线段树,二分法,矩阵乘法
usaco 刷水。。。
2017:[Usaco2009Nov]硬币游戏f(i,j)表示考虑最后i枚，前一次对手取j枚，自己的最大获益[crayon-5d5b69929e95c563913570/][Usaco2005Feb]RiggingtheBovineElection竞选划区爱怎么暴力怎么暴力[crayon-5d5b69929e966534569933/]1661:[Usaco2006Nov]BigSquare巨大正方形狗眼瞎了wa了n发。。。枚举一条边暴力即可[crayon-5d5b69929e96d846497613/]1654:[Usaco2006Jan]TheCowProm奶牛舞会有向图强连通分量。。。[crayon...
02015年5月26日1,963递推与动规,深度搜索,图的连通
POJ训练记录4
1694.AnOldStoneGamef[x]表示x为根的树至少需要的石头，把子树按f排序后贪心即可[crayon-5d5b69929eece077686692/]poj1738.AnoldStoneGame参见discuss的神算法，据说是knuth提出的？[crayon-5d5b69929eede992769210/]1737.ConnectedGraph跪大爷http://blog.csdn.net/PoPoQQQ/article/details/43525019[crayon-5d5b69929eee9829261849/]1742.Coins二进制拆分+bitset竟然过不了...我被题解骗了突然一想这不是以前做过...
02015年5月20日2,013模拟,递推与动规,贪心,背包动规,树形动规,几何,排列组合
POJ训练记录3
1379.RunAway模拟退火裸题[crayon-5d5b69929f4fd051965383/]2758.CheckingtheText暴力+哈希[crayon-5d5b69929f506175466534/]poj3156.Interconnect由于状态是满足拓扑序的，所以直接dp上，再用个hash记忆化[crayon-5d5b69929f50d206168408/]1837.Balancef(i,j)前i个力矩为j的方案,dp[crayon-5d5b69929f517280443298/]3609.ResetSequence状压+bfs初始集合是0-n-1每个指令会使得集合中的一些元素消失，目标状态是只有一个0[c...
02015年5月19日2,013递推与动规,广度搜索,状压动规,几何,哈希表,记忆化搜索,概率与期望
「CF507X」Codeforces Round #287 (Div. 2)
A.AmrandMusic排序贪心[crayon-5d5b69929fab4725837267/]B.AmrandPins算出距离除以直径[crayon-5d5b69929fabd854761483/]C.GuessYourWayOut!按位考虑[crayon-5d5b69929fac1056827321/]D.TheMathsLecture从后往前dpf(i,j,k)表示后i位，当前模为j，是否有后缀被K整除[crayon-5d5b69929fac6596079283/]E.BreakingGood广搜，选可用边最多的路径[crayon-5d5b69929facf354792117/] ...
02015年5月16日1,616递推与动规,模拟,贪心,广度搜索
PKUSC 2013 #1
poj2245.Lotto裸搜索[crayon-5d5b69929ffe8394837533/]poj2601.Simplecalculations推公式麻烦。。直接二分[crayon-5d5b69929fff1918449086/]poj1635.Subwaytreesystems树的同构，哈希[crayon-5d5b69929fff6715108001/]poj2419.Forests暴力即可[crayon-5d5b69929fffb958950004/]poj1717.Dominoesdp水题[crayon-5d5b6992a0001516134254/]poj2949.WordRings建图+分数规划[crayon-5d5b6992a0007483191964/] ...
02015年5月14日1,655递推与动规,spfa,深度搜索,二分法,并查集,哈希表