初赛复习

2021/9/17 23:09:58

本文主要是介绍初赛复习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

初赛复习

知识点

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\).

\[T(n)= \begin{cases} O(n^d) &(d>\log_ba)\\ O(n^d\log n) &(d=\log_ba)\\ O(n^{\log_ba}) &(d<\log_ba)\\ \end{cases} \]

错题集

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

img

NP: 多项式验证一组解

P :多项式求解

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

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

10. 错题

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



这篇关于初赛复习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程