下一页 »Current position : 首页 >> 动态规划
「CF1242X」Codeforces Round #599 (Div. 1)
A.TilePainting对n做因式分解，如果n有超过一个质因数t，则答案是1，否则答案是t。因为两个质因数求gcd以后是1，则ax+by可以把所有格子染上。[crayon-6996e27fe59ff887039444/]B.0-1MST求补图的联通块个数，BZOJ1098原题。维护一个1-n的链表，表示有哪些点还没确定所在连通块。从1-n枚举点x，用bfs把与x同一连通块的点找出来，每次bfs只需要考虑还在链表里的点，这样每一条边要不然在原图中，要不然不在原图中使得某个点...
2018-2019 NOIP课件 by hzwer
分享一下这两年做的课件链接:https://pan.baidu.com/s/1DUUkwBrAE5tH1lFvNSkocQ提取码:2vfp
「CF1240X」Codeforces Round #591 (Div. 1)
A.SavetheNature二分答案，计算一下x%y%(x+y)%的票的数量，贪心地让贵的比例最高[crayon-6996e27fe6a07506263239/]B.SequenceSorting离散化以后，则不用移动的数的数值是连续的一段，递推一下最长连续的序列，或者双指针实现[crayon-6996e27fe6a10349409514/]C.PainttheTree每个点只能选择不超过𝑘个相连的边，dp一下，f[x]表示选了x和其父亲的边，g[x]表示没选转移的时候，贪心选收益前k大的边[crayon-6996e27fe6a17285...
「CF1220X」Codeforces Round #586
A.Cards统计一下z和o的个数[crayon-6996e27fe738b295754909/]B.MultiplicationTable取第一行的gcd，则a1一定是gcd的约数再取一个M23，确定一下a1[crayon-6996e27fe7394508803000/]C.SubstringGameintheLesson先手可以直接转移到左边的最小字符[crayon-6996e27fe739a763250181/]D.AlexandJulian按每个数的2的因子数分类，只有2的因子数相同的才能共存选择最多数的一类[crayon-6996e27fe739d528522969/]E.Tourism按起...
「CF1214X」Codeforces Round #583
A.OptimalCurrencyExchange只有1美元和5欧元是有用的，直接枚举美元数即可通过[crayon-6996e27fe78f3455362459/]B.Badges枚举一下蓝色校徽的个数，并得出红色校徽的个数，这时判断一下有没有超过男女生人数[crayon-6996e27fe78fc107488214/]C.BadSequence我把这一题想复杂了。合法的括号序列判断方法是，把左括号看作+1，右括号看作-1，只要前缀和都大等于0就可以。当不合法的括号序列使得前缀和为-1时，只要把这个右括号...
【LOJ】小奇 NOIP 练习题
可以在https://loj.ac/problems/tag/207AC这些题目小奇采药小奇取石子小奇的旅行计划小奇探险小奇采药对于30%的数据，\(O(2^n)\)枚举取or不取对于60%的数据，\(O(nm)\)做01背包，即\(f(i,j)\)表示前i株草药，耗费j的时间能达到的最大代价。对于100%的数据，注意到m,t,v纯随机那么不会选太多的草药，而耗时较少的草药有很大概率存在于最优解中针对这些性质优化搜索当然也可以合理使用随机化和卡时，复杂度O(玄学)小奇取石子在n...
算法设计与分析讨论班上机作业
凸包A:WallPOJ1113求凸包周长加一个圆[crayon-6996e27fe7f8d841765459/]B:ScrambledPolygonPOJ2007排序凸包上的点[crayon-6996e27fe7f99386070798/]动态规划G题真的坑A:Fourier’sLinesPOJ1923[crayon-6996e27fe7fa0410787953/]B:TourPOJ2677[crayon-6996e27fe7fa4171552064/]C:IncreasingSequencesPOJ1239[crayon-6996e27fe7faa747126099/]D:Charlie’sChangePOJ1787[crayon-6996e27fe7fb1667...
「百度之星2017」程序设计大赛 初赛(B)
好气啊突然发现复赛的时候要军训1001.Chessf(i,j)表示最后一个棋放在(i,j)的方案[crayon-6996e27fe87a1415307099/]1002.Factory把集合分为元素个数大于\(m=\sqrt{n}\)，和小等于m的对于元素个数很多的集合，每个集合bfs一次，预处理出到其它集合的距离如果询问的两个集合的元素个数都比较少，建一下虚树dp。。。我不慎误算复杂度把这里写成了记忆化搜索+暴力，结果还过了[crayon-6996e27fe87ab927991345/]1005.度度熊的交易计划预...
2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-6996e27fe91a0986848043/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-6996e27fe91aa422193291/]D.Factors爆搜前16个素数[crayon-6996e27fe91b7513545645/]F.LowPower二分答案贪心检验[crayon-6996e27fe91bd636932889/]H:М...
2017ACM萧山训练第2场(NWERC 2008)
A:EquilibriumMobile最终天平平衡的状态下，每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数[crayon-6996e27fe9c0b021903063/]B:ProvingEquivalences答案是max{入度为0的连通块个数，出度为0的连通块个数}特判连通块为1的情况每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环[crayon-6996e27fe9c1c782901213/]C:Catvs.Dog找出所有相互不兼容的人，将他们连边...
2017ACM萧山训练第1场(NEERC 2016)
队友做的题目我并不是非常懂。。。A.[Neerc2016]Abbreviation字符串模拟E.[Neerc2016]ExpecttoWait如果对于等待的人数维护一个关于时间的前缀和那么我们就得到了一个很长的前缀和序列，我们注意到初始车辆为x，实际上就是询问这个序列大于x的前缀和的和那么对于时间离散化以后，就是询问大于x的段的加权和对所有的段从小到大排序，依次处理[crayon-6996e2800e3ce353513871/]G.[Neerc2016]GameonGraph第二个人先手的状态...
程序设计实习实验班2017推荐习题
区间众数问题这题写莫队是最容易的，可以对于每种出现次数的数字维护一个堆，用于删除时维护答案[crayon-6996e2800ea2f390928253/]「BZOJ3659」WhichDreamedIt 神奇钥匙求以1为起点的欧拉回路的个数乘1的度数BESTtheorem[crayon-6996e2800ea3d337378793/]「bzoj4031」[HEOI2015]小Z的房间矩阵树定理推荐阅读算法合集之《欧几里得算法的应用》[crayon-6996e2800ea4c091076227/]POJ2373DividingthePath用dp(i)...
近期评论