下一页 »Current position : 首页 >> 数学
「CF1246X」Codeforces Round #596 (Div. 1)
A.p-binary最终答案不超过logn，枚举答案i，找出n-i*p在二进制下1的个数[crayon-691e6e8fe743b042222960/]B.PowerProducts想了一个比较复杂的做法先把所有在10^10以内的，能表示成x^k的数存起来若k=2，对于每个数ai，把ai的平方因子除掉以后得到y，和它配对的数一定是y*t^2若k>2，10^10内x^k数至多2万个，枚举一个数，暴力找另一个和它配对的数比较简单的做法是，先把每个数做质因数分解，把指数取模k以后，找与它互补的数的...
「CF1242X」Codeforces Round #599 (Div. 1)
A.TilePainting对n做因式分解，如果n有超过一个质因数t，则答案是1，否则答案是t。因为两个质因数求gcd以后是1，则ax+by可以把所有格子染上。[crayon-691e6e8fe83f5140703540/]B.0-1MST求补图的联通块个数，BZOJ1098原题。维护一个1-n的链表，表示有哪些点还没确定所在连通块。从1-n枚举点x，用bfs把与x同一连通块的点找出来，每次bfs只需要考虑还在链表里的点，这样每一条边要不然在原图中，要不然不在原图中使得某个点...
2018-2019 NOIP课件 by hzwer
分享一下这两年做的课件链接:https://pan.baidu.com/s/1DUUkwBrAE5tH1lFvNSkocQ提取码:2vfp
「CF1228X」Codeforces Round #589
A.DistinctDigits模拟判定每个数[crayon-691e6e8fe8953513215459/]B.FillingtheGrid首先按照要求染黑，check一下是不是合法的恰好达到要求的后一个格子一定是白色，再往后的格子就黑白都行，算一个2的幂次[crayon-691e6e8fe895c865326203/]C.PrimesandMultiplication对于每一个x质因子p，n以内有n/p个它的倍数，有n/(p^2)个p^2的倍数，统计一下，最后快速幂[crayon-691e6e8fe8962963060208/]D.CompleteTripartite贪心，...
「CF1229X」Codeforces Round #588
A.MarcinandTrainingCamp若A觉得自己没有B强，B向A连边度数为0的点，是觉得自己比其它人都强的，把它们依此拓扑排序删除[crayon-691e6e8fe8e69060034356/]B.KamilandMakingaStream从一个点向上走，区间gcd单调下降，且最多变化log次可以用树上倍增维护区间gcd，枚举每个点往上二分跳，暴力统计答案更简单的做法是用vector维护一个点往上的不同gcd，以及它们贡献答案的次数，这个vector大小是logdfs暴力往儿子转移倍增：...
「CF1220X」Codeforces Round #586
A.Cards统计一下z和o的个数[crayon-691e6e8fe9397083752148/]B.MultiplicationTable取第一行的gcd，则a1一定是gcd的约数再取一个M23，确定一下a1[crayon-691e6e8fe93a5808881314/]C.SubstringGameintheLesson先手可以直接转移到左边的最小字符[crayon-691e6e8fe93af508362811/]D.AlexandJulian按每个数的2的因子数分类，只有2的因子数相同的才能共存选择最多数的一类[crayon-691e6e8fe93b4464050464/]E.Tourism按起...
2017ACM萧山训练第3场(World Final 2013)
A.Self-Assembly如果一个正方形有两条边a,b则a->op(b)b->op(a)，判图中是否有环，有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大[crayon-691e6e8fe9986105063104/]C.SurelyYouCongest只有最短路相同的会互相影响按最短路分组后跑c次最大流[crayon-691e6e8fe9990451848852/]D.Factors爆搜前16个素数[crayon-691e6e8fe999d742564341/]F.LowPower二分答案贪心检验[crayon-691e6e8fe99a6292748540/]H:М...
2017ACM萧山训练第2场(NWERC 2008)
A:EquilibriumMobile最终天平平衡的状态下，每个结点x满足w[x]*(2^dep[x])相等统计所有的w[x]*(2^dep[x])，答案是叶子数减去出现次数最多的个数[crayon-691e6e8fea525273315482/]B:ProvingEquivalences答案是max{入度为0的连通块个数，出度为0的连通块个数}特判连通块为1的情况每个连通块，出度0的点，向其它入度为0的连边，使得形成一个环[crayon-691e6e8fea532380104954/]C:Catvs.Dog找出所有相互不兼容的人，将他们连边...
2017ACM萧山训练第1场(NEERC 2016)
队友做的题目我并不是非常懂。。。A.[Neerc2016]Abbreviation字符串模拟E.[Neerc2016]ExpecttoWait如果对于等待的人数维护一个关于时间的前缀和那么我们就得到了一个很长的前缀和序列，我们注意到初始车辆为x，实际上就是询问这个序列大于x的前缀和的和那么对于时间离散化以后，就是询问大于x的段的加权和对所有的段从小到大排序，依次处理[crayon-691e6e8feaf2b417052167/]G.[Neerc2016]GameonGraph第二个人先手的状态...
程序设计实习实验班2017推荐习题
区间众数问题这题写莫队是最容易的，可以对于每种出现次数的数字维护一个堆，用于删除时维护答案[crayon-691e6e8feb505633112883/]「BZOJ3659」WhichDreamedIt 神奇钥匙求以1为起点的欧拉回路的个数乘1的度数BESTtheorem[crayon-691e6e8feb512977131215/]「bzoj4031」[HEOI2015]小Z的房间矩阵树定理推荐阅读算法合集之《欧几里得算法的应用》[crayon-691e6e8feb51b936634822/]POJ2373DividingthePath用dp(i)...
程序设计实习实验班2017作业(算法 作业19, 20, 21)
一些以前做过的就不再贴了AFunnyStoneGame发现每一堆的每个石子之间都是相互独立的[crayon-691e6e9008a0b074070270/]nnimn阶nim和，在二进制下，每一位求和后对(n+1)取模[crayon-691e6e9008a15529121076/]一个水水的序列在建操作树的过程中就能顺便维护信息每次新加入节点的时候维护一下这个点的倍增数组，询问的时候直接向上倍增[crayon-691e6e9008a1a990661675/]「poj1523」SPF求割点，并且求删去割点后的连通分量个数[cr...
2017 训练赛 1 by hzwer
「poj1054」TheTroublesomeFrog（恼人的青蛙）「poj1037」decorativefence「hdu2197」本原串「poj2112」OptimalMilkin「bzoj4010」[HNOI2015]菜肴制作「hdu2462」TheLuckiestnumber「bzoj3172」[Tjoi2013]单词「poj1054」TheTroublesomeFrog（恼人的青蛙）首先O(n^3)的算法是显然的，即枚举两个点，check一下这条路径上所有点，由于这道题时限放的比较宽，实际上图可以直接用二维的bool数组存下来网络上的题解大多...
近期评论