pat乙级自我回顾：一般错误出现原因 - fool_king

在obsidian里面写的有些引用没用，需要的可以评论区或者私信我呦~
对于错误，末尾的换行不影响格式，

一般是设置的数组小于题目给定的要求，循环条件i--写成i++，数组下标写错,也有可能是因为数组a没有初始化，导致 b[a[2]] 这种形式访问了⾮法内存，是否没有考虑0或者边界值的情况？⽐如对于⼀个空数组却访问了 arr[0]即，scanf的时候是不是没写&数组越界、还有就是堆栈溢出（⽐如，递归调⽤层数太多）

答案错误一般就是代码逻辑有错误，或漏了某个点，从新审题把孩子

运行超时：

1. 所有测试点都是运⾏超时，⼀般情况是出现了死循环
2. 部分说明题目不能用暴力破解，尝试跳过一些数.
3. 然后就是当你对一段数据重复访问，你应该问问自己怎么样减少访问次数。
4. cin 的输⼊⽐ scanf 更耗时，如果个别测试点超时可以考虑是否可以通过优化输⼊将 cin 改成 scanf
5. 使⽤ map 存储如果超时了，⽽题⽬⼜没有要求排序，换成⽤ unordered_map 就不会超时，同理，使⽤ set 存储如果超时了，可以考虑换成 unordered_set 避免超时。
6. 对数据进⾏排序的过程中，有很多数据是⽆效数据，如果对所有数据都排序可能会引起超时，所以可以考虑在放⼊数组之前就做⼀些条件判断剔除⽆⽤数据，然后再对数组进⾏排序。
7. 一些小习惯：如果写了 main 函数之外的其他函数，传引⽤会⽐传值的⽅式更省时，因为传值是拷⻉传参，传引⽤是传⼊的地址直接在原变量上修改，所以可以考虑优化为 void func(int& a) 的⽅式传递参数减少耗时。for 循环语句⾥定义 int i 和在外⾯定义 int i 其实有少许区别，在 for 循环语句⾥直接定义的 i ，⽐如 for(int i = 0; i < 10; i++) 可能会更耗时，把它改成 int i; for (i = 0 ; i < 10; i++) 也是降低代码运⾏时间的⼀种可考虑⽅式哦～
8. 使⽤了 v.size()-1 等⽅式，如果 v.size() 本身就是0，因为 v.size() 返回值是⽆符号整数 unsigned int ， unsigned int 的0减去1得到的是 unsigned int 的最⼤值⽽⾮ -1 ，这可能会让int i 循环时 i < v.size() - 1 超时
   https://www.cnblogs.com/ahappyfool/p/17173405.html
   如果某些循环是必要的，那么可以采取跳着访问，跳两个效率就提升一倍。例如1104缘份数：m和n的最大公因数必须大于2，容易得知s1最后结果的个位一定需要是9，如若不是9则n=m+1，那么n与m的最大公因数一定只能是1，因为相邻两个正整数的最大公因数是1，只有s1的末位是9或末尾是连续的9，加一之后末尾变为0才有可能使m与n的最大公因数大于2。[代码#1104 天长地久]
   常考错误点和方法统计：
   一定要注意自己写的每一步，for内部，函数参数，判断条件等都是容易犯错的地方——特别注意已经非常多次了
   注意给的数值范围，如果储存不下换类型，注意不超过等字眼，注意没有给定什么类型的数，然后就是某种类型不满足要求就该使用(int->double)1020 月饼：[[代码#1020 月饼：不能在结构体内使用其他结构体变量初始化另一个变量，可以指定默认值。注意数据类型，这种销售数据不能时int]]
   关注题目信息
   注意临界情况测试，如1103缘份数中，对于m=1时，如果b也等于1，那么就会出错，会得到答案不符的结果，所以测试一下就好了
   题⽬输⼊中所给的a b区间可能a和b给的顺序反了，要⽐较⼀下a和b的⼤⼩，如果 a>b 记得swap回来。
   如果是简单题观察能否直接使用某种方式打出，又或者说，能不能一点一点打出
   特殊情况处理(空格处理，特例，哪种情况特殊)，处理时因十分注意，以免有有坑,即把不是特殊情况的情况处理成特殊情况1012 数字分类：[[代码#1012 数字分类：要注意当没有该类元素时才用n表示，也就是说该小心当总和为零的选项]]
   大量读入和输出使用scanf和printf 1066 图像过滤
   %操作要注意负数1069微博转发抽奖（和map）
   定义大数组要使用全局变量⽽不是写在main函数⾥⾯，否则容易发⽣段错误（因为⼤数组
   在 main 函数⾥⾯的话是存储在栈⾥，⽽栈空间是在进程创建时初始化的，有固定的⼤⼩，⼀
   般为⼏⼗KB，所以太⼤的数组会耗光栈空间。⽽全局变量占⽤的堆空间，堆空间中的内存是按
   需分配，⾃由增⻓的，可以⾮常⼤，⽐如32位的系统中可以⼤到4GB。将⼤数组放在全局变量中
   能避免栈溢出～同时对于做题目可以尝试把重复的元素和固定不变的元素都放在main之外
   如果觉得数组从下标0开始麻烦，可以考虑舍弃0位，从1下标开始存储数据
   int最⼤值为2147483647，共10位数字； LLONG_MAX 最⼤值有19位数字，以9开头。所以说储存13位的学号可以⽤ long long int ，输出的时候使⽤ %013lld
   对 char c[15] 进⾏ sort 排序的 cmp(char a[], char b[]) 函数要这样写： strcmp(a, b) < 0 ，因为 strcmp 返回的不是 -1 0 1 ⽽是 等于0 ⼩于0 ⼤于0 的某个值， strcmp 在头⽂件 #include <string.h> ⾥⾯对 vector v 或者 string v 进⾏ sort 排序： sort(v.begin(), v.end(), cmp1); ；对数组a进⾏sort排序： sort(a, a + n, cmp1);
   输出语句如果有 is / are、加s / 不加s的区别的话⼀定要当⼼，⽐如 "There is 1 account" 和 "There are 2 accounts" 是不同的输出语句
   printf输出%的时候用%%
   当索引为int时，使用数组比map好得多，尤其是在时间严格的时候
   时间和日期需要运算比较时可以将其转化为最小单位如秒和天，也可以不转，看哪个方便吧。学⽣姓名和分数，如果不需要将姓名输出的话，不仅可以⽤ struct 结构体中 string 或者 char 存储姓名，还可以将姓名转化为 int 类型，⽐如 ABC4 可以转换为 ((((A * 26) + B) * 26) + C) * 10 + 4 = ((((1 * 26) +2) * 26) + 3) * 10 + 4
   大的数的后面几位数等于小的数：1.to_string 2.%操作
   对于多个循环体内多个变量需要累加求和时，应该在最后一重循环进行运算，否则可能会因为当前循环进行多遍而导致某个中间数加了多遍。
   整除和被整除不同，别搞反了
   是否产生相同元素，产生是否想要的结果
   1106题外话：判断数列中不可能出现2018；通过奇偶判断：奇偶会出现规律：0011，0110，1100，1000，0001， 0011，0110
   gcd：辗转相除法求最大公约数

int gcd(int a, int b){	return b == 0 ? a : gcd(b, a % b);}

字符串：stoi,to_string,substr,data,reverse,sort,insert,

1. 实现数学计算（int）：注意开头零。注意含有空格可能(getline和cin.get()循环连续输入多行可能包含空格的字符串，无论在此之前是否有读入，应该在循环开始前加入cin.get()；)。还要当心结果为0(即去开头0不能把结果为0去掉)要符合逻辑，保证应有的结果。如果前面保留有前导零，和数字太长就是说明该用字符串了。1114全素日。1019数字黑洞（atoi和to_string）：[[代码#1019 数字黑洞：注意字符串转数字和数字转字符串也就是还有前导零，然后当n=6174时，不能直接输出空值，可以尝试自己定义转换函数也可以用库]] 1017 A除以B:（同时还要小心当被除数只有一位，和为0，为负数的情况）。部分简单题直接改为long long就行。大整数运算注意0[[代码#1017 A/B：注意当除数没有被除数大时应该输出0，而且首部不能有多余的0；模拟手动除法的过程，每次用第一位去除以B，如果得到的商不是0就输出，否则就 *10+下一位，直到最后的数为余数]]
2. 实现数学计算(double)：浮点数的⽐较不能直接⽤ == ⽐较，因为根据计算机中浮点数的表示⽅法，对于同⼀个⼩数，当⽤不同精度表示时，结果是不⼀样的，⽐如 float 的 0.1 和 double 的 0.1 ，直接⽤ == ⽐较就会输出不相等，所以可以使⽤⾃定义 eps = 1e-8 进⾏浮点数的⽐较：对于保留小数输出时要注意输出-0.00；比如说-0.004保留两位小数就是，要避免的话if(p3>-0.005&&p3<0)p3=0;加个判断条件
3. 实现时间和日期，数字相加有（60s，60m，24h向前进一和日期也是，数字的四舍五入round，如果是整数转为int，注意高位加一。然后就是输出格式问题
4. 使用c语言字符串应该注意结尾0，而string中没有，因此在字符数组定义时要多给几个空间避免出错。
5. 字符串对应输出时可以使用字符串数组，不要用switch case和条件判断。int变成string使用to_string函数，如果还要对应输出就可以str[num[i] - '0'];转到对应字符数组输出就行，PAT乙级1002 题写出这个数（与柳神思路比对），同理要进行多个数计数是用数组储存他们string(保证位数时注意前导零)或者int数组。当然太少也可以不用储存。1006 换个格式输出整数：[[代码#1006 不能对一大串括号整数运算使用++、--]]如果不是只有百位 1014 福尔摩斯的约会：[[代码#1014 福尔摩斯的约会:注意条件判断，什么字符该通过，什么不该，然后就是时间的变化进位，和格式化输出,使用字符串数组储存要输出的星期]]
6. 逻辑推理判断符合的字符串：1003 我要通过’PAT‘（找规律，数学题）：[[代码#1003 我的想法错误的原因时：每次A3并不是直接减两倍，而是减A1那么大。所以A3/A1要等于A2]]
7. 遍历找寻符合要求的字符，注意通过字符的条件判断 1014 福尔摩斯的约会(上面第五点)
8. 1009 说反话 ：[[代码#1009 思路一：直接储存字符串使用scanf的while循环while(scanf("%s",&str[i])!=EOF){ i++; }有空格所以用字符数组，或者使用vector 来存储。while(cin >> str)，然后反向输出，思路二：使用堆栈，push和pop思路3：使用fgets（）方法读取这一行字符串，存到一个一维数组中，之后遍历这个数组，以空格为判断条件，分别存入一个二维数组中，之后逆序输出这个数组。fgets(char *str,int num,FILE *stream);]]
9. 给⼀些数字字符串，求这些字符串拼接起来能够构成的最⼩的数字的⽅式：⽤ cmp 函数就能解决： bool cmp(string a, string b)
10. 通过空格和标点分隔每个独立单词：遍历字符串，使用临时变量储存(+=)每个不是标点或空格的字符，当读到空格或标点时对单词进行操作，并清空tmp
11. char a[] 的⻓度要⽤ strlen(a) ; 得到的⻓度是⾥⾯真实存储了字⺟的⻓度，不包括 \0 要输⼊⼀⾏的数据的话： 如果是 string s ，则⽤ getline(cin, s); 在头⽂件 #include ⾥⾯； 如果是 char str[100] , 则⽤ cin.getline(str, 100); 在头⽂件 #include ⾥⾯，也可以⽤ gets(str);#todo
12. 关于字符串提取有效元素：1052 卖个萌 1024 科学计数法 1058 选择题 1073 多选题常见计分法 1068 万绿丛中一点红：#todo

实际问题多重循环枚举逻辑条件判断处理（模拟）：

1. 循环内判断条件等于n，某个数不一定是和其他一样是整数。注意使用数学逻辑演算，多重循环某数相加，最后加不用+=，以免重复加
2. 当某些操作要移动多个位置，一个循环解决不了时，可一点一点移动使用for循环一位一位移动。1008 元素循环右移(2.逆序3.重复交换4.直接打印，先从逆转那打到尾，在从头打，很多时候直接打印出来会简单很多)：[[代码#1008元素循环右移(三种方法)：思路一：利用递归或者循环一次一次移动；思路二：将所有元素逆序，然后将前m位和后n-m位分别逆序]]
3. 狼人杀，模拟，逻辑题，这类题要注意题目是要求怎么怎么优先输出。他说的是按狼人序列小的，所以说，你一开始使用谁说谎来进行判断就会徒增麻烦。注意条件控制，这种题目其实不难。[[代码#1087 狼人杀：]]

优先，排序,大量数据查询操作：

1. 当大量的for循环是用来查找的时候就是该使用排序和二分查找的时候或者使用大数组下标
2. 只要输出最大最小或者少量数据时可以不用排序，使用中间变量记住就行。1004 成绩排名：[[代码#1004 要注意它说的字符串不超过十个字符，加上‘ 0’也就是11个；vector传引用为函数参数，然后vector在声明是并不会直接调用构造函数，然而在用c语言数组时会出现无无参构造函数的错误，当然也可以不写构造函数改为写复制构造函数。类定义完要加；]]
3. 对于题目要求很明显排序，这个时候一定要耐下性子来分析关系，写出合适的com函数，然后return可以写数1<数2来减少代码量 1015 德才论：加了一个level参数[[代码#1015 德才论：通过多组数据进行排序，主要考察对数据的理解写出com函数]]
4. 1100校庆(排序校友，在来宾中使用二分查找是否校友，因为还要统计非校友年龄最大所以这样遍历较为省事) 重点是确定好排序和二分查找的对象
5. map的使用：1003pat中元素(字符)个数对应<char,int>；1069 微博转发抽奖(stl容器一般自动初始化为0或空)；1080 mooc最终成绩(使用map来更好的对应输入实现map的键值排序)。当不需要排序时，使用unordered_map可以节省时间
6. 遇到链表中有⽆效结点还要排序的，在结构体⾥⾯加⼀个 bool flag = false; 变量，将有效结点的 flag 标记为 true ，并统计有效节点的个数 cnt ，然后在 cmp 函数中这样写：

   bool cmp(node a, node b) {  
   	if(a.flag == false || b.flag == false)  
   		return a.flag > b.flag;  
   	else  
   		return a.value < b.value;  
   }

这样 flag == false 的会⾃动变换到最后⾯去，到时候输出前 cnt 个有效的结点就可。如果问年龄区间内的前100个，⽽数据量很庞⼤的话，在处理数据的时候就可以把每个年龄的前100个选出来，然后再遍历，因为⽆论如何也不会超过100个，最极端的情况就是当前区间只包含⼀个年龄～
7. 1065 单身狗和1090危险物品集装箱。查找题目，有两种方法，第一种就是将要查找的人排序，然后通过二分查找（两边都要）确定是否含有冲突元素。第二种就是通过两个map用来找对称值。其实还有一种大数组方法，使用对应下标(这个只能在单身狗中使用)
8. 1095 解码PAT准考证，大量对点查询使用map或者unordered_map,使用printf就不会超时啦。排序传参建议⽤引⽤传参，这样更快，虽然有时候不⽤引⽤传参也能通过，但还是尽量⽤，养成好习惯

重要题目:
哈希散列：⽤数组 hash[26] 或者 hash[10] 保存某个字⺟或者数字出现的次数/是否曾经出现过；⽤ hash[256] 保存某个 ASCII码 字符是否出现过， exist[10000] 、 cnt[10000] 同理。只是使用这些操作时，使用hash散列比map快上不少；
1005 还是3n+1：采用的是打表法(如果访问次数多，且范围小可以打表)[[代码#1005 注意条件判断时确定跳过条件的同时要确定程序还会按着你的猜想继续执行下去，new的使用。还有就是本来可以使用库函数进行排序但是不熟悉。]]对每⼀个输⼊的数字n进⾏验证，把验证过的数字对应的arr标记为1，然后对这些输⼊的数字从⼤到⼩排序，输出所有arr=0的数字即为关键数字。

素数：1007 素数对猜想：打表以及判断函数[[代码#1007 素数对猜想 :注意条件不超过N，应该包括N，判断素数方法i+=2和sqrt；通过isprime函数判断i和i-2是否是素数不用数组储存]]1094 谷歌的招聘：注意开头的0也要输出和isprime小于等于一的判断

	// 素数表的建⽴  
	// ⾸先都标记为1，外层循环i从2到√n，内层循环j从2开始到i*j<n 把j的i倍都标记为0  
	vector<int> isprime(50000, 1);  
	for (int i = 2; i * i < 50000; i++)  
		for (int j = 2; j * i < 50000; j++)  
			isprime[j * i] = 0;

two pointer ：所谓two pointers问题，就是⽤ p 、 q 两个指针，使⽤ while 语句处理链表问题，链表什么的⽤ vector 存储就好了 1030完美数列 1035 插入与归并

贪心算法：
1070 结绳:[[代码#1070 floor，ceil，（int）round，格式化输出]]

打印题目：
1027 打印沙漏：[[代码#1027 打印沙漏：一个经典的打印题，分析清楚行数与每行打印个数的关系。]] 打印只能一个接一个，一行接一行打印。 1008元素循环右移，1050 螺旋矩阵

1066 图像过滤：[[代码#1066 图像过滤：大量输入输出使用scanf和printf]]

1069 微博转发抽奖：[[代码#1069 微博转发抽奖：map中使用find的返回值为迭代器，判断是否为end可分辨找没找到，同时map会把储存在其中的东西初始为空或者0，一般来说stl容器都是这样，然后就是%操作，要注意和排除负数%为0的情况即符合常理]]

1074宇宙无敌加法器和1079延迟的回文数：[[代码#1074宇宙无敌加法器和1079延迟的回文数：字符串（不）同进制加法实现，注意保证应有的满数进一，前导后导零和零的输出，然后就是stoi如果超过范围会产生越界错误，insert方法补足前0，保证位齐：]]和1113钱串子的加法，注意区分和火星数字

1080 mooc最终成绩:[[代码#1080 mooc最终成绩：map<string,stu>把stu里面的名字取出来作为键值，用来读入个人信息，然后遍历map将其stu存在结构体数组中进行排序，从而实现值排序]]

1081 检查密码：[[代码#1081 检查密码：注意用户可能输入空格作为密码，虽然不允许，但是要告知不合理，所以输入要getline，但是多行的getline要在循环前加入cin.get()，然后就是i和j不要写错了]]

1084 外观数列:[[代码#1084 外观数列:使用at和[]对字符串进行修改时，只能对已有字符的位置修改，而且要使字符串已有增加只能+=和其他类似方法]]

1010 一元多项式求导：[[代码#1010 一元多项式求导：注意输入时应使用 scanf因为能够通过可以按住Ctrl+z,再按enter键就可以手动结束，而我用的是cin以最后一位为0做为终点，显然不行。然后注意题目说的零多项式最后要表示为0 0，其实是在说明当只有一项且指数为0（常数项）时，要打印成0 0，用以区分什么都没输入时的情况。题目说的每句话都是很重要的输入数组的方式有两种，一种是按顺序系数和指数直接输入，还有就是在指数对应的位置输入系数即a [指数]=系数，注意此题有指数递减等字眼，且输出方式也是按照原来的递减所以两种都可以问题不大，但是要是没有说是递减要你从大到小那第二种容易很多，而且还可以相加。第二个代码更精巧]]