知识点

P/NP/NP-hard问题

P类问题：存在多项式时间算法的问题。(P：polynominal，多项式)

NP类问题：能在多项式时间内验证得出一个正确解的问题。(NP:Nondeterministic polynominal，非确定性多项式)

• P类问题是NP问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内验证他。

（3）NPC类问题（Nondeterminism Polynomial complete）：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：
首先，它得是一个NP问题；
然后，所有的NP问题都可以约化到它。
要证明npc问题的思路就是：
先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它。

（4）NP难问题（NP-hard问题）：
NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广，NP-Hard问题没有限定属于NP），即所有的NP问题都能约化到它，但是他不一定是一个NP问题。
NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

时间复杂度

主定理

对于\(T(n)=aT(\lceil \frac nb\rceil)+O(n^d)\quad a>0,b>0,d\ge 0\).

错题集

NOIP2013

T19
（ ）属于 NP 类问题。
A. 存在一个 P 类问题
B. 任何一个 P 类问题
C. 任何一个不属于 P 类的问题
D. 任何一个在（输入规模的）指数时间内能够解决的问题

引用-From ltdj

https://www.cnblogs.com/ltdjcoder/p/13779423.html

OI初赛知识点整理

---

1.广告题

• 创办时间：　NOI(1984)、IOI(1989)、NOIP(1995)、冬令营(1995)、APIO(2007)、

• 举行时间：...........

• 可以携带：笔、手表
  不能携带：纸、U 盘、手机、笔记本。【2015年开始不允许自带鼠标键盘等设备】
  场地为选手提供的物品是：草稿纸、饮用水、食品。指noi）

• 不具有通讯功能的电子词典也不能带　

• C和C++中64位整数只能使用long long类型及unsigned long long类型。
  C++可以使用STL中的模板。
  PASCAL程序中禁止使用除system库（自动加载）和math库（须用uses math子句）之外的其他单元。

• 从2020年开始，除NOIP以外将不再支持Pascal语言和C语言。
  从2022年开始，NOIP竞赛也将不再支持Pascal语言。

• NOI官网：http://www.noi.cn/
  官网OJ：http://oj.noi.cn/
  CCF官网：http://www.ccf.org.cn/

• ccf奖：终身成就奖、王选奖、夏培肃奖、

• 1949.10.1是星期六

2.计算机硬件

• CPU

  • 由运算器, 控制器， 及一些寄存器组成。主要性能指标是主频和字长（16，32， 64位等）。
  • CPU能直接运行机器语言。

• 随机储存器（RAM）　所谓“随机存取”，指的是当存储器中的数据被读取或写入时，所需要的时间与这段信息所在的位置或所写入的
  位置无关 ， 可以随时读写。不是指分配给程序的内存位置是随机。

• 一般的个人计算机在同一时刻只能存/取一个特定的内存单元

• 内存寻址: 寻址是以字节为单位， 不是bit， 地址总线32位， 可寻x^32 字节。即****微机以字节编址

3.计算机软件

• 操作系统

• 操作系统(Operating System，简称OS)是管理计算机硬件与软件资源的计算机程序。

• 分时操作系统 (time-sharing system)，“分时”的含义：分时是指多个用户分享使用同一台计算机。多个程序分时共享硬件和软件资源，是指在一台主机上连接多个带有显示器和键盘的终端。

• BIOS是计算机基本输入输出系统软件的简称。

4.常识题

• 1948年，（香农 ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

5.网络必错题

• 网络协议层

  • 应用层：HTTP, FTP, SMTP, TELNET, NFS, 等应用。
    • Telnet是基于TCP/IP的应用，用于远程连接。
    • NFS基于UDP，是网络文件系统，广泛适用于Unix系统
  • 表示层：表示数据格式或加密，加密，ASCII等
  • 传输层：TCP, UDP, SPX,
  • 网络层：IP, IPX

• IPv6 是 IPv4的补充升级， v4需要32位， v6需要128位

• IP地址分类

  • A类网络的IP地址范围为：1.0.0.1 －126.255.255.254；
  • B类网络的IP地址范围为：128.1.0.1－191.255.255.254；
  • C类网络的IP地址范围为：192.0.1.1－223.255.255.254

6.数据结构

• 顺序存储结构：把逻辑上相邻的结点存储在物理位置上相邻的存储单元中。 链表是非顺序储存结构。　　
• 线性结构是一个有序数据元素的集合。
  • 常用的线性结构有：线性表，栈，队列，双队列，串(一维数组)。
  • 常见的非线性结构有：二维数组，多维数组，广义表，树 (二叉树等)，图
    • 广义表，高维数组是广义线性的，但是不是线性结构。

7.c/c++

• 字符串末端有结束标记‘0’, 占一个字节，而字符数组没有。

• 运算符

  优先级	运算符	名称或含义	使用形式	结合方向	说明
  1	[]	数组下标	数组名[常量表达式]	左到右
  ()	（表达式）/函数名(形参表)
  .	对象.成员名
  ->	对象指针->成员名
  2	-	负号运算符	-表达式	右到左	单目运算符
  (类型)	(数据类型)表达式
  ++	++变量名/变量名++	单目运算符
  --	--变量名/变量名--	单目运算符
  *	*指针变量	单目运算符
  &	&变量名	单目运算符
  !	!表达式	单目运算符
  ~	~表达式	单目运算符
  sizeof	sizeof(表达式)
  3	/	除	表达式/表达式	左到右	双目运算符
  *	表达式*表达式	双目运算符
  %	整型表达式/整型表达式	双目运算符
  4	+	加	表达式+表达式	左到右	双目运算符
  -	表达式-表达式	双目运算符
  5	<<	左移	变量<<表达式	左到右	双目运算符
  >>	变量>>表达式	双目运算符
  6	>	大于	表达式>表达式	左到右	双目运算符
  >=	表达式>=表达式	双目运算符
  <	表达式<表达式	双目运算符
  <=	表达式<=表达式	双目运算符
  7	==	等于	表达式==表达式	左到右	双目运算符
  !=	表达式!= 表达式	双目运算符
  8	&	按位与	表达式&表达式	左到右	双目运算符
  9	^	按位异或	表达式^表达式	左到右	双目运算符
  10	|	按位或	表达式|表达式	左到右	双目运算符
  11	&&	逻辑与	表达式&&表达式	左到右	双目运算符
  12	||	逻辑或	表达式||表达式	左到右	双目运算符
  13	?:	条件运算符	表达式1? 表达式2: 表达式3	右到左	三目运算符
  14	=	赋值运算符	变量=表达式	右到左
  /=	变量/=表达式
  *=	变量*=表达式
  %=	变量%=表达式
  +=	变量+=表达式
  -=	变量-=表达式
  <<=	变量<<=表达式
  >>=	变量>>=表达式
  &=	变量&=表达式
  ^=	变量^=表达式
  |=	变量|=表达式
  15	,	逗号运算符	表达式,表达式,…	左到右	从左向右顺序运算

  • 　　

8.编码

　　原码: 最高位为符号位， 其他正常表示

　　　反码： 正数为其原码， 负数在原码的基础上，符号位不变， 其他位取反。

　　　补码：正数为其原码， 负数在反码基础上加1， 符号位不变

9.np

NP: 多项式验证一组解

P ：多项式求解

NPC: 如果所有np问题都可以归结为一个np问题， 解决了这个np问题就解决了所有np问题， 那么这个问题就是npc问题。

NP-hard ： 就是npc， 但是不一定是np， 就是把npc的范围扩大到所有问题，而不只是np问题

10. 错题

Linux下可执行文件的默认扩展名是： 好吧linux没有扩展名