初赛知识点dark回顾
pengzhaozhao · · 个人记录
初赛知识点大回顾
本文章由pzh一手编写，未经允许请勿转载！
|初赛题库大全|
祝各位神犇初赛顺利通过！！！
1、计算机常识（级别：计算机 & 错了该打）
计算机通俗来讲，我们现在用的电脑就是计算机，当然还有许多高级计算机，我们平常看不到，我先从历史开始讲起吧。
（1）计算机历史
第一代计算机：电子管计算机（1946~1958） 比如说ENICA就是，它诞生于1946年的美国，它的体积巨大，运算速度为每秒 5000次加法运算。 所以说计算机一开始是运用于数值计算。
第二代计算机：晶体管计算机（1958~1964） 这不常考，知道名字就好，知道它是第二代，还有别和第一代搞混就行。
第三代至第四代计算机：集成电路和超大规模集成电路计算机；（1964~1970~至今） 你只要知道它是微型计算机就是今天电脑这么大的鼻祖就行了，集成电路是计算机史上一个重大的转折点，计算机从这以后发展速度迅猛，所以有一个重要定律：摩尔定律。 根据摩尔定律， 计算机集成电路板上的晶体管数量24个月翻一倍。 也就是说，计算机处理性能每隔两年翻一倍，现在还是这样的吗？那我们就不得而知了，不过这个定律很重要，要记住。
现今世界上基本上全部的计算机都采取冯式结构，即伟大的计算机鼻祖冯·诺依曼，他最早提出了使用二进制编码运算数据。
（2）机器组成
我们现在讨论的计算机以现在普遍使用的普通计算机为例。
计算机通常由 软件 和 硬件 组成。
(1)硬件：看得见，摸得着的就是硬件，显示器是硬件，鼠标是硬件，键盘也是硬件。这里在细分有以下几种：
·CPU： 它是电脑的核心，负责 运算和控制系统数据，好比说你要开机了，你按下电源线，电源通过总线向CPU传输数据，它就得动了，分析完这是要开机（运算）后，CPU会传输数据，让显示器亮起来（控制）。CPU有几个重要组成部分： 运算器+控制器+寄存器，一定要记住。
·存储器： 存储器包括固态硬盘；RAM（随机存储器，也叫内存），ROM（只读存储器），硬盘和ROM断电之后 能够保存数据， 因为硬盘里的东西肯定不能关机之后就没了嘛，ROM是只读存储器，一般是买来电脑前就被厂家写死的，不会变也不会没。RAM是随机存储器，比如说你现在打开了Chrome浏览器，你立即关机，再开机你会发现你的Chrome没了，桌面上什么都没开；又比如说你在写Word文档，你如果按了保存键，那么Word会保存到硬盘上，电脑关机它还在，但是如果不保存，那么它就存在RAM上，关机之后会清空。 RAM负责与CPU直接交换数据，非常重要。
另外， 计算机的基本存储单位是byte，即字节。几种存储单位关系如下所示：
1byte（字节） = 8bit（比特）
1KB（K） = 1024byte（字节）
1MB（兆或M）= 1024KB
1GB（G）= 1024MB
1TB（T）= 1024GB
一般的，从字节到TB都是1024的关系；
特殊的，一字节等于八比特。·各种卡： 比如说声卡，用来播声音的，显卡，没了它你的电脑屏幕就是黑的或者花的或者蓝的，网卡，没了它你就没得上网，不能去洛谷算命了，这些卡与CPU与内存都连接在 总线 上。
(2)软件： 看不见，摸不着的就是软件，它主要分为 系统软件 和 应用软件 两大类，比如说Windows10就是系统软件，Chrome浏览器就是应用软件。
操作系统： 主要功能是控制计算机和管理系统资源。 Windows，Linux都是操作系统，我们现在用的一般是64位操作系统，这和以前的32位，16位操作系统的最大不同是寻址（可以理解为内存上限）能力不同，比如说，32位操作系统最多可以寻址4G，64位则是恐怖的八十多亿GB，16位则只不过是64KB的内存，这主要取决于CPU的针脚分给你多少个用来寻址，一般现在的CPU都有几千个针脚，分64个去寻址很容易，但是以前的只有几百个，我分32个出去都很多了。
软件系统： QQ，微信都是软件，光有一个操作系统可能不能满足我们的需求，所以我们需要安装各种软件，安装多少不会有要求，只要你硬盘资源足够就行，一般操作系统本身就占了硬盘10G到30G了。
总之，计算机的硬件系统组成可以理解为五大模块：运算器，控制器，存储器，输入设备、输出设备。软件系统组成包括系统软件和应用软件。
备注：
存储器一般认为是内部的存储器，即不包括Udisk，移动硬盘等外部存储设备，输入设备例如鼠标，键盘给电脑输送命令的设备，显示器，音箱，打印机等输出给人看的就是输出设备，有些东西比如说触屏笔既是输入设备也是输出设备。
计算机知识到此结束。错了该打。。。QWQ
2、有点信息学的“味道”的数论（级别：计算机+/数论- & 错了不太应该）
·计算机位运算、二进制编码和进制转换：
一、二进制基础上的逻辑运算（或与非）
1、或：逻辑符号表达为或，或者是or或者是||，它的运算规则是0和1有一个是1这一个值答案就是1 。
2、与：逻辑表达符号位与，或者是&& 和 and，它的运算规则是如果两值为1那么答案都为1，否则为0，例如：1&&1=1， 0&&1=0， 0&&0=0;
3、非：逻辑符号表达为非，或者是 ! 和 not，它的运算规则是如果这个值为真，那就把它变为假，反之变为真，例如：!0=1; !1=0;
基本上会考的就这些，再补充一个异或，作Xor，运算规则是两个值不同则为真，相同则为假。再补充一个取反，作~，如果这个数是1，则取0，否则取1,和非差不多，但是取反可以针对多位，所以这个比较特殊。但是 注意，这些其它逻辑运算只能针对两个数或者一个数，一串数和一串数只能一位一位地算，不是说一串数直接通过一次逻辑运算就可以得到新的一串数的，而且这些都是在2进制的基础上，如果一个数不是二进制，那要转成二进制。在C/C++中，true代表1即真，false代表0即假。
二进制编码是计算机用来计算的，不是人看的，但是SCP CSP要考，所以它不是人。我们一般采用 八位二进制编码，数字部分首位是符号位，0代表正数，1代表负数，不论怎么变，符号位不会变的，剩下的是都是数字，这种编码在计算机中我们把它称之为 原码。如果我把这串编码除了符号位作取反操作，那么得到的就是 反码， 一串数的补码就会等于它的反码+1，这三种“码”有助于计算机化简运算操作。
再补充一个知识点：ASCILL码，中文读阿斯科码，为 美国信息标准交换代码，重要，它是用数字编号代表一个一个的字符，需要知道的是字符之间的大小关系，首先'A'小于'a','A'的值是65，'a'的值是97，'0'的值是48，都是顺序排的，比如说A后面就是B，C，D，a后面就是b、c、d，所以知道其中一个字母的值就可以推出其它字母的值，C++的字符比较大小都是用的ASCILL码。
同样地，有2进制就会有其他进制，我们现在熟悉的都是十进制，即满十进一，一个数为不可能有大于等于10的数字出现，因为进一了，同样二进制也只能有0,1；三进制满三进一，只能有0,1,2；八进制最多一位上也只能有7；但是十六进制不一样，它慢十六才进一位，所以一位如果大于等于十，我们用ABCDE表示，即A表示10，B表示11，以此类推。
如何运算？
（1）十进制转x进制（包括小数），那用短除法，将原数除以x取余，作为x进制数的最低位，将整型原数除以x的商（即只要整数部分，不考虑小数和四舍五入）继续除以x取余， 商为1的时候还不能停，必须再除，直到商为0才停止。
例如，(5) 10 转 二进制：5除以2得2余1，最低位为1,2除以2余0，商为1，1除以2得0余1，从下往上读得结果为“101”。
对于小数部分也好办，小数部分乘以x取整，比如说(0.125)10转2进制：
0.125 * 2 = 0.25 .....整数部分取0
0.25 * 2 = 0.5 ......依然取0
0.5 * 2 = 1 ......整数部分是1，取1，发现没有小数部分，则运算结束。
从上往下读，结果为(0.001)2。
（2）x进制数转十进制：将x进制数从低位往高位看，最低位要乘以x的0次方，加上倒数第二位乘以x的1次方，倒数第三位乘以 x的2次方，乘到最高位，把所有算的加起来即为答案；
对于小数部分，从十分位往后，第i位的k应该转为 k * x^-i，就是第i为的那个数乘以进制的负的第几位次方，a^-b的算法就是把它看成 a的b次方分之一。
例如：(0.11)2转为10进制：
小数点后：
第一位：1 * 2的负一次方 = 1乘以2的1次方分之一 = 0.5
第二位：1 * 2的负二次方 = 1乘以2的2次方分之一 = 0.25
从上往下读，结果为(0.75)10。注意，十进制转x进制用整数短除法，直到商为零，从下往上读，小数部分乘x取整，直到小数部分为零，从上往下读；x进制转十进制整数部分从低位往高位累加数字乘以进制的第几位-1次方，小数部分从左往右累加数字乘以进制的负位数次方。
位运算到此结束QWQ。
3、排列组合问题（难度：数论+/变态 & 做不出来的，这辈子都不可能做出来的hiahiahia）
这个东西，我们仿佛离开了信息学，走进了数学，不是，我们月考才刚考完数学，卷子还贼难，不过还好，八上月考不会有排列组合的。（废话一堆）
一、总结归纳了一下
我总结了历年普及组试题，发现排列组合变态的还真的是，说多绝对不可能，说少，那也没少到哪去，我认为，排列组合主要从以下几种情况考：
以下方法不专业，不专业，不专业！！！！
但是百通百灵！！！一用就对！！！
（1）袋子：n个球放进m个袋子，允许有blblblblblbl，有多少种方法？
解决办法：枚举
0个袋子：1种
1个袋子：1种
2个袋子：
1 n - 1
2 n - 2
3 n - 3
4 n - 4
....
3个袋子：
.................这种方法有三大优势：一是一看就稳，二是一枚就准，三是我不知道~ 目前，没有人能够阻挡我对这种题用枚举法的冲动。哈哈哈！
（2）多少中选多少：一看就是排列组合，这时候枚举也有三大优势：一是一看就会，二是一做就错，三是枚到你怀疑人生，天旋地转，生无可恋……
所以，我们要学会有 技术含量，做初赛，不带有 技术含量 怎么行呐，我们先得要判断这是排列还是组合，举个简单的例子，不是组合，就是排列，假如1 2 3和2 1 3 都算不同的方案，那这就是排列，因为这是不同的排列，所以就用A几几，反之，1 2 3和2 1 3没区别，因为这两种方案都包含它们三个数，如果算做同一种方案，那这就是组合，一般用C几几；
公式：
n是底下的，m是上面的。
A(n, m) = n * (n - 1) * ... * (n - m + 1)
其实就是从n乘m次，每次减一。
C(n, m) = A(n, m) / m!
其实百度上的是 C(n, m) = n!/m!(n - m)!
化简就是上面那个，C(n, m)一般比A(n, m)结果小。
（3）乘法原理： 具体的话我也不知道该说什么好，看题吧，NOIP2012的第22题就是这个，这种题就是最变态的那种，其实也有简单的，比如说SCP2019的那个车牌。
一般是看某一个位置有多少中选法，是否会有重复，然后将每一位的选法累乘起来，再除以重复的次数，就是答案。 重复的这玩意最恶心，能让你要去算有重复的话那就恭喜你遇到了变态级别的排列组合（放在高中是个中档题，嘿嘿嘿）
排列组合到此结束QWQ。
4、树&图论 （难度：常识+/算法- &做不出来要被kiu眼珠子特别是二叉树的那种）
图论我前面其实写文章写过一篇，在这里就不讲了，那边讲的很有归纳，也很详细，待会放个链接，这里呢，先讲讲树这个憨憨玩意。LAJI ERCHASHU HUIWO QINGCHUN
树是图的一种，树往往有 n个顶点，n-1条边，这玩意是常识，必须得知道。
树也可以分很多种，比如说kiu你眼珠子kiu的最狠的就是二叉树，考得最多的那种，在这里我们就要说以下关于二叉树的一下定义和公式了：
（1） 一些名词：
根节点：二叉树的最上面的那个“根”，就是祖宗，根节点。
左子节点 ：二叉树最多有两个子节点，因为它是“二”叉树，所以它左边的那个就叫做左子节点，注意，这有很强的方向性，不能乱规定它一定是左子节点或者右子节点。
右子节点：跟左子节点一样，只不过方向往右。
子树： 一个节点的左子节点存在的话，那么这个节点存在左子树，右子节点存在的话，那么这个节点存在右子树。
叶子节点： 一颗二叉树的叶子节点就是不存在任何子节点的节点。
深度： 二叉树根节点深度记为1（不一定，也可以记为零），然后它有多少层？跟层树，高度差不多。
森林： 一堆树在一起，就叫森林，这个名词知道就好。
（2） 二叉树的种类：
①：完全二叉树：怎么说呢，有点复杂，比如说我现在有一棵树的叶子节点，我们看着叶子节点的上一层来看，如果上一层有x个节点，它们的子节点都是叶子节点哈，然后比如说从第一个说起，第二个节点如果想要有子节点，那么前一个，也就是第一个节点必须要有右子节点才行，我第二个节点这时可以有子节点了，但是如果我没有左子节点就不能有右子节点。我在强调一遍，我刚刚说的那俩，它们的子节点都是叶子节点。所以当一棵树满足我填的点都是从左往右填的，填的满满的，中间没有空一个出来的，就是完全二叉树。
再不door就看图吧：
你看，是不是节点5因为4两个节点都有了，所以才可以有一个节点10，此外，这颗完全二叉树里面除了叶子节点要么就做有两个子节点都有，要么就只有左子节点，不可能说只有右子节点的吧。所以这就是完全二叉树。
②：满二叉树
满二叉树是完全二叉树的一种，它除了叶子节点之外，每个节点都有左右两个子节点。 它的节点数量为： 2^k-1，其中k为二叉树的深度（根节点深度为1才行），这个结论很重要，很重要，必须记住。此外，2^(k-1)是第k层的节点个数（满二叉树里）。
（3） 遍历
一般是分为先序遍历，中序遍历和后序遍历；
先序遍历：先访问根节点，再访问左子节点，最后访问右子节点。
中序遍历：先访问左子节点，中间访问根节点，最后访问右子节点。
后序遍历：先访问左子节点，再访问右子节点，最后访问根节点。
遍历以递归形式前进，即深搜。绝对的，一棵树的先序遍历第一个肯定是根节点，后序遍历的最后一个也肯定是根节点。如果给你一棵树的先序遍历与中序遍历，要知道后序遍历应该怎么样？
很简单， 前序定根，中序定左右，先确定先序遍历第一个点是根节点，然后再中序遍历中找到它，在中序遍历中，其左边的所有点是根节点的左子树，其右边的所有点是根节点的右子树，然后先序遍历第二个肯定是左子树的根节点或者是右子树的根节点（如果有左子树肯定是左子树的），然后反复上述步骤还原出整棵树，也是递归思想嘛，太水——到渠成了，不想举例子。QAQ
后序遍历和中序遍历，推出先序遍历也是这样，但是只知道先序遍历和后序遍历，不能确定唯一的树。
接下来是图论： 戳这里
树、图搞定！！！
5、数据结构 & STL模板类 （级别：常识+/算法- & 错了要把眼珠子kiu下来）
这个玩意是最常考的，数据结构的常识，STL模板类，选择题常考，问你是什么意思，问你理不理解，不理解 那就完蛋了！ 所以，让我们赶紧来赣淦C++的这些玩意：
一、几种定义：
int:整型变量，数据范围从-2^31 ~ 2^31-1;
(-2147483648 ~ 2147483647)一个整型变量占4个字节（32位的8位2进制）。
long long:长整型变量，数据范围从-2^63 ~ 2^63-1;
一个长整型变量占8字节。
char:字符变量，数值（ASCILL）从0~255，占1个字节。
bool:真假变量，要么是true，要么是false，占1个字节。
double,float:浮点型变量，可以有小数点。范围和int一样。
二、数组： 相信这是啥大家都知道了，注意，数组的下标从零开始，然后你们把初赛里面的集合理解为一个数组也行。
三、字符数组： 字符数组也是数组的一种，不过它存的是字符，跟数组用法一样，字符串最后一位以\0结尾，否则不能称之为字符串。在C++中，string 就可以定义一个字符串，有诸多用法：
#include <string>//必要的头文件
s.length()//字符串的长度;
s.subster(0,x)//从0开始算一位，拿x位，剩下的不要。
.....//初赛很少涉及到。此外，字符串的子串是 一段连续的字符串子序列。 空串也是子串，如果要算空串的话，运算公式就是：
n(n-1)/2 + 1。
STL模板类：
（1） 栈：栈是一种后进先出的线性数据结构，先进先出就是：它相当于一个杯子，将一个物品放进去，再将其它很多个物品再放进去，第一个放进去的那个物品最后才能出来，每次出来，只能出最顶上的那个，每次放，也只能放到最顶上，不能随机访问任一元素。线性：我不知道，数组也是一维线性数据结构，字面意思吧。
stack<数据类型> st;
| |
| |
|__|
此栈为空：入栈“1” st.push(1);
| |
| |
|1_|
入栈：“2”st.push(2)
| |
|2 |
|1_|
入栈：“3”st.push(3)
|3 |
|2 |
|1_|
理论上栈这种东西可以无限入栈，但如果题目有要求就得判断。
出栈（不能指定，只能是最顶上的）st.pop();
| |
|2 |
|1_|
出栈st.pop()
| |
| |
|1_|
出栈
| |
| |
|__|
栈为空的时候不能出栈，否则会报错。
（2） 队列：queue<数据类型>来定义，它是一个先进先出的线性数据结构，你可以理解为是一个管子，两端都是可以出去的那种，先放入A，出队A就出去了。它也是不能随机访问任一元素。一般用来广搜。
q.push(x);将x入队
q.pop();出队，也不能指定，只能是队头。
特殊地：
priority_queue<数据类型> ：优先队列，
放入一个数据它自动帮你排序小的在前大的在后，用小根堆实现。如果要大的在前小的在后就要：
priority_queue<数据类型, vector<数据类型>, greater<数据类型> >
deque<数据类型>：双端队列，可以入队队头，也可以入队到队尾，出队同样不只是出队头，也可以出队尾。（3）：vector，vector是一种一维线性数据结构，它跟队列有点像，但是它可以随机访问任一元素，如果要输入的话，不能直接cin，要像队列那样给v.push_back(x)，注意不是单纯的push，然后如果要遍历的话，那就必须得从0开始遍历而不是1。它跟数组比较类似，所以LeetCode上面的题是数组的全部都用vector。
（4）：链表，链表的话太奇妙了，它分为两种，单向链表，双向链表，每个元素有几个域，指针域和数据域。
当链表为单向链表时，指针域只有一个，指向后续节点，数据域是当前的值，单向链表的某一个节点只能访问后续节点，不能访问前驱结点（只能看后面的，看不到前面的）
当链表为双向链表时，指针域有两个，一个指向前驱节点，一个指向后续节点，数据域存储当前的值，它既可以访问前驱结点，也可以访问后续节点。
链表在内存上的存储是随机的，不连续的，它不像数组那样有一个指定的空间，因为链表可以连无限个，还有它的特点是它不可以访问任一元素，这个常考，要记住。
搞定。
6、深搜广搜递推递归，二分搜索动态规划（难度：算法+ & 有些时候允许错）
这玩意涉及到CSP的大题，CSP的大题靠你考的是看你到底有没有真正理解这个程序，所以上面6个算法必须要烂熟于心。
·深搜：
如果你们学过图论的话，深搜广搜一点都不难理解，对于一道搜索题，你要学会将它隐式图转化，这个我那个图论の重点讲过的。
就是说深搜为了什么，它是为了找到多个符合题意的解，找一个目标，往往不考虑最优解这种东西，而它往往能够转化成动归，我后面讲动归的时候会讲。深搜的结构图论里面也讲了，不多讲了。
·广搜： 广搜其实也很简单，它是为了找到最优解，比如说它算最短路，最小生成树都行。它不用递归，用队列，结构也讲过了。
·递归： 递归就是将一个问题转化为许多子问题，解决子问题的问题规模不同，但是方法是一样的，简单来说，就是自己调用自己，递归一定要有三个要素： 1、递归出口、2、复述状态，3、前进过程。递归出口必须要有，复述状态就是负数子问题的状态，前进过程就是我如何自己调用自己。
·二分搜索： 这个有意思，初赛每年都会考，估计2020也会（就是今天），这个玩意简称猜答案，一般是问你 最大值最小或者是最小值最大。 就是我要在一个区间内，二分猜一个答案，往往是用一个左变量和右变量l、r，然后while(l <= r)... 区间很重要，它是决定你猜数的范围，l小于等于还是小于r，这里需要引入一个区间概念：
【a,b】: 区间a到b（包括a和b）（左闭右闭）
（a,b）: 区间a到b（不包括a和b）（左开又开）
【a,b）：区间a到b（包括a不包括b）（左闭右开）
（a,b】：区间a到b（不包括a包括b）（左开右闭）题目会告诉你区间在哪，有时候不会很直接，然后你自己判断吧。
然后就是找一个中间的值mid = (l + r) / 2，这是个基本模型，/2之后要不要加一或者干嘛题目说了算。这是为了找一个中间值，如果这个中间值符合某些条件（这个条件可能很复杂，要专门写几行来判断，题目说了算），l = mid; 或者 r = mid;区间范围就缩小了，到底要不要加一一定要判断 慎重，题目说了算。如果mid就是答案怎么办？你人知道了，计算机不知道，不用担心，就算mid是答案，r会等于mid然后不久不满足while条件了嘛，或者l就等于mid了然后就退出了。 最大值最小的答案存在于右变量r上，最小值最大的答案存在于左变量l上。
·动态规划： 动归三要素是 重复子问题，最优子结构、无后效性。重复子问题是递归里面引出的，它主要通过解决一系列的子问题来求解最大的问题以得到目标状态，就是答案。
比如说我要走10步，我怎么帅气的走一步？怎么帅气的走1+1步？怎么帅气的走2+1步？是不是，问题规模不同，但是“帅气”都是一样的，这就是 重复子问题。
最优子结构就是我帅气的走10步是由帅气地走1步，2步，3步推导而来的，他们之间有包含关系，子问题是最优的，总问题也是最优的。这就是最优子结构。
无后效性指的是我想出来的帅气地走3步的解不会因为我要帅气地走3步，我就需要改变我帅气地走1步的方案，也就是说，一旦我确定我要帅气地走x步，它以后就不会改变了。
更多具体怎么解：戳这里
初赛知识点大概就这些了，够全面的，其他的看造化吧。QWQ