下一页 »Current position : 首页 >> 树形动规
「CF1240X」Codeforces Round #591 (Div. 1)
A.SavetheNature二分答案，计算一下x%y%(x+y)%的票的数量，贪心地让贵的比例最高[crayon-6975f3fe1128b809112775/]B.SequenceSorting离散化以后，则不用移动的数的数值是连续的一段，递推一下最长连续的序列，或者双指针实现[crayon-6975f3fe11295444033107/]C.PainttheTree每个点只能选择不超过𝑘个相连的边，dp一下，f[x]表示选了x和其父亲的边，g[x]表示没选转移的时候，贪心选收益前k大的边[crayon-6975f3fe1129c257...
「CF1220X」Codeforces Round #586
A.Cards统计一下z和o的个数[crayon-6975f3fe12bf7419798843/]B.MultiplicationTable取第一行的gcd，则a1一定是gcd的约数再取一个M23，确定一下a1[crayon-6975f3fe12c05347373850/]C.SubstringGameintheLesson先手可以直接转移到左边的最小字符[crayon-6975f3fe12c0f975003149/]D.AlexandJulian按每个数的2的因子数分类，只有2的因子数相同的才能共存选择最多数的一类[crayon-6975f3fe12c13895115471/]E.Tourism按起...
2017ACM萧山训练第1场(NEERC 2016)
队友做的题目我并不是非常懂。。。A.[Neerc2016]Abbreviation字符串模拟E.[Neerc2016]ExpecttoWait如果对于等待的人数维护一个关于时间的前缀和那么我们就得到了一个很长的前缀和序列，我们注意到初始车辆为x，实际上就是询问这个序列大于x的前缀和的和那么对于时间离散化以后，就是询问大于x的段的加权和对所有的段从小到大排序，依次处理[crayon-6975f3fe13256662736815/]G.[Neerc2016]GameonGraph第二个人先手的状态...
「CF718X」Codeforces Round #373 (Div. 1)
A.EfimandStrangeGrade给一个长为n的小数，有t次操作，每次可以让小数点后的某一位向前四舍五入问能最终能得到的最大的数题解考虑找到最前的一个大等于5的数字，从其开始考虑四舍五入如果四舍五入到小数点，将小数点去掉最后再处理一下整数位的进位问题[crayon-6975f3fe138d0002821380/]C.SashaandArray给定一个长度为n的数列an，有两种操作1、将L到R的加上X2、询问\(\sum_{L\leqi\leqR}F(a_i)\)题解考虑在线段树的每...
2013PKU计算概论入学测试
OpenJ_Bailian3254.约瑟夫问题2模拟，用vector比较方便[crayon-6975f3fe13ee8401971272/]poj2393.Yogurtfactory求出将酸奶保存到某一天的最小代价贪心[crayon-6975f3fe13ef1923515986/]poj1321.棋盘问题回溯裸题[crayon-6975f3fe13ef6476543140/]poj2576.TugofWarf(i,j,k)表示前i个选j个能不能凑成k，第一维滚动[crayon-6975f3fe13efb233088444/]poj1974.RebuildingRoads用f(i,j)表示子树i，剩j个结点需要至少删多少条边[c...
Codeforces Round #359 (Div. 1)
A.Robbers'watch可以先算出n-1,m-1所需的位数如果位数和超过7，根据抽屉原理，则一定会存在相同的数字特判一下输出0后，位数小等于7的情况暴力即可枚举i<n,j<m，七进制拆分一下看有没有相同数字[crayon-6975f3fe14868150982872/]B.KayandSnowflake题意是询问一棵树某些子树的重心树的重心定义为，删去这个结点后，剩下的连通块大小不超过1/2*（总结点数）用yi表示x结点的儿子预处理size[x]和mx[x]表示树的大小，yi树的最...
「JoyOI1520」树的直径
描述Description树的直径，即这棵树中距离最远的两个结点的距离。每两个相邻的结点的距离为1，即父亲结点与儿子结点或儿子结点与父子结点之间的距离为1.有趣的是，从树的任意一个结点a出发，走到距离最远的结点b，再从结点b出发，能够走的最远距离，就是树的直径。树中相邻两个结点的距离为1。你的任务是：给定一棵树，求这棵树中距离最远的两个结点的距离。输入格式InputFormat输入共n行第一行是一个正整数n，表示这棵树的结点...
Manthan, Codefest 16
A.EbonyandIvory给定a，b，c求一组整数解x，y使得x*a+y*b=c题解数据范围很小暴力枚举x[crayon-6975f3fe15b42515902795/]B.ATrivialProblem求n！有多少个0题解暴力求n！被多少个2和5整除[crayon-6975f3fe15b4b179823342/]C.SpySyndrome2给定长为（n<=10000）的主串，给（m<=100000）个长不超过1000的子串，总长不超过1000000求一个主串由子串的反串拼出的解法题解求每个子串的哈希值，主串每位枚举串长<=1000，求...
「CF618X」Wunder Fund Round 2016 (Div. 1 + Div. 2 combined)
A.SlimeCombining模拟或二进制拆分[crayon-6975f3fe16b14244488390/]B.GuessthePermutation第i行出现的最多的数就是数列中pi的值[crayon-6975f3fe16b22638952803/]C.Constellation选一条任意直线上最近的两点，和离该直线最近的点[crayon-6975f3fe16b2b666350894/]D.HamiltonianSpanningTree菊花图特判x>=y直接输出(n-1)*y否则树形dp或贪心求出最少要用的非树边数[crayon-6975f3fe16b35973905316/] ...
「BZOJ4203」「FJ2015集训」同桌的你
「问题描述」同桌的你(deskmate.cpp/c/pas)每学期最让人激动的时候莫过于换同桌了,没有一位学生不愿意和自己喜欢的同学坐在一起,度过一个愉快充实的学期。作为一位民主的教师,小A会收集每个学生的同桌意向作为参考,每个学生会向小A提交一个他(或她)理想中的同桌。小A希望他能够满足尽可能多的同学的要求,当然,每位同学只能有一个同桌。换句话说,小A希望能够出现尽可能多的同桌,满足同桌两人中存在着一个人,喜欢和另一个人为同桌...
POJ训练记录4
1694.AnOldStoneGamef[x]表示x为根的树至少需要的石头，把子树按f排序后贪心即可[crayon-6975f3fe35898082218383/]poj1738.AnoldStoneGame参见discuss的神算法，据说是knuth提出的？[crayon-6975f3fe358a9518752089/]1737.ConnectedGraph跪大爷http://blog.csdn.net/PoPoQQQ/article/details/43525019[crayon-6975f3fe358b5901551482/]1742.Coins二进制拆分+bitset竟然过不了...我被题解骗了突然一想这不是以前做过...
POJ训练记录2
3613.CowRelays求经过n条边的最短路，floyd+倍增QAQ[crayon-6975f3fe3606b495113016/]2728.DesertKing最优比率生成树分数规划[crayon-6975f3fe360a1889160178/]1639.PicnicPlanning带度数限制的最小生成树http://wenku.baidu.com/link?url=UKcnK1pZvaVwypQOrIFRTOPzM4edIlBmqvnZjZipGf2o_6u-aB1F2tFsMGdUQbA1O-96menmbgyxNoSoWKWBeJnr-RJKuG2yM4b6Jf7IvR3[crayon-6975f3fe360...
近期评论