素数筛法

埃氏筛法:从2开始,找到第一个没有被筛的数,把它标记为素数,然后把它的2倍、3倍……筛掉。
复杂度O(nlogn)

改进的埃氏筛法:从2开始,找到第一个没有被筛的数x,把它标记为素数,然后把它的x倍、x+1倍……筛掉。
复杂度O(nloglogn)

线性筛:保证每个数都被它的最小素因子筛掉。
复杂度O(n)

Continue reading “素数筛法”

组合游戏学习

  阅读了《由感性认识到理性认识——透析一类搏弈游戏的解答过程》、《解析一类组合游戏》、《组合游戏略述——浅谈SG游戏的若干拓展及变形》这三篇论文,对组合游戏以及SG函数有了更深的理解。这篇文章摘下了这三篇论文的部分重要内容,以及部分我对组合游戏的理解。


一些名词与约定:

  • 游戏:这里的游戏指的并不是平时玩的那些游戏(Dota2啥的),而是只一些如Nim取石子之类的“益智”组合游戏。并且,我们关注的不是游戏好不好玩,而是游戏有没有必胜策略。下文详细介绍。
  • 状态:用一些数字来表示的游戏进行中的一个局面。
  • 必胜状态:存在一种走法走到一个必败状态。
  • 必败状态:后继状态都为必胜状态。
  • 特别的在组合游戏中一个状态不是必胜状态就是必败状态。

组合游戏是满足以下一些性质的游戏:

Continue reading “组合游戏学习”

题解 BZOJ 2725 故乡的梦

这个题在bzoj上好像是个权限题,想做的可以去Vani的博客下载测试数据。
这里有题面。

简单叙述一下题意
给你一个n个点、m条边的带权无向图,S点和T点,询问Q次删一条给定的边的S-T最短路。

其中 1<=n,m,q<=200000

ps. 1.这个题网上好多解法都是错的。2.这个题数据范围很大。

先求S到每个点的距离ds[i]。如果ds[T]为inf的话,输出Q个无解好了。
然后再求每个点到T的距离dt[i]。(用堆优化的Dijkstra即可。)

Continue reading “题解 BZOJ 2725 故乡的梦”