NOIp结束后，我开始给我们学校高一高二的同学进行选拔赛辅导，时间是从12月11日到2月底，主要讲解NOIp以外的知识。期末考试的日期是2月1日，以这个日期为分界点可以把辅导分成两个阶段。前一阶段全部进行知识讲解，讲到了组合数学。这个阶段一星期上三次课，每个星期总计大概有8到9个课时。讲到1月24日后大家就回去准备期末考试了。后一阶段是在寒假中了，上了两个星期，模拟考试和知识讲解交替进行。每一天大概6到7课时。
    我讲的进度飞快，下面所有的知识基本上是讲完了的，不算模拟考试的话总共用了20多天共70到80课时。当然，这些时间里包括了扯蛋，乱谈，和集体玩SC、CS、WWP的时间。记得有一天扯蛋扯了一个多小时。
    最后的结果不令人满意，因为这次重庆选拔赛的题目很怪，没有用到什么比NOIp高级一点的东西。因此，下面我整理的课程安排在实践上看还没有确切的最终效果可供参考。

    

    NOIp的知识点并不多，很多参考书上都有。但是NOIp之外的东西一下子就多了，想再要排出一份课程来就很麻烦了。比如，不少比较交叉的东西很不好归类。我的这份知识列表很多时候怎么看怎么不顺眼，有些重复，有些遗漏，有些归类混淆。这份列表只是一个参考，我强行地归一下类仅仅是因为课程的安排需要有一个顺序。这只是一个初步的尝试，很多科学性的问题值得思考。

    我收到过很多邮件，不少人问我想要参加NOI还需要哪些知识。需要的知识很多，列一张表出来的话需要经过仔细的思考。然后我就我仔细思考了一下。我发现，NOI需要的东西还真他妈的多。现在，我就把我想到的东西写在下面供大家参考。这里面没写贪心、分治之类的东西，因为它们里面不包含什么特别的知识点，只有一大堆题目。
    我预言这篇日志一定是访问量最高的，因为这里面关键字云集。若某人查资料找到这里来失望地发现其实只是一群关键字的话，我先给您说不是。

    OIBH上的牛人其实不多，真正牛的人很少上OIBH。像我这样的NOI菜鸟时常在想，什么时候能像集训队的那些牛一样研究一些更高级的东西。很多东西我都不会，比如线性时间构造后缀树，查找最大重复子串，HLPP也没有仔细研究过。但是，我仍然很想帮助更多的OI新手。我经常看到OIBH上很多人问问题却没有人回答或回答很简略，这并不是因为大牛们不会，而是它们没有时间来写冗长的分析讲解。网上相关的资料其实是很多的，不过能顺利理解英文的OIer似乎不占多数，一些中文讲解也有很多问题，有很多讲不清的地方。嗯，既然大牛们没有空写，那就把任务交给我吧。后来我就写了一些风格比较相近的长篇知识讲解，冠名“Matrix67的OI点滴”。前几天觉得这真他妈的形式化，然后把标题里的这句话都删了。还有很多东西我都想写，自己该写什么就写什么更自由一些，不用限制在一个自己规定的框架里。今后我打算继续写下去，仍然以大众化的、容易理解的、罗嗦的语言来描述各种算法。省选辅导让我把这些知识又回顾了一遍，很多东西更清晰了。我想按着下面的线索把我在辅导中讲的东西写下来，提供更多网络上不好找的资料。

时间复杂度（渐近时间复杂度的严格定义，NP问题，时间复杂度的分析方法，主定理）
排序算法（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）
数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）
指针（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）
按位运算（and，or，xor，shl，shr，一些应用）
图论（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路的三种算法，标号法，差分约束系统，验证二分图，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算法）
计算几何（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）
数据结构（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）
组合数学（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）
概率论（简单概率，条件概率，Bayes定理，期望值）
矩阵（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）
字符串处理（KMP，后缀树，有限状态自动机，Huffman编码，简单密码学）
动态规划（单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）
博奕论（Nim取子游戏，博弈树，Shannon开关游戏）
搜索（A*，ID，IDA*，随机调整，遗传算法）
微积分初步（极限思想，导数，积分，定积分，立体解析几何）

Matrix67原创
转贴请注明出处

题目在这里：http://www.matrix67.com/blog/article.asp?id=186

    第一题是老题了，到处都有，连Vijos上居然也找到了一个（VOJ1214）。
    一个O( sqrt(k) )的方法是先算前面sqrt(k)个值，然后剩下的部分除出来的商会出现大段大段相等的情况（这些商的值从sqrt(k)一直变到0，因此最多有sqrt(k)段），每一段的余数是个等差数列，它们的和可以直接算出来。

    第二题，递归问题递归求解。看看样例怎么来的吧，312的右边可以直接确定为314，因为最后一位是2，它的右边就是相同大小的4。312的下边是31的下边，即34。312的左边就是31的左边，而31的左边仍然不能确定（因为1的左边不知道是什么，还需要看它所在的更大的三角形），于是继续递归为3的左边，3的左边是4。这个递归操作完全是多余的，其实只需要从后往前扫描一遍输入的字串就可以了，分别把第一次出现的1、2、3改成4。还有，如果最后一位是4，那就把它改成1、2、3。

    第三题当成答案提交类的题目乱搞，可以搜，也可以用带状态压缩的动态规划。
    第四题动态规划，F[i,j,k]表示从 i 到 j 这一段，且最底下被涂成了颜色k后所需要的最少次数。

Matrix67原创
转贴请注明出处

题目名称    余数之和    三角形       矩形        涂色
英文代号    sum         tri          rect        paint
输入文件名  sum.in      tri.in       rect.in     paint.in
输出文件名  sum.out     tri.out      rect.out    paint.out
时限        1秒         1秒          5秒         5秒
测试点个数  10          10           10          10
总分        100         100          100         100

    给出正整数n和k，计算j(n,k)=k mod 1+k mod 2+k mod 3+ ... +k mod n的值，其中k mod i 表示k除以 i 的余数。
    例如j(5,3)=3 mod 1+3 mod 2+3 mod 3+3 mod 4+3 mod 5=0+1+0+3+3=7

［输入］
    输入仅一行，包含两个整数n,k。

［输出］
    输出仅一行，即j(n,k)。

［样例输入］
5 3

［样例输出］
7

［限制］
50%的数据满足：1<=n,k<=1000
100%的数据满足：1<=n,k<=10^9

    画一个等边三角形，把三边的中点连接起来，得到四个三角形，把它们称为T1,T2,T3,T4，如图1。把前三个三角形也这样划分，得到12个更小的三角形：T11,T12,T13,T14,T21,T22,T23,T24,T31,T32,T33,T34，如图2。把编号以1,2,3结尾的三角形又继续划分……最后得到的分形称为Sierpinski三角形。

    如果B不包含A，且A的某一条完整的边是B的某条边的一部分，则我们说A靠在B的边上。例如T13 23（注：官方订正）靠在T24和T4上，但不靠在T32上。给出Spierpinski（注：原文如此）三角形中的一个三角形，找出它靠着的所有三角形。

［输入］　  
    输入仅一行，即三角形的编号，以T开头，后面有n个1到4的数字。仅最后一个数字可能为4。

［输出］
    输出每行一个三角形编号，按字典序从小到大排列。

［样例输入］
T312

［样例输出］
T314
T34
T4

［限制］
50%的数据满足：1<=n<=5
100%的数据满足：1<=n<=50

    给一个a*b矩形，由a*b个单位正方形组成。你需要沿着网格线把它分成分空（注：错别字，原文如此）的两部分，每部分所有格子连通，且至少有一个格子在原矩形的边界上。“连通”是指任两个格子都可以通过水平或者竖直路径连在一起。
    求方案总数。例如3*2的矩形有15种方案。

［输入］
    输入仅一行，为两个整数a,b。

［输出］
    输出仅一行，即方案总数

［样例输入1］
3 2

［样例输出1］
15

［样例输入2］
3 3

［样例输出2］
52

［限制］
50%的数据满足：1<=a<=4, 2<=b<=5
100%的数据满足：1<=a<=6, 2<=b<=7

    假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。
    每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。
    用尽量少的涂色次数达到目标。

［输入］
    输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

［输出］
    仅一行，包含一个数，即最少的涂色次数。

［样例输入1］
AAAAA

［样例输出1］
1

［样例输入1］ （注：原文如此）
RGBGR

［样例输出1］
3

［限制］
40%的数据满足：1<=n<=10
100%的数据满足：1<=n<=50

做人要厚道
转贴请注明出处

不管结果怎么样，这都是一个转折点，一个有必要记录一下曾经走过的路的转折点。

    2004年9月1日决定参加信息奥赛。
    2004年9月17日晚在阶梯教室上信息奥赛，简介奥赛内容，熟悉进制转换并接触Pascal语言。
    2004年9月29日初上Pascal。
    2004年10月16日下午2:30进行信息奥赛初赛。
    2004年10月27日知信息奥赛初赛成绩。获初赛的三等奖，未进入复赛。因欲上信息奥赛，放弃数学奥赛资格。
    2004年10月28日下午报名正式参加信息奥赛培训。
    2004年11月27日引入数组，难度稍增。
    2004年12月4日指出Zlaner公布的书上习题源程序的错误，引起Zlaner的重视。
    2004年12月5日第一次感到视力下降。
    2004年12月22日试做NOIP2004的题，第一题AC，第二题有思路。
    2004年12月22日继续做NOIP2004的题，合并果子冒泡小数据AC大数据TLE，合唱队形穷举小数据AC大数据TLE。
    2005年1月15日下午信息奥赛上机考试，要求3小时完成4道编程题。4道题分别为数字黑洞、圆环找数、稀疏矩阵和删数游戏。一个半小时全部完成，第一个提前离开考场，赶去和尚静雪、杜巧编排《树人》的目录。
    2005年1月18日知15日考试成绩。最后一题忽略了前导“0”的情况，与嘎嘎并列第一。
    2005年1月29日寒假信息奥赛培训。
    2005年2月2日寒假信息奥赛培训结束。
    2005年2月28日接触Delphi。
    2005年3月2日讲到二叉树，第一次出现了听不很懂的情况。
    2005年3月23日信息奥赛考试，以初赛方式（程序阅读和完善，笔试）进行。
    2005年4月5日开始做TJU。
    2005年4月13日听学校“几何学在并行计算机中的应用”的讲座。
    2005年4月22日建立重庆八中信息奥赛QQ群。
    2005年5月11日发明针对评测系统漏洞的“万能程序”。
    2005年5月13日信息奥赛课后送王雪乔回寝室。
    2005年5月30日信息奥赛课上抢王雪乔饼干吃。
    2005年6月17日晚信息奥赛考试，3小时5道题，结果普遍很差，多数因文件读写错。
    2005年6月24日动态规划上手。
    2005年7月1日因与暑期信息奥赛培训冲突，放弃《三星智力快车》节目录制机会。
    2005年7月11日暑期信息奥赛培训。
    2005年7月24日信息奥赛考试。
    2005年7月25日参加巴蜀中学市NOI集体培训，全天课程持续6天。接触C语言。
    2005年7月30日巴蜀中学市NOI集体培训结束，中午吃自助烧烤，下午集体逃课回家。
    2005年8月27日开学前信息奥赛集训。下午信息奥赛考试。
    2005年8月28日MSN大流行。
    2005年9月26日研究最大匹配问题与匈牙利算法。
    2005年9月28日“是男人就撑20秒”过一分钟。
    2005年10月3日假期信息奥赛集训。
    2005年10月5日连续三天考试，每天一套题。成功破解教师机各密码。
    2005年10月6日再考一套题。火拼泡泡龙大流行。
    2005年10月8日讨论强题——登山机器人。
    2005年10月9日摆脱Zlaner，开始进行自发探索研究。研究并查集和树型动态规划。
    2005年10月14日被迫开始写笔记。
    2005年10月15日信息奥赛NOIP2005初赛。
    2005年10月17日起每天下午都有奥赛培训。
    2005年10月21日做NOIP2003试题。
    2005年10月23日网上模拟赛。发明用rewrite修改C:\windows\notepad.exe等文件的病毒。
    2005年10月25日信息奥赛考试。
    2005年10月26日给李芮简介信息奥赛内容。
    2005年10月29日年级针对信息奥赛采取停课停考政策。下午信息奥赛考试。
    2005年10月30日开始停课搞信息。
    2005年11月3日讨论KM算法。 <---这就是传说中的“KM之夜”
    2005年11月9日TJU的Zroge生日邀请赛。
    2005年11月10日挑战小木棍一题。
    2005年11月11日第二次停课集训开始。
    2005年11月12日网上同步模拟赛。
    2005年11月13日又一网上模拟赛。研究NP问题。
    2005年11月14日强题——Expression。
    2005年11月15日研究凸包。
    2005年11月16日官方发布题目名称。开始猜题。
    2005年11月17日下午集体活动放松，打羽毛球。晚集体外出吃火锅。
    2005年11月19日NOIP2005。
    2005年11月21日信息奥赛结束，恢复正常上课。课程进度严重落下。
    2005年12月6日研究程序算法的不可能问题。网上买的黑书送到。
    2005年12月7日开始看黑书。
    2005年12月11日研究杨式图表、Catalan数列、错排公式、极限、导数。
    2005年12月12日研究Ramsay问题、数论、群论。
    2005年12月18日全国划线。
    2005年12月21日NOI官方网站一等奖获奖名单放出。
    2005年12月23日研究简单的计算几何。做去年选拔赛的Newyear，小数据AC大数据TLE。
    2005年12月24日买《算法导论》。
    2005年12月25日研究矩阵。
    2005年12月30日聚餐七十二行。
    2006年1月1日研究微积分。
    2006年1月5日年级组建第二批信息奥赛团队。
    2006年1月7日Vijos。
    2006年1月10日放弃冬令营。
    2006年1月11日研究各种数列。
    2006年2月1日研究Pólya置换群定理等。
    2006年2月4日买《离散数学》。
    2006年2月7日Zroge大牛讲课。
    2006年2月11日信息奥赛模拟考试，Zroge大牛出题。
    2006年2月13日研究离散变换和反演。
    2006年2月14日研究计算几何等。
    2006年2月15日研究集合论、概率。
    2006年2月16日研究博弈论等。
    2006年2月20日开始直接用GDB命令调试程序。
    2006年2月25日重庆队选拔赛。
    ……
    XXXX年X月X日决定参加ACM团队。

    新年第一天斗地主输了13元，郁闷了，到这里来写一点东西。
    昨天和NK聊MSN，对方冒了一句暴经典的话，说把儿的时间是给女人和OI的。这句话很值得思考。我们要思考一下，为什么OI和女人的地位并列？他们之间有什么共同处吗？我陷入了沉思。几分钟后，我猛然抬头，发掘了一个OI和女人的共同处：对于一个女人和一段程序，往往都是输入的多，输出的少；过程也许很复杂，但我们只管最后的输出。这也是女人和程序最吸引人的地方。因此，我们可以认为，NK的这句话是富有哲学韵味的。
    NK为何说得出这样经典的句子而把儿自己却说不出来？我们很快联系到，NK说，他放弃了。他放弃了什么我们不管，但很显然他能站在把儿、女人和OI之外去分析。换句话说，当把儿陷入OI不能自拔时，NK却清醒的看到OI与女人的等价性。即把儿和NK有个区别：虽然他们都是男人，都把女人放在第一位；但前者却放不下OI，后者却可以坦然的放下来。说穿了，就是把儿把OI当作了一个男人的第二生命（男人的第一生命永远是女人）。
    一个人一生有且只能有一个追求。猫猫这一辈子的追求是什么？猫猫可以选择音乐，可以选择童话，可以选择化学；但一旦选定了，这一辈子都要以它为“线索” 了。有人会说，我什么也不会，就是很猥亵，我这一生还能追求什么？把儿的回答是：你就算只会猥亵，你这一辈子能猥亵出点名堂来，出了点小名气也可以。但是显然这不是针对把儿自己说的。
    曾以为物理是小把儿毕生的追求。后来才知道我错了。用物理知识去说明一些现象，解决一些问题是非常有趣的；但用物理公式去计算一些数值来却毫无意义。计算题玷污了物理的趣味性。有人说，哪个学科不是这样呢？我找到了，那就是信息学。闲时你可以做一些题，你可以去参加竞赛。虽然大多数时候结果也是一个数值，但它与其他的竞赛有一个最大的不同，这也是它迷人的地方：它只关心输出，不关心过程。你的程序不一定对，但你的结果对了；你们的程序都对，但你们的程序完全不一样。每次想到这里我就感到非常高兴。这是目前为止我所发现的唯一一科只需要思维，不需要动笔计算的学科。你不用算，你只需要知道怎么算，然后让计算机算。同时，它也是我发现的涵盖最广的学科。它包含了几乎所有非计算的数学知识，包括离散数学、组合数学、运筹学、逻辑学、图论……
    因此我说，信息学特别有趣。而且是相当的有趣。我不放弃它。但这里的“放弃”定义与NK有所不同。我可以放弃NOIp，可以放弃省选，可以放弃NOI，可以放弃IOI，甚至可以放弃整个信息学竞赛。但我不放弃信息学。用这种方式定义“放弃”，我相信，不单是NK，所有深入学习过信息学的人都清楚，放弃整个信息学是不会发生的事。正如猫猫不会放弃童话，不会放弃音乐。那是一种兴趣和爱好。而我则走上了极端，我不但不放弃它，而且把它置于了与女人同等重要的地位。它将陪伴我一生。我将永远用OI充实我的生活。
    最后说一下，新OIer们，道路非常漫长，要学的东西还非常多。也希望你们永远不要放弃。
    给大家拜个年。