下一页 »Current position : 首页 >> 贪心
2018-2019 NOIP课件 by hzwer
分享一下这两年做的课件链接:https://pan.baidu.com/s/1DUUkwBrAE5tH1lFvNSkocQ提取码:2vfp
「CF1240X」Codeforces Round #591
A.SavetheNature二分答案，计算一下x%y%(x+y)%的票的数量，贪心地让贵的比例最高[crayon-5da93a84d2d54181486237/]B.SequenceSorting离散化以后，则不用移动的数的数值是连续的一段，递推一下最长连续的序列，或者双指针实现[crayon-5da93a84d2d62089327113/]C.PainttheTree每个点只能选择不超过𝑘个相连的边，dp一下，f[x]表示选了x和其父亲的边，g[x]表示没选转移的时候，贪心选收益前k大的边[crayon-5da93a84d2d6a121...
「CF1228X」Codeforces Round #589
A.DistinctDigits模拟判定每个数[crayon-5da93a84d42ea730325607/]B.FillingtheGrid首先按照要求染黑，check一下是不是合法的恰好达到要求的后一个格子一定是白色，再往后的格子就黑白都行，算一个2的幂次[crayon-5da93a84d42f4030056974/]C.PrimesandMultiplication对于每一个x质因子p，n以内有n/p个它的倍数，有n/(p^2)个p^2的倍数，统计一下，最后快速幂[crayon-5da93a84d42fa217820994/]D.CompleteTripartite贪心，...
「CF1220X」Codeforces Round #586
A.Cards统计一下z和o的个数[crayon-5da93a84d4802429629805/]B.MultiplicationTable取第一行的gcd，则a1一定是gcd的约数再取一个M23，确定一下a1[crayon-5da93a84d480c909334997/]C.SubstringGameintheLesson先手可以直接转移到左边的最小字符[crayon-5da93a84d4811812313479/]D.AlexandJulian按每个数的2的因子数分类，只有2的因子数相同的才能共存选择最多数的一类[crayon-5da93a84d4816690306540/]E.Tourism按起...
「CF1209X」Codeforces Round #584
A.PainttheNumbers从小到大排序以后，每次贪心的把能被最小元素整除的划分到一起[crayon-5da93a84d4d81170338990/]B.KoalaandLights因为ab都很小，枚举时间，暴力模拟灯的开关[crayon-5da93a84d4d8a442741040/]C.PainttheDigits枚举一下染色成1的最大值x，则比x小的都染色成1，再从右往左，直到第一个比x小的元素出现之前，把所有等于x的元素染色成1剩下的全染色成2，check一下是否合法[crayon-5da93a84d4d90701738947/]D...
「CF1214X」Codeforces Round #583
A.OptimalCurrencyExchange只有1美元和5欧元是有用的，直接枚举美元数即可通过[crayon-5da93a84d56e2545045167/]B.Badges枚举一下蓝色校徽的个数，并得出红色校徽的个数，这时判断一下有没有超过男女生人数[crayon-5da93a84d56eb509809219/]C.BadSequence我把这一题想复杂了。合法的括号序列判断方法是，把左括号看作+1，右括号看作-1，只要前缀和都大等于0就可以。当不合法的括号序列使得前缀和为-1时，只要把这个右括号...
「百度之星2017」程序设计大赛 初赛(B)
好气啊突然发现复赛的时候要军训1001.Chessf(i,j)表示最后一个棋放在(i,j)的方案[crayon-5da93a84d5cd1102593460/]1002.Factory把集合分为元素个数大于\(m=\sqrt{n}\)，和小等于m的对于元素个数很多的集合，每个集合bfs一次，预处理出到其它集合的距离如果询问的两个集合的元素个数都比较少，建一下虚树dp。。。我不慎误算复杂度把这里写成了记忆化搜索+暴力，结果还过了[crayon-5da93a84d5cdc977226798/]1005.度度熊的交易计划预...
2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)
E.Enclosure做出大小两个凸包，即所有点的凸包和前k个点的凸包按动态凸包的思路，新加入的点会把小凸包上连续的一些点弹出，这些点是一个连续的区间相当于切掉凸包的一个角，加入一个三角形若在大凸包上顺时针枚举一个加入的点，这个区间左右端点也是顺时针转的，类似旋转卡壳切掉部分的面积顺便维护由于坐标范围较大，用double精度会炸[crayon-5da93a84d6627218643178/]G.MaximumIslandsL的上下左右直接贪心为W然后剩下的就...
2017ACM萧山训练第4场(CTUO 2015)
D.FalconDive计算左下角的像素移动的距离，直接模拟[crayon-5da93a84d6c2a301795006/]F.TheFoxandtheOwl贪心如果n是负数，找n最低的非9的位加1考虑在n的某一个高位减1，在之后的低位中加2如果存在多个满足的高位，取最低的一个若不存在，构造一个绝对值最小的负数[crayon-5da93a84d6c36857917052/]J.JumpingYoshi两个点连边的条件是\(d_y-d_x=a_y+a_x,y>x\)由于点对不超过10^6，扫一遍用map维护，把所有的边用并查集连...
2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-5da93a84d72b4755831124/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-5da93a84d72be614999947/]D.Factors爆搜前16个素数[crayon-5da93a84d72cb138312827/]F.LowPower二分答案贪心检验[crayon-5da93a84d72d2944342950/]H:М...
2017ACM萧山训练第2场(NWERC 2008)
A:EquilibriumMobile最终天平平衡的状态下，每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数[crayon-5da93a84e1403188039799/]B:ProvingEquivalences答案是max{入度为0的连通块个数，出度为0的连通块个数}特判连通块为1的情况每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环[crayon-5da93a84e140f861291217/]C:Catvs.Dog找出所有相互不兼容的人，将他们连边...
2017 训练赛 1 by hzwer
「poj1054」TheTroublesomeFrog（恼人的青蛙）「poj1037」decorativefence「hdu2197」本原串「poj2112」OptimalMilkin「bzoj4010」[HNOI2015]菜肴制作「hdu2462」TheLuckiestnumber「bzoj3172」[Tjoi2013]单词「poj1054」TheTroublesomeFrog（恼人的青蛙）首先O(n^3)的算法是显然的，即枚举两个点，check一下这条路径上所有点，由于这道题时限放的比较宽，实际上图可以直接用二维的bool数组存下来网络上的题解大多...
Learning to Paint
近期评论