SCAU 2020年计算智能考试复习指南

逃离我推掉我的手 2023-10-06 09:27 31阅读 0赞

### 2020年计算智能考试复习指南 ###

**一、处理多case的程序设计**  
18104 练习使用多case解题  
`while(1) break；`  
`while(scanf("%lld%lld",&c,&d)>1)`  
scanf有返回值，scanf(“%d %d”，&a,&d)的返回值是2

**二、测试的重要性及数据的文件导入方式**  
了解OJ的评判的详细过程，了解各类评判结果（尤其是编译错误、超时、运行时错误）对应可能的出错原因。  
编译错误：代码格式错误、函数头文件没有添加进去（如cstring）、GCC CPP、书写错误，有拼写错误，常见的就是单词的大小写没有区分开，英文句号写成英文逗号、有格式错误，比如该缩进的没缩进，漏了括号，又或者忘记加冒号、对于用法错误，比如函数的传入的参数与函数要求的参数不符、基本语法错误  
超时：死循环、代码复杂度过高、输入条件和题目的不符合  
运行时候错误：输出结果不对（输出必要的换行或者大小写错误、有特殊的数据没有考虑.看看数组开的是否太小）、格式错误。多了少了空格回车什么的、发生除零错误、指针用错了，导致访问到不该访问的内存区域。

**三、程序的运行时间及复杂度估算**  
学会找基本操作（单位时间操作）  
学会推导数据规模与时间的关系式  
 下面说一下各个复杂度1s可计算数据的规模：（用机房电脑跑出来的，仅供参考）  
线性O（n） ： 1s 大概 3e8 个数据 当然这只是执行一条语句； 多条语句 最好不要超过 1e8，感觉1e7都勉强了  
O(nlogn)  
10^5 ~ 5 \* 10^5  
O(n^2)  
1000 ~ 5000  
O(n^3)  
200 ~ 500  
O(2^n)  
20 ~ 24  
O(n!)  
12  
  
**四、了解pair、vector、string、stack/queue、map的作用和时间复杂度**

**五、熟练sort/stable\_sort的使用，了解何为稳定的/非稳定的排序算法**  
sort是快速排序O(nlogn)实现，因此是不稳定的；stable\_sort是归并排序实现，因此是稳定的O(n2)；  
对于相等的元素sort可能改变顺序，stable\_sort保证排序后相等的元素次序不变；  
如果提供了比较函数，sort不要求比较函数的参数被限定为const，而stable\_sort则要求参数被限定为const，否则编译不能通过。  
18118 勇者斗恶龙  
总结：就是将骑士和恶龙的值从小到大排序（sort），然后一条龙一条龙的杀，如果有一条龙无法被杀掉，则无解。  
时间复杂度：O(nlogn+n)=O(logn)  
18107 校赛排名  
总结：题目就是要我们给选手排名，根据通过题数多的排前，同题数的，罚时少的排前。如果题数相同，罚时也相同，而按数据读取的先后排。利用sort定义bool函数，来处理优先比较谁，这题就要定义一个结构体，也就是说用sort函数对结构体进行排序。  
时间复杂度：O（nlogn）

**六、掌握枚举的技巧并会分析时间复杂度**  
完美立方  
总结：直接暴力求解  
时间复杂度：O（n3）或者O（n*logn*logn*logn)*  
生理周期  
总结：读入 p, e, i, d  
从 d+1 循环到 21252， 找到第一个满足条件 1)的时间 a、并跳出循环  
从 a 循环到 21252，找到第一个满足条件 2)的时间 b、并跳出循环  
从 b 循环到 21252，找到第一个满足条件 3)的时间 x、并跳出循环  
输出 x-d  
时间复杂度：O（1）  
称硬币  
在称量结果为"even’’ 的天平两边，没有出现 x ；  
如果 w 表示假币比真币轻，则在称量结果为"up’’ 的天平右边一定出现 x、在称量结果为"down’’ 的天平左边一定出现 x  
如果 w 表示假币比真币重，则在称量结果为"up’’ 的天平左边一定出现 x、在称量结果为"down’’ 的天平右边一定出现 x  
在参数str所指向的字符串中搜索第一次出现字符c（一个无符号字符）的位置。  
18443 除法等式  
总结：先枚举出C，注意C的每个数字要不一样，判断C%A是否为0，然后C/A（A是我们输入的数字），求的B，再看B里的数字和C中的是否一样，这样我们就能得到C/B=A。  
时间复杂度：O（1+1)=O(1)  
1079 三角形  
先判断如果是斜边，则从3开始枚举。  
如果是直角边，则假设为最小的那条边k，然后斜边就是a，另外一条就是a-1，通过  
aa-(a-1)*(a-1)=k*k,a=(k*k+1)/2,从而确定最大边的上界，下界比较容易算不解释，a>sqrt(k*k/2)。  
时间复杂度：O（n2+n2-√n2/2)=O(n2)  
**七、掌握递归的技巧并会分析时间复杂度**  
爬楼梯  
 楼梯有一个台阶，只有一种走法；  
两个台阶，有2种走法；  
有n个台阶时，设有count(n)种走法，最后一步走1个台阶，有count(n-1)种走法；最后一步走2个台阶，有count(n-2)种走法。于是count(n)=count(n-1)+count(n-2)。  
此问题类似斐波那契数列。  
unsigned long int 无符号型长整形，数据全为正数，范围较大。

1142 巡逻的士兵  
判断一共有多少种分法  
O（logn）  
18441 偷懒的士兵  
和巡逻的士兵相似，如果如果少于三个人，则那一组一定不会被选走。  
O（logn）  
**八、掌握分治的技巧并会分析时间复杂度**  
归并排序  
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(N*logN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。  
逆序数  
快速排序  
**九、掌握深搜和广搜的技巧并会分析时间复杂度**  
抓住那头牛  
就是访问每一个点  
O（n）  
迷宫问题  
广度搜索o(n)  
城堡问题  
18440 走迷宫2  
采用广度搜索（queue），先要判断是否为为传输门，并且有一个visit数组来判断该点是否有被走过，如果没有走过，则把这个点放到队列中去。  
时间复杂度：由于每个节点仅被发现一次，因此每个节点入栈和出栈各一次，时间均为O(1),故入栈和出栈总时间为O(V);由于需要对每个节点的邻接表进行扫描，时间为O(Adj\[u\]),总时间为O(E);综上所示，广度优先搜索的时间复杂度为O(V+E).即是图邻接表大小的线性函数。  
18124 N皇后问题  
时间复杂度：n皇后问题如果不进行任何剪枝，以最朴素的观点来看，其时间复杂度就是 \[N的N次方\] 。因为 N 行N 列，皇后的排列方式共有 \[N的N次方\] 种。  
大概会将最坏时间复杂度优化至 \[N！\] ，平均时间复杂度应该也是指数的，因为中间如果遇到不符合的时候，就直接break了，就不会进行接下来了运算，降低了算法的复杂度。  
**十、掌握动态规划的技巧并会分析时间复杂度**  
数字三角形  
递归 (重复计算，效率低) O(2^n)  
把当前位置(i,j)看成一个状态 d\[i\]\[j\]为从格子出发能得到的最大和 解为d\[1\]\[1\]  
d(i,j)=a(i,j) +max \{d(i+1,j),d(i+1,j+1)\}   
递推 (逆序枚举) O(n^2)  
i是逆序枚举的，计算d\[i\]\[j\]前 所需要的d\[i+1\]\[j\]  
和d\[i+1\]\[j+1\]一定计算出来了  
[https://blog.csdn.net/baidu\_38304645/article/details/83718174][https_blog.csdn.net_baidu_38304645_article_details_83718174]  
最长上升子序列  
0-1背包问题  
着一类的问题用递推的话都是建立一个二维数组递推，然后时间复杂度就是O（n^2）  
最长公共子序列  
8615 快乐  
设dp\[i\]\[j\]在选择第i个物体时（此时背包容量为j）时的最优快乐指数（物体从0开始），首先对dp\[0\]\[j\]初始化，即只有精力j时是否选择第0个物体的最优解。根据0-1背包模型；从第1至第n-1个物体，只存在两种情况，选取或者不选取。选取时，需判断dp\[i-1\]\[j\]，dp\[i-1\]\[j-losspow\[i\]\]+gethappy\[i\]谁为最优，不选取时，直接等于 dp\[i\]\[j\]=dp\[i-1\]\[j\]。最后答案输入dp\[n-1\]\[2000\]加一即可。  
注意这里的dp\[51\]\[2001\]是指最多50个物品和2000个精力，对于第一个if，dp\[i-1\]\[j-b\[i\]\]是指i物品之前的剩余的精力(在这里已经是该物品的最优解），max则是看看加上这个第i个物品好，还是不加上这第i个物品好。  
时间复杂度：O（n \* 2000）=O（n）  
**十一、掌握贪心的技巧并会简单证明贪心的合理性**  
圣诞老人的礼物  
电影节  
9506 吃水果  
 （1）读取数据，设置一个数组K，下标为第i天，记录每一天要吃的水平重量  
（2）水果按重量由大到小排  
（3）由大到小，遍历每一个水果，该水果到第w天过期，就从下标w开始倒序查找数组K，发现第一个  
数组K的元素为0，则将该水果的重量赋值到该数组元素，如果没有找到为0的，则放弃该水果。  
（4）最后将K数据中的数累加起来，就是答案。  
时间复杂度：O（nlogn+n2）=O（n2）

[https_blog.csdn.net_baidu_38304645_article_details_83718174]: https://blog.csdn.net/baidu_38304645/article/details/83718174