初赛整合-临门一脚

  • CSP一年三次,分为”入门组”,”提高组”,”专业认证”,到今年为止,CCF已成功举办19次CSP

  • NOIP开始于1996年,全称是National Olympiad in Informatics in Provinces

  • NOI开始于1983年,今年是第37届在湖南长沙一中举行

  • IOI第一届于1989年在保加利亚的布拉维茨举行

  • 省队名额分为A,B,C,D,E,初中只能进E队

  • Linux系统具有开源且免费,跨平台等优良特征,而Mac OS,Windows系统并不开源

  • 常用的电脑操作系统:Windows,UNIX,Linux,Mac OS,DOS,Windows系统使用最广,Linux深受码农喜爱

  • 正数的补码为其本身,负数的补码为其除了符号位之后取反+1的值

  • 计算机能直接执行的指令:操作码和操作数(而非:源操作数和目标操作数)

    “∨” 表示”或”

    “∧” 表示”与”

    “┐”表示”非”

  • CSP和NOIP举办的目的不同,且没有从属关系

  • 照片内存计算:分辨率 * 位数 / 字长(8) / $ 1024^x $

  • 概念:贪心是求局部最优,以得到全局最优 true

  • 函数式编程语言
    定义:函数式编程语言(functional programming language)或称函数程序设计,又称泛函编程,是一种编程典范,它将计算机运算视为数学上的函数计算,并且避免使用程序状态以及易变对象。函数编程语言最重要的基础是λ演算(lambda calculus)

    特征:
    1.以“函数”为首,如同命令式语言中的“变量”,函数可以赋值给其他变量,可以作为其他函数的参数,或者作为其他函数的返回值
    2.不修改变量的值
    3.只有表达式,没有语句。此处的语句指的是没有返回值得某些操作
    4.引用透明(Referential transparency),函数的运行不依赖与外部变量或“状态”,简单的说就是,同一个输入(参数),总是会产生同一个输出(返回值),这与数学函数的特征很一致。命令式语言因为全局变量等的存在,就无法做到这一点
    5.对比命令式语言,递归形式的循环

  • 纯函数式编程语言:Concurrent Clean,Haskell,Miranda,Lazy K

    非纯函数式编程语言:F#,ML,OCaml,Scala,Erlang,LISP,LOGOScheme,Clojure,Mathematica,R,Unlambda

    其他函数编程语言:APL,XSLT

  • 树边(tree edge):每次搜索找到一个还没有访问过的结点的时候就形成了一条树边

    反祖边(back edge):也被叫做回边,即指向祖先结点的边

    横叉边(cross edge):它主要是在搜索的时候遇到了一个已经访问过的结点,但是这个结点 并不是 当前结点的祖先时形成的

    前向边(forward edge):它是在搜索的时候遇到子树中的结点的时候形成的

    $ \therefore $ 对于DFS生成树有树边,返祖边,横叉边,无前向边

  • 时间复杂度主定理

  • 闰年->分为普通闰年和世纪闰年

    普通闰年:公历年份是4的倍数的,且不是100的倍数,为普通闰年

    世纪闰年:公历年份是整百数的,必须是400的倍数才是世纪闰年

  • 闰月->是一种立法置闰方式,在亚洲(尤其在中国),闰月特指农历每$ 2 \sim 3 $年增加的一个月

  • TCP UDP

    全称 传输控制协议 用户数据报协议

    是否连接 面向连接 面向非链接

    传输可靠性 可靠 不可靠

    应用场合 传输大量数据 少量数据

    速度 慢 快

    连接对象个数 一对一 一对一,一对多,多对一,多对多

    首部开销 首部最小20字节 首部开销小,仅8字节
    ​ 最大60字节

  • 计算机在存储,传送或操作时

    字:一个单元的一组二进制码

    字长:一个字中的二进制位的位数

  • 字长是决定电脑计算精度

    衡量CPU指标的是字长

字长越长,电脑运算能力越强,精度越高,有效数据的存储单元数越多,寻址能力越强

  • 32位系统的最大寻址空间为4GB

    64位系统的最大寻址空间为

  • $ B \rightarrow KB \rightarrow MB \rightarrow GB \rightarrow TB \rightarrow PB \rightarrow EB \rightarrow ZB \rightarrow YB $

  • KiB是kilo binary byte的缩写,指千位二进制字节,1KiB=1024B

    KB是kilobyte的缩写,指千字节,1KB=1000B

  • 机器字长:是指计算机能直接处理的二进制数据的位数,决定了计算机的运算精度

    指令字长:一个指令字中包含二进制代码的位数

    存储字长:一个存储单元存储一串二进制代码(存储字专),这属串二进制代码的位数称为存储字长,存储字长可以是8位、16位、32位等

  • 二分图相关概念

  • NOI各省组织单位必须遵循CCF《关于 NOIP 数据提交格式的说明》的规范在竞赛结束后规定时间内向 CCF 提交本赛区所有参赛选手的程序

  • 英特尔是全球最大的半导体芯片制造商,成立于1968年

    AMD是目前业内唯一一个可以提供高性能CPU,高性能独立显卡GPU,主板芯片组三大组件的半导体公司,并是首家推出x86架构处理器的公司

  • CPU

    功能:解释计算机指令,处理计算机软件中的数据

    组成:控制器,运算器,高速缓冲存储器,以及连接它们的数据控制的总线

    功效:处理指令,执行操作,控制时间,处理数据

  • CPU性能衡量指标:主频,位数,缓存指令集

    主频:时钟频率

    位数:处理器能够一次性计算的浮点数位数

    缓存指令集:主要指的是能够对CPU运算进行知道以及优化的硬程序

  • 计算机三大核心部件:CPU,内部存储器,输入/输出设备

  • 图形加速器(图形加速卡):

    概念:一种以芯片集成方式专门进行图形运算的图像适配卡

    组成:一般由具备独立CPU的硬件和相应软件构成

    用途:专门为图形图像显示而优化

  • 3D加速器:一种可安装成城电脑

  • g++编译器常用指令:

    -Ofast:-Ofast优化

    -o:file生成指定的输出文件

    -O0:不进行优化处理

    -O(-O1):优化生成代码

    -O2:进一步优化

    -O3:比-O2更进一步优化,包括inline函数

    exec:将源文件编译为可执行程序且保留调试信息

    -w:不生成任何警告信息

    -Wall:生成所有警告信息

    -E:只运行C预编译器

    -c:只编译并生成目标文件

    -g:生成调试信息(GNU调试器可利用该信息)

    -shared:生成共享目标文件(通常用在建立共享库时)

    -static:禁止使用共享链接

  • P类问题(polynominal,多项式):存在多项式时间算法的问题

  • NP问题(Nondeterministic polynominal,非确定性多项式):能在多项式时间内验证得出一个正确解的问题(不知道这个问题存不存在多项式时间的算法)

    NPC问题(Nondeterminism Polynomial complete):存在这样一个NP问题,所有的NP问题都可以约化成它

    NP-Hard问题:NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,NP-Hard问题没有限定属于NP),即所有的NP问题都能约化到它,但是它不一定是一个NP问题

初赛-3.jpg

  • 常见图像文件格式:
    PSD,PDD:Photoshop软件自身的专用格式,是唯一能支持全部图像颜色模式的格式

    GIF:一种使用LZW压缩的格式,目的在于最小化文件和减少传输时间

    JPEG,JPG:既是一种文件格式,又是一种压缩技术

    PNG:可以存储透明,完爆GIF格式的地方在于失真小,没锯齿,缺点是不支持动画

    PDF:一种灵活的,跨平台,跨应用程序的便携文档格式,可以精确地显示并保留字体

    SVG:可缩放的矢量图形,当该格式文件的图像进行任意缩放,都不放影响他的清晰度和光滑度

  • 编译器功能:一种语言(通常为高级语言)翻译为另一种语言(通常为低级语言)

    主要工作流程:源代码 (source code) → 预处理器(preprocessor) → 编译器 (compiler) → 目标代码 (object code) → 链接器(Linker) → 可执行程序 (executables)

  • Gitee:基于Git的代码托管和研发协作平台

  • memset的一般设置

  • 计算机发展代别划分:
    初赛-1.png

  • 1946年2月,在美国宾夕法尼亚大学诞生了世界上第一台电子计算机ENIAC(Electronic Numerical Integrator And Computer),这台计算机占地170 $ m^2 $,重达30t,用了18000多个电子管,加法运算次数5000次/s

  • 1944年,美籍匈牙利数学家冯·诺依曼提出计算机基本结构和工作方式的设想,为计算机的诞生和发展提供了理论基础

    其理论要点:计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备5部分组成

    存储程序思想:把计算过程描述为由许多命令按一定顺序组成的程序,然后把程序和数据一起输入计算机,计算机对已存入的程序和数据处理后,输出结果

  • 计算机分类:巨型机,大中型机,小型机,微型机,工作站

  • 图灵(Alan Turing)是英国人,1913年图灵进入剑桥大学国王学院,毕业后到美国普林斯顿大学攻读博士学位,二战爆发后回到剑桥,后曾协助军方破解德国著名密码系统Enigma,帮助盟军取得了二战胜利

  • 汉字信息编码:
    1.汉字交换码:汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用的代码标准。国家标准GB2312-80公布以来,我国一直延用该标准所规定的国标码作为统一的汉字信息交换码(GB5007-85图形字符代码)。

    GB2312-80标准包括了6763个汉字,按其使用频度分为一级汉字3755个和二级汉字3008个。一级汉字按拼音排序,二级汉字按部首排序。该标准还包括标点符号、数种西文字母、图形、数码等符号682个。

    区位码的区码和位码均采用从01到94的十进制,国标码采用十六进制的21H到73H(数字后加H表示其为十六进制数)。区位码和国标码的换算关系是:区码和位码分别加上十进制数32。如“国”字在表中的25行90列,其区位码为2590,国标码是397AH

    2.字形存储码:字形存储码是指供计算机输出汉字(显示或打印)用的二进制信息,也称字模。通常,采用的是数字化点阵字模

    一般的点阵规模有16×16,24×24等,每一个点在存储器中用一个二进制位(bit)存储。在16×16的点阵中,需8×32 bit 的存储空间,每8 bit为1字节,所以,需32字节的存储空间。在相同点阵中,不管其笔划繁简,每个汉字所占的字节数相等。

    为了节省存储空间,普遍采用字形数据压缩技术。所谓的矢量汉字是指用矢量方法将汉字点阵字模进行压缩后得到的汉字字形的数字化信息

  • IP地址:所谓IP地址,是用于标识 IP Internet 网络上节点的 32 位地址(以后可能使用的V6版本是128位的,分8组,每组16位)。对于 IP Internet 网络上的每个节点都必须指派一个唯一的地址,它由网络 ID 和唯一的主机 ID 组成。该地址通常用由句点分隔的八位字节的十进制数表示(例:192.168.7.27)。

  • 算法性质:有穷性,确定性,输入,输出,可行性

  • 0的反码有两种表示:$ +0 \rightarrow 000 \cdots 000,-0 \rightarrow 111 \cdots 111 $

  • C++运算等级:
    初赛-2.png

  • 关于前缀,中缀,后缀表达式表达式的转化

     中缀表达式可以写成一棵表达式树
    
     对于中缀表达式转前缀表达式:在表达式树上进行先序遍历即可
    
     对于中缀表达式转后缀表达式:在表达式树上进行后序遍历即可
    
     对于前缀表达式转中缀表达式:倒序使用辅助栈即可
    
     对于后缀表达式转中缀表达式:正序扫并建树,最后中序遍历即可