【OI之路】01语法与STL-1概要与常识

这些可能在NOIP初赛、日常做题比较有用
当然也是计算机领域的一些常识

系统dfs栈

windows默认60000左右,linux默认250000左右
解决方法:手写栈

主定理

用来分析复杂度的东东
$T(n)=aT(\frac{n}{b})+f(n)$
如果 $f(n)<n^{log_b a},T(n)=O(n^{log_b a})$
如果 $f(n)=n^{log_b a},T(n)=O(n^{log_b a} log n)$
否则, $T(n)=O(f(n))$
很多分治算法不太好计算,就可以用这个

初赛易错

  1. 主频1 GHZ=1000 MHz
  2. 区位码转国际码,分别加上32;国际码转机内码,分别加128
  3. LAN 局域网,MAN 城域网, WAN 广域网
  4. 网络协议
    应用层:telnet(远程登陆),ftp,e-mail
    传输层:TCP(传输控制协议), Udp(用户数据报协议)
    网络层:IP 网际协议,ICMP(网际控制报文协议),IGMP(组管理协议)
    网络结构层:设备驱动程序

  5. DNS域名系统,将域名转化为地址

  6. 电子邮件:简单邮件传输协议SMTP,电子邮件拓展协议MIME,POP协议
  7. 不稳定排序:选择排序,希尔排序,快排,堆排, 只有堆排和归并最坏nlogn
  8. 16位色指有 $2^{16}$ 种颜色,即每个像素2字节
  9. 面向对象的语言:C#,c++,java,smalltalk,eiffel
  10. 第一种高级语言:Fortran
  11. 浮点数分阶码和尾数两部分,阶码位数越多,可表示的数的范围越大;尾数越多,所表示的数的精度越高
  12. 复杂度包括时间和空间
    P问题:存在多项式解法的问题;
    NP问题:多项式时间内验证答案的问题;
    NP-hard问题:所有NP问题可以在多项式复杂度内归约到它
    NPC问题:所有NP问题可以在多项式复杂度内归约到它,而且是NP问题
  13. IP
    0.0.0.0 对应于当前主机
    255.255.255.255当前子网的广播地址
    127.0.0.1 代表本机IP地址

oth

我的:
原码、补码、反码
操作符和优先级
可变参数
数据类型的对照

别人的:
数制转换
逻辑运算
栈与卡特兰数
二叉树的遍历和性质
哈夫曼树和哈夫曼编码
模拟与高精度算法
排序与算法复杂度
数据结构基础
数论算法基础
图论算法基础
组合数学基础
计算几何基础
基本算法思想
计算机文化基础
计算机系统原理
计算机网络基础
计算机病毒防治
计算机信息处理
信息学奥林匹克

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/5fe4.html
转载请注明出处,谢谢!