初赛复习:完善程序

入门普及提高篇

  • 认真审题,到底要做一个啥。
  • 知道题目意思之后尝试自己用自己的思路解决题目。
  • 根据题目给出的部分程序,结合自己的思路,推断出每一部分的作用。
  • 若推断不出来可以根据题目代码中的函数名例如Sta/Top等可以得知这是一个栈。
  • 注意语法问题,语法中函数名什么注意不要拼写错误。
  • 注意在判断出每一段作用时,校验一下有没有跟之前重复的作用的函数,数组,有的话可能就是出错了。
  •  ......  查看更多

    初赛复习:阅读程序

    入门篇

  • 要细心,其实都是简单的小程序,只要认真看两下,模拟三遍确认答案就好,这种题目一定要拿分
  • 观察内嵌函数规律,有些比较大的函数模拟不便时考虑一下与组合数等关系
  • 对于每一次模拟递归函数,记得写清除每一次递归的参数,递归到了哪里,值是多少。
  •  ......  查看更多

    初赛复习:问题求解

    组合与排列

    1. 这个的话其实到时不会可以手玩一下杨辉三角形,第i行第j+1个既C(i,j)
    2. 抽屉原理,有n个抽屉kn+1本书,那么至少有一个抽屉里至少有k+1只鸽子。

    容斥

  • 看过Ax人,看过By人,两个都看过的z人,总人数为x+y-z
  •  ......  查看更多

    初赛复习:程序设计基础知识

    算法

    1. 有穷性,确定性,输入,输出,可行性
    2. 复杂度分时空复杂度,时间复杂度为O(x),空间复杂度可以划分为输入所需存储,程序本身存储,逻辑运算所需存储。
    3. 算法结构有顺序结构,选择结构,循环结构

  • 操作插入查询弹出的都是栈顶元素
  •  ......  查看更多

    初赛复习:计算机基础知识

    计算机历史

    1. 计算机发展经历了很多的阶段,总体来说,就是逻辑电路的集成化,从电子管晶体管集成电路到如今的大以及超大规模集成电路
    2. 第一台电子计算机是1946年2月在美国宾夕法尼亚大学诞生的。

    计算机架构

    1. 冯诺依曼架构美冯诺伊曼提出,既计算机拥有储存运算控制输入输出的功能。
    2. 图灵架构是英国图灵提出的,既计算机有基础逻辑工作方式,是现代AI常用架构。

    历史常识

    1. 计算机保护法是保护软件著作权的法律
    2. 世界上首个写代码的人是Ada Lovelace
    3. 显示器颜色既RBG,RED红,BLUE蓝,Green绿
    4. 图灵奖既计算机界的诺贝尔奖
    5. ITInformation Technology信息技术缩写。

    计算机组成

    1. 中央处理器CPU,由运算器控制器以及高速寄存器组成用来执行逻辑运算。
    2. 存储器,分主存储和辅助存储两种,主存储器一般指内存RAM,辅助存储器一般指硬盘,还有一种厂家预先写入的叫ROM。储存单位是1024B=1KB1024KB=1MB1024MB=1GB1024GB=1TB1024TB=1PB,都是1024进制的。
    3. 输入输出设备,输入设备一般有鼠标键盘等,输出设备一般指显示器打印机音响,WIFI光驱等即为输入设备也为输出设备。

    计算机主要性能指标

    1. 字长 一般有64位和32位,有极少数老机子还是16位的。字长月长,可以表示的信息就越多,机器的功能就越强,可以操控的内存区域就越大。
    2. 主频,主频越高,运算速度就越亏奥,单位一般位GHZ
    3. 内存容量,是储存运行数据的地方,常用单位为GB,字长不一样的机器可以控制的最大内存容量是不一样的。

    计算机操作系统

    一般分两种Unix类操作系统,一般指的是Linux,MacOS等系统,另一种指的是微软的Windows操作系统,Windows是目前最普遍的操作系统。
    以下是一些Unix类系统和Windows系统
    Unix: Red Hat Linux,CentOS,Debian,Ubuntu等。
    Windows:Win NT,Win server 2003,Win 7/8/10等 ......  查看更多

    Accumulation Degree

    Accumulation Degree
    这题简单来说就是任意根到子树的最大流量,这题假如我们枚举n个点的话,我们可以用O(n^2)时间做出这一题,但是呢,n很大,所以呢我们要至少减去一个log的复杂度,又因为我们只枚举一个任意点进行一次DP就可以获得大多数其他点DP得到的结果,所以我们先DP一次,然后再利用dfs计算DP取得的数据据算出其他点的数据。 ......  查看更多

    没有上司的晚会

    没有上司的晚会
    这题的话我们可以把直接上司和员工连一条边,这里f[x][0]表示我不让x来的最大快乐值,f[x][1]表示让x来的最大快乐值,那么我们每次dfs下去回溯时,就分f[x][1]+=f[x][0]f[x][0]+=max(f[y][0],f[y][1]),分情况讨论一下,最后输出max(f[1][0],f[1][1])即可

     ......  查看更多

    选课

    选课
    选课这一题我们很容易发现没有根节点,因为可能不止一个不用前置课程的节点,然后我们因为多个课程可能有一个相同的前置课程,所以我们其一可以通过森林转二叉树进行就是左孩子右兄弟,或者采用背包型树形DP,把每一次树形DP的结果都做一个背包,这样子用f[x][t]代表以x为跟的子树选t个节点的最大值,然后再回溯时背包一下,就可以用不同的t取得不同f[x][t]结果,然后就可以正常动归了! ......  查看更多

    「算进」[动归]树形DP

    动态规划问题是大家都很熟悉的问题了,那么好了,树形DP顾命思意就是在一棵树上DP,解决一些问题,那么我们可以采用Dfs+边目录的方式来处理这些问题。通常来说从x节点递归下去,然后回溯上来,递归的数据x转移。

    没有上司的舞会

    这题的话我们可以把直接上司和员工连一条边,这里f[x][0]表示我不让x来的最大快乐值,f[x][1]表示让x来的最大快乐值,那么我们每次dfs下去回溯时,就分f[x][1]+=f[x][0]f[x][0]+=max(f[y][0],f[y][1]),分情况讨论一下,最后输出max(f[1][0],f[1][1])即可
    AcceptCode ......  查看更多

    「算进」[字符串]KMP

    纯属为了复习KMP,以前论文丢失了,现在参考算进重新撰写。
    简单来说我们可以用O(n)的方法找到所有字串匹配原串的位置,就是基础的字符串匹配算法啦,但是如果暴力的话复杂度是O(nm)。KMP可以通过失败指针进行跳转,省去了直接暴力比对的时间。
    失败指针是什么呢?就是下一个这种字串出现的位置在哪里,我们就可以在失败的时候跳去下一个可能可以继续匹配的地方继续询问,而不用暴力枚举。
    那么我口胡一下KMP的过程
    1. 对字串进行一次自己匹配自己的操作求出Fail数组也就是等会例题代码里面的p数组。
    2. 用子串求出来的Fail值匹配母串,记录最长匹配值。
    3. 在匹配值里面进行查找,如果又等于子串长度的就是有完全匹配。 ......  查看更多