点赞请戳屏幕右下角的圆 QAQ

前言

本文在一定程度上可以说是为浙江的OIer写的，因为大概也只有像我这样的浙江OIer需要担心初赛吧QAQ
本人现为准初三，但却是你谷最弱红名现在还掉了QWQ。（我实在是菜死了）。我第一次参加NOIP是在2016年，那年初赛前的1个月，我才知道的NOIP然后草草报了名，去书店买了本做工程的书看，最后只会数组去考了个29.5分回来QAQ。后来，我搞文化课，结果NOIP再度荒废，直到2017年7月开始才正经起来。结果NOIP又滚粗了（初赛三等QAQ）。
为了今年的NOIP初赛，我就写了这篇文章……

如果你想对本文有个大概的了解，可以点击查看词云.

正文

好了，下面说正经的。
在许多浙江人看来，初赛那是世上最大的坑啊。

很多人觉得初赛跟复赛没啥关系啊，初赛不就是考考硬件嘛。
其实初赛大部分的分数都是考察你的代码能力相关联的东西的。
你有没有发现，初赛里的选择题一题才1.5分（而且最近几年初赛选择题里CCF赞歌的题越来越多了），而看程序写结果一题就8分。而问题求解一共10分，考的是数学，而且跟信息学里常涉及到的数论关系密切。

选择题

我们先来说说选择题，虽说选择题里的确有几道硬件相关的题目，但其实更多的还是考算法复杂度、算法概念、二叉树相关的这些的，跟复赛关联性还是蛮大的。
最近几年特别爱考进制相关的，什么十进制小数转二进制啊，什么原码反码和补码啊之类的。
你甚至会发现，每年NOIP初赛的选择题里都会有一些神题，但也不缺乏送分题，比如下面这道就是典型的送分题：

只要是个人的都知道选C好吧QAQ估计是CCF怕一些人爆零难看
普及组的选择题其实不难，难的是提高组的不定项选择题。这个比学校里的考试要奇葩多了，CCF居然规定多选或少选均不给分。说到这个就不得不提去年的那道题。

这道题很多人只选了B，然鹅答案是B、D。这个故事告诉我们既然参加CCF的比赛就要乖乖地看CCF的新闻。

然后我们再详细说说选择题考什么。
选择题主要是考数学知识、图论、数据结构、时间复杂度、硬件知识、计算机发展史、常用软件知识和CCF赞歌。
下面主要提一下数学知识和CCF赞歌相关的，相信大家在其他的洛谷日报里能够看到许多图论与数据结构相关的内容，而硬件知识与计算机发展史也应该已经有所了解。
好吧，还是给一张计算机发展史的表吧：

	第一代（1946~1958）	第二代（1958~1964）	第三代（1964~1975）	第四代（1975~至今）
核心部件	电子管	晶体管	中小规模集成电路	大/超大规模集成电路
内存	汞延迟线	磁芯存储器	半导体存储器	半导体存储器
外存	穿孔卡片、纸带	磁带	磁带、磁盘	磁盘、光盘
速度（指令数/秒）	几千条	几百万条	几千万条	数亿条

还有关于计算机中各存储单位的进位关系：
1TB=1024GB，1GB=1024MB，1MB=1024KB
1KB=1024B，1B（字节）=8bit（位）

然后是美籍匈牙利数学家冯·诺依曼于1946年提出存储程序原理的特点（这个也曾经于多年前考过）：

• (1)采用存储程序方式，指令和数据不加区别混合存储在同一个存储器中

• (2)存储器是按地址访问的线性编址的一维结构，每个单元的位数是固定的。

• (3)指令由操作码和地址组成。操作码指明本指令的操作类型,地址码指明操作数的地址

• (4)通过执行指令直接发出控制信号控制计算机的操作

• (5)以运算器为中心，I/O设备与存储器间的数据传送都要经过运算器。

• (6)数据以二进制表示。

至于时间复杂度，大家可以参考文章《十分钟搞定时间复杂度（算法的时间复杂度）》 和时空复杂度分析及master定理

数学知识

首先说说数学知识。这方面主要是排列组合、进制转换和原码反码补码。

排列组合

首先是排列组合。何谓排列组合？360百科这样说：“所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。”
的确，解决排列组合的题目的关键就是分清到底是排列还是组合，这两者的主要区别就是排列问题是有序的，而组合问题是无序的。
简单一点的题就是乘法原理和加法原理，但光这样是远远不够的。
排列组合的题目在分清题目究竟是求排列还是组合以后就可以套公式求解。

其实更为复杂的题目应该数同一道题既有排列又有组合。

例题：由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置.
先排末位共有C^1_3
然后排首位共有C^1_4
最后排其它位置共有A^3_4
由分步计数原理得 C^1_3C^1_4A^3_4=288

解决排列组合综合性问题的一般过程如下:

• 1.认真审题弄清要做什么事
• 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。
• 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素.
• 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略

进制转换

然后再来说说进制转换那些事。NOIP初赛主要考的是二进制、八进制、十进制、十六进制之间的转换，以二进制居多，且有时可能会考小数的转换。

至于其他进制转十进制，一点都不难。主要可以这样看：十进制数都可以表示为一个算式，比如说(105)_{10}可以表示为5*10^{0}+0*10^{1}+1*10^{2}，其他进制也一样。如(10101)_{2}可以表示为1*2^{0}+0*2^{1}+1*2^{2}+0*2^{3}+1*2^{4}，因此(10101)_{2}=(21)_{10}

点击这个链接可以简单了解如何将十进制转其他进制（以二进制为例）。而其他进制的相互转换一般是先将其转换为十进制然后再转为要求进制的。

至于小数的进制转换，其他进制转十进制，一点都不难。也可以这样看：十进制小数都可以表示为一个算式，比如说(1.05)_{10}可以表示为1*10^{0}+0*10^{-1}+5*10^{-2}
那么十进制转其他进制呢？可采用乘2取整法，即每一步将十进制小数部分乘以2，所得积的小数点左边的数字（0或1）作为二进制表示法中的数字，第一次乘法所得的整数部分为最高位。

原码反码和补码

再说到原码反码和补码。

• 1.原码：在用二进制原码表示的数中，符号位为0表示正数，符号位为1表示负数，其余各位表示数值部分。
• 2.反码：对于正数，它的反码与原码相同，对于负数，反码符号位与原码相同，其余的按位取反。
• 3.补码：对于正数，它的补码与原码相同，对于负数，先得到相应的反码，并在此基础上加1。
  P.S.原码和反码0的表示方法有两种。这也就是为什么要引进补码的原因。

CCF赞歌

这部分基本上网上你是没地方找到整理好的文档的，主要是因为这东西每年都会换，相当于政治里的时事热点，而OI界基本上没有人会年年都去专门整理。
我这里整理了一些，希望对大家有帮助QAQ
希望大家可以看看下面这些内容，虽然比较CCF，但万一真的押对题了呢？
P.S.下面提到的一些网址也望注意一下。

From NOI官网(www.noi.cn)

1. 初赛及复赛试题均采用电子版本，各省组织单位可视情况印刷纸质试题。（CCF NOIP2018报名通知）
   P.S.这句话说明CCF连卷子都懒得打印CCF下发的是电子版本试题而非纸质版本。 由CCF主办的NOIP赛事举行在即，保密起见，现将有关规定发给各省赛区组织单位。

2. CCF官网近日进行了一次改版，新版上线后，原版网址的地址改为http://history.noi.cn

3. 2018年国际初中生信息学竞赛（International School for Informatics “Junior”,ISIJ2018）于2018年6月23日至7月2日在俄罗斯喀山举行。这是中国队首次参加该项赛事，六名选手取得五金一银的佳绩。中国队获得团体总分第一。（国际初中生信息学竞赛中国队大放光彩）

4. 7月16日-22日，由中国计算机学会（CCF）主办，长沙市雅礼中学承办的第35届全国青少年信息学奥林匹克竞赛（NOI2018）在星城长沙隆重举行。（点燃梦想，燃烧激情——NOI2018在长沙顺利举行）
   P.S. 竞赛之余，NOI2018承办单位长沙市雅礼中学组织了一系列文体活动，丰富大赛日程，增进师生交流。

5. NOI科学委员会(Scientific Committee，简称SC)是CCF设立的负责NOI竞赛技术工作的机构，负责命题、评测、选拔、培训、带领选手出国参赛等。科学委员会成员以自愿者身份开展工作，并唯一对CCF负责。（CCF关于公开招募NOI科学委员会学生委员的通知）

6. 为推动中小学计算机科学教育事业的普及和发展，CCF接受无偿捐赠。捐款方需保证捐赠财产系其所有的合法财产，且有权捐赠。（关于向CCF无偿捐赠的说明 ）

7. 宗旨：旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀计算机人才。（全国青少年信息学奥林匹克竞赛系列活动简介）

8. 关于规范NOIP试题管理办法的通知

9. 根据国际信息学奥林匹克竞赛（IOI）的相关决议并考虑到我国目前程序设计语言的具体情况，CCF决定：1.2020年开始，除NOIP以外的NOI系列其他赛事（包括冬令营、CTSC、APIO、NOI）将不再支持Pascal语言和C语言；2.从2022年开始，NOIP竞赛也将不再支持Pascal语言。即从NOIP2022开始，NOI系列的所有赛事将全部取消Pascal语言。在无新增程序设计语言的情况下，NOI系列赛事自NOIP2022开始将仅支持C++语言。（CCF关于NOI系列赛事程序设计语言变更的公告）

From CCF官网(www.ccf.org.cn)

1. 经CCF奖励委员会决定，为了与国际奖项推荐制度接轨，从2018年起，CCF奖项推荐的有效期延长至三年，即被推荐人如未在推荐当年获评被推荐奖项，只要年龄仍符合条件，则三年内该推荐持续有效，只需由推荐人更新或补充推荐材料即可。（CCF奖项推荐，三年有效）

2. 为发挥中国计算机学会（简称CCF）的学术评价作用，激励、调动计算机专业工作者的积极性，促进计算机科学与技术的创新和进步，CCF设立中国计算机学会奖（简称CCF奖）。CCF奖包括学术（技术）、教育、产业和服务四类。（CCF奖励条例） P.S.推荐大家看看《CCF奖励条例》。CCF奖有：CCF终身成就奖、CCF王选奖、CCF海外杰出贡献奖、CCF优秀博士学位论文奖、CCF-IEEE CS青年科学家奖、CCF夏培肃奖（备注：女性专属）、CCF科学技术奖、CCF杰出教育奖、CCF优秀大学生奖、CCF计算机企业家奖等等。CCF奖励网

3. CCF会员登录全新改版后的CCF数字图书馆网站http://DL.ccf.org.cn，即可免费浏览和检索其中的大部分数字资源。（CCF Digital library，开启CCF在线服务之门）

4. E-Mail：[email protected]
   网　址：www.ccf.org.cn
   CCF简介

问题求解

至于问题求解，主要是数学题，弄清楚组合数学之类的知识（其实很多时候只是一些类似于小学奥数的东西）基本上就没问题了（但务必要拿准了，毕竟一题5分呢）

阅读程序写结果

然后就是阅读程序写结果。
这是初赛中单题分值最高的题，一共四题，每题八分。一般最后两题会出现递归，如果出题人心情好，最后一题会有一个小数据和一个大数据。

下面来详细说说看程序写结果这类题型。
根据历年的题目，我把这类题分为：简单送分题、循环结构题、递归搜索题。
先来说说简单送分题，我这里所指的简单送分题，不仅是指没有循环的，也指那些循环只进行了没几次的简单结构。这类题目一般看看程序顺着其结构往下走就能得到答案，关键是看清楚程序每一步，千万不能因为疏忽大意导致这类题失分。但也许你会说，这类题咋可能会失分呢？这就不对了，且看下面的一个栗子： 不得不提NOIP2016初赛的逗号惨案。

那是一件非常惨烈的事件……由于出题人图谋不轨，PJ的第三题/TG的第一题挖了一个非常非常非常毒瘤的坑，有的选手直接写上的答案却忘记了行末逗号，然后就gg了（当然这个事情后来各省处理方案不一样）
这个故事告诉我们：一定要好好读程序，谨慎写答案。
一个逗号引发的血案啊，足足8分呢！！！
所以做完卷子后（时间肯定是足够的），一定要反复检查阅读程序写结果，尤其是这种简单送分题，因为出题人总是喜欢在简单的题目上埋坑。

接下来再说说循环结构题，我所指的是较为复杂的循环结构的题目，比如说NOIP普及组2017年的第4题&NOIP提高组2017年第4题：

#include <iostream>
using namespace std;

int main() 
{
    int n, m;
    cin >> n >> m;
    int x = 1;
    int y = 1;
    int dx = 1;
    int dy = 1;
    int cnt = 0;
    while (cnt != 2) 
    { 
        cnt = 0;
        x= x + dx;
        y= y + dy;
        if (x == 1 || x == n) 
        {
            ++cnt;
            dx = -dx;
        }
        if (y == 1 || y == m) 
        { 
            ++cnt;
            dy = -dy;
        }
    }
    cout << x << " " << y << endl; 
    return 0;
}
输入 1：4 3
输出 1：_________（3 分）
输入 2：2017 1014
输出 2：_________（5 分）

俗话说得好（俗话：我没说过），循环一烦，形同递归。
其实这个题还有一个坑点，就是每次循环的时候都会有一句cnt = 0（感谢@ciwomuli大佬的反馈）
不过话虽这么讲，循环至少比递归来得好一些，层数也要少（要知道递归可以用来代替多层循环的）
这类题一般会出在第四题，如果出题人觉得的确有点为难参赛者，他们会出两个输入（如本例），第一个输入会非常小，这个分一定要拿到。关键是这种题一定是有规律的，你要根据小输入（题目给的或者你自己构造的）来猜测规律然后求解。
如果不幸遇见递归，那么请把递归当做是循环来做，或者你可以画一个树状图（不知道的右转百度或者左转初中数学课本）来解决。

完善程序

然后就是完善程序。这部分其实说简单还是蛮简单的，说难也蛮难的。
为什么这么说呢？因为做复赛的题目的时候，你完全可以按着自己的思路来，而在初赛的这个地方，你必须完全按着写代码的人的思路来。不过幸好，出题人心情好会出模板题。
在这类题型上，就是要注意多读几遍题目和程序，不要急于去填空。不过其实有些空是可以猜出来的。

比如说NOIP2017普及组初赛的完善程序第一题（快速幂）：

#include<iostream>
using namespace std;
int x, p, m, i, result;
int main() {
    cin >> x >> p >> m;
    result = ________(1)________;
    while (________(2)________) {
        if (p % 2 == 1)
            result = ________(3)________;
        p /= 2;
        x = ________(4)________;
    }
    cout << ________(5)________ << endl;
    return 0;
}

第一个空嘛，看一眼就会填上1.其实是个OIer的应该都有这样一个常识：累加时初值应该为0，而累乘时则一般为1
至于最后一个空嘛，当然填 result 喽，不然前面算它干嘛。
像这种分还是应该要拿的，不然太对不起自己了，对吧？

还有一个注意点就是，完善程序题的变量名一定要注意，绝对不能想当然。
举个栗子，NOIP2017普及组的最后一题（二分），题目中使用了lbound和ubound，但很多人由于代码习惯问题写成了lbound和rbound，甚至有人写成了l和r，这种分丢得你说可不可惜？@memset0大佬在NOIP2017普及组中就是因为看错最后一题的变量名而导致97分变成了91分。（感谢@memset0大佬的反馈）

后记

至于为什么初赛的筛选幅度这么大，你得明白一点，基本上能进复赛的三等奖就拿稳了。

至于初赛咋复习最高效？其实就是多做真题，去领悟CCF的命题规律（尽管CCF的规律是永远无法摸透的）。做题做多了就有觉悟了嘛。
有一点建议：平时有事没事多上CCF官网和NOI官网，看看CCF的最新政策之类的，因为每年NOIP初赛选择题基本上都会有CCF赞歌。

不管咋样，初赛的题就算不会也绝不能空着，蒙也得蒙完。万一蒙对了呢
选择题真的不会就三长一短选最短，三短一长选最长（大雾）

祝愿大家能过初赛QAQ（希望我今年不会在初赛滚粗QWQ）
（阅读程序写结果）一定要好好读程序，一定要好好读程序，一定要好好读程序！！！重要的事情说三遍。
最后，对洛谷的初赛题库表示非常期待。

2018.08.17UPD:推荐补充阅读@iWApD3的《初赛》