动态规划 - Page 3

「CF685X」Codeforces Round #360 (Div. 1)
A.NP-HardProblem二分图染色[crayon-6863812fb22ca826894756/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-6863812fb22d4374673214/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-6863812fb22d9564507930/] ...
02016年6月30日2,273背包动规,二分图染色,最大公约数与最小公倍数

2014PKU计算概论入学测试
poj1961Periodkmp求出fail数组后，前i个的重复子串就是i-fail(i)[crayon-6863812fb2722991994261/]poj1276 CashMachine用f(i,j)表示前i种面值，达到j的面值和，所需要的第i种钞票的最少数量[crayon-6863812fb272c553685761/]poj1702 Eva'sBalance先把n转为3进制，若p位为2，就在左盘放3^p，进位若p位为1，就在右盘放3^p[crayon-6863812fb2731611773084/]poj1273 DrainageDitches大名鼎鼎的草地排水，网络流模板[crayon-6...
42016年6月30日5,330递推与动规,KMP,最大流,后缀数组
2013PKU计算概论入学测试
OpenJ_Bailian3254.约瑟夫问题2模拟，用vector比较方便[crayon-6863812fb33fe038356710/]poj2393.Yogurtfactory求出将酸奶保存到某一天的最小代价贪心[crayon-6863812fb3407979206369/]poj1321.棋盘问题回溯裸题[crayon-6863812fb340b538671188/]poj2576.TugofWarf(i,j,k)表示前i个选j个能不能凑成k，第一维滚动[crayon-6863812fb3412427446508/]poj1974.RebuildingRoads用f(i,j)表示子树i，剩j个结点需要至少删多少条边[c...
22016年6月28日4,384模拟,贪心,深度搜索,树形动规
Codeforces Round #359 (Div. 1)
A.Robbers'watch可以先算出n-1,m-1所需的位数如果位数和超过7，根据抽屉原理，则一定会存在相同的数字特判一下输出0后，位数小等于7的情况暴力即可枚举i<n,j<m，七进制拆分一下看有没有相同数字[crayon-6863812fb4670092481106/]B.KayandSnowflake题意是询问一棵树某些子树的重心树的重心定义为，删去这个结点后，剩下的连通块大小不超过1/2*（总结点数）用yi表示x结点的儿子预处理size[x]和mx[x]表示树的大小，yi树的最...
32016年6月24日4,052树形动规
「NOI联考by ysy」庆典
「题目描述」战狂在昌和帝国的首都法法城召开了庆典，向一万名最杰出的士兵分发了用魔法猪做的猪肉饺子，士兵们吃了猪肉饺子后，战斗力大幅提高。为了保护战狂的安全以及维护现场秩序，大预言家抽调了n名普通士兵组成了m个小队完成一些不同的任务。由于一些特殊的原因，所有小队的人数都互不相同。你需要求出有多少种可能的组队方案。注意士兵是相同的，而小队是不同的。「输入数据」第一行两个个整数n，m。「输出数据」一行一个数...
02016年6月17日3,669递推与动规
「JoyOI1520」树的直径
描述Description树的直径，即这棵树中距离最远的两个结点的距离。每两个相邻的结点的距离为1，即父亲结点与儿子结点或儿子结点与父子结点之间的距离为1.有趣的是，从树的任意一个结点a出发，走到距离最远的结点b，再从结点b出发，能够走的最远距离，就是树的直径。树中相邻两个结点的距离为1。你的任务是：给定一棵树，求这棵树中距离最远的两个结点的距离。输入格式InputFormat输入共n行第一行是一个正整数n，表示这棵树的结点...
22016年6月15日6,572树形动规,广度搜索
「小奇模拟赛」[BZOJ3576] 小奇的博弈2
「题目背景」小奇和提比开脑洞又发明了新的游戏。「问题描述」给定一个数字F，游戏系统产生T组游戏。每组游戏包括n堆糖果，小奇和提比轮流操作。每次操作时，一方将某一堆数量不小于F的糖果分成M堆(M>=2且每次可以不同），要满足M堆中任意两堆糖果的差值不超过1，且不存在空堆。若一方不能操作，它就输了。假设提比和小奇都非常机智，小奇先手，请你预测一下游戏的结果。「输入格式」第一行有2个整数T，F接下来T行，每...
02016年5月21日4,778博弈论,记忆化搜索
「CF666X」 Codeforces Round #349 (Div. 1)
A.ReberlandLinguistics此题最重要的是理解题意！！！英语渣伤不起给定一个字符串，先去掉一个长度至少为5的前缀，要求把剩下的字符串划分成长度为2或3的串，这些串相邻之间不能完全相同，问可能有哪些长度为2或3的串看错题意就写了个哈希+搜索一直wa，后来领悟了就没另起炉灶，改成了牵强的记搜大概和dp差不多意思，f[i][0/1]表示前i个字符，最后一个串长度为2/3是否可行，转移显然。。。[crayon-6863812fedd8b462645016/]B.W...
02016年5月1日4,473广度搜索,记忆化搜索
Manthan, Codefest 16
A.EbonyandIvory给定a，b，c求一组整数解x，y使得x*a+y*b=c题解数据范围很小暴力枚举x[crayon-6863812fee232922326588/]B.ATrivialProblem求n！有多少个0题解暴力求n！被多少个2和5整除[crayon-6863812fee23b791863136/]C.SpySyndrome2给定长为（n<=10000）的主串，给（m<=100000）个长不超过1000的子串，总长不超过1000000求一个主串由子串的反串拼出的解法题解求每个子串的哈希值，主串每位枚举串长<=1000，求...
142016年3月6日4,650STL,树形动规
「CF618X」Wunder Fund Round 2016 (Div. 1 + Div. 2 combined)
A.SlimeCombining模拟或二进制拆分[crayon-6863812fefe43527189929/]B.GuessthePermutation第i行出现的最多的数就是数列中pi的值[crayon-6863812fefe4c454198727/]C.Constellation选一条任意直线上最近的两点，和离该直线最近的点[crayon-6863812fefe52729310386/]D.HamiltonianSpanningTree菊花图特判x>=y直接输出(n-1)*y否则树形dp或贪心求出最少要用的非树边数[crayon-6863812fefe57037711578/] ...
02016年2月4日4,514模拟,构造,树形动规,几何
「CF611X」Good Bye 2015
智商基本已经放弃我了，身败名裂后的题解。因为太弱加上是个高三狗，所以就只有ABCD了QAQA.NewYearandDays求2016年有多少个星期n求2016年有多少个月有n号可以算好答案输出[crayon-6863812ff0341144336308/]B.NewYearandOldProperty求L-R中有多少十进制数转为二进制只有1个0枚举0在哪一位，然后再枚举1的个数[crayon-6863812ff034b987873026/]C.NewYearandDomino求一个子矩形有多少种放置1*2的方式二维前缀和...
102016年1月2日4,237模拟,递推与动规,二分法,哈希表
「省选模拟赛」[BZOJ1556] 小奇走迷宫
原题：「bzoj1556」墓地秘密「题目背景」小奇驾驶G-1500机器人探险时落入了一个有魔法的迷宫，一旁的木牌上写着：“你可以回头，但你永远无法离去。”「问题描述」木牌下方有一行小字：“撞击所有机关墙”。G-1500机器人每次可以朝着前方光速移动，质量、动能无穷大，可以选择自己在行进中停下来或者撞墙后停下来，移动时只有转向需要花费时间。真是个诡异的迷宫，不过，小奇的眼前已经出现了迷宫的地图，它想尽早离开这里，请你...
22015年12月19日7,728spfa,状压动规