NOIP2014 行记

不知道OI是啥或者信息学竞赛是啥的可以按Ctrl+W

很早开始写的。。准备出分之后再发布。

谨以此文纪念我信息学竞赛的第一次正式考试。

考前一些天写的:

11.5

下午想转发一下去年的RP++的说说。发现去年没有发(或被删?)。。

真想认识一下heoi群里其他学校那些人。

晚上回忆了回忆去年noip的作死种种。发现新高一的比我们去年厉害多了。

11.7

上午吃完早饭发现过了上学的点了,于是就又没去。

下午去河北师大试机。

Continue reading “NOIP2014 行记”

素数筛法

埃氏筛法:从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 故乡的梦”

这几天做的POI的题

正规、严谨、精妙。 -POI


发现POI(波兰信息学奥赛)的题都很有意思。于是开刷bzoj上的poi题目(按ac人数降序。。)。顺手写一写题解,加深印象。


BZOJ 1103 : [POI2007]大都市meg

给一棵树,每次可以把树上的一些边标记了,问一个点与根之间需要走多少没有标记的边。

这个可以把这颗树遍历得到一个dfs序每第一次经过一个点的时候记录为+1,第二次经过一个点的时候记录为-1,然后记录每个点第一次经过时在序列里的位置f[i]和第二次经过在序列里的位置l[i],对于查询(x)就是序列中一直到f[x]-1的前缀和,因为真正没走的那些边都+1 -1消掉了,只剩下真正要统计的边了。对于每次标记(a,b) 设a < b 就是序列里 f[b]的位置-1,l[b]的位置+1,就相当于消掉了这条边。另外这道题得手写栈dfs,否则会爆栈。

Continue reading “这几天做的POI的题”

白书第五章(网络流)练习题

一切皆可网络流

图论题,转化到常见模型才是最重要的。


网络流

花了点时间把白书的网络流例题、习题都做了,覆盖的挺全的,主要是建图的技巧吧。
一些简单的题解。


例题:

uva 11248 Frequency Hopping

网络扩容,bzoj上有一道类似的题,就是每次扩展最小割的边,看看够不够。两个优化:

一个是直接在残余网络内增广,一个是不用求最大流,当增广到C就不用增广了。忘记将belong置0,wa了一次。

Continue reading “白书第五章(网络流)练习题”

中考一周年纪念

“很难想象自己一年后的样子呢。”


如果没记错,一年前的今天应该是中考的日子,当时考完感觉很爽。(考完很爽的考试这辈子应该也没几次。) 过了几天后得知happyending,然后就玩了一个暑假,去了好多地方。

时间过得好快呢~

来省理科实验班也一年了吧,现在依然是天天被虐的感觉。

刚开学的时候老师说高一会过得很快,现在看应该是真的。


学OI也有一段时间了,从原来的非常弱变到了现在的很弱。(也是一种进步呢。)

学了许多神奇的算法,认识了许多人,达到了自己想象不到的打字速度。除了这些,收获应该还有许多。


中考,高考。“你觉得对自己很重要的考试,对别人来说也许就只是几天假。”

以上。

每天都对自己充满信心。