爱站程序员基地寒假前班主任帮我们报了名，是得好好准备准备。作为一个CSer，coding能力一定不能太弱。我反思，好久没写C/C++代码了，净是些随手写的python脚本，刚开始上手题目bug一大堆。
由于也不是啥特别的算法竞赛，就把列入这个系列吧。整理发出来，也就是一个回顾。
00 赛事了解
00-1 oi赛制
每道题提交之后都没有任何的反馈，每个题都有多个测试点，根据通过的测试点的数量，来给予分数。每道题不限提交次数，如果提交错误没有任何惩罚，仅以最后一次提交为准，比赛过程中看不到实时排名，赛后按照总得分排名。
输入输出明确按规定来做。
00-2 基础语法
要熟悉一门语言的语法，对于我来说就是C/C++，这一点需要再翻翻书，避免一些低级错误。
00-3 算法与数据结构
这一点需要再复习一下自己的数据结构学习笔记，然后再看看网课。确保自己刷题能够不卡顿。
00-4 刷题
- 洛谷的官方题单
- 蓝桥杯真题
- 北京大学的poj
- acwing
- 力扣（只有接口函数，不是完全，所以这点不好）
递归和暴力需要多练，保证自己有办法做出来题目。另外再学学贪心、搜索（深搜极其重要、广搜一般）、动态规划。
我此前练了几十道力扣，今天注册（0310）了洛谷，做了入门题目，大致了解了一下如何把一个题目通过。
关于如何找题，这个知乎博主回答得比较好：
- 在左侧栏里的题单广场里找，建议先做官方题单，再做用户分享题单
- 在左侧栏里的题库里找，要搜哪道题就直接搜就行，要搜哪种题就在高级搜索里添加算法标签就行，要搜哪种难度的题直接选择，还有不要只看主题库里的题，看看CodeForces，SPOJ，AtCoder，UVA的题都不错
- 还可以看主页的智能推荐（不过最近智能推荐挂了）
- 终极办法（不要经常用），直接发帖求题
01 0310
01-1 P1014 [NOIP1999 普及组] Cantor 表
01-1-1 题目描述
现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：
1/11/1,1/21/2 , 1/31/3, 1/41/4, 1/51/5, …2/12/1, 2/22/2 , 2/32/3, 2/42/4, …3/13/1 , 3/23/2, 3/33/3, …4/14/1, 4/24/2, …5/15/1, ……
我们以 Z 字形给上表的每一项编号。第一项是 1/11/1，然后是 1/21/2，2/12/1，3/13/1，2/22/2，…
输入格式
整数(1<= N <=10^7)。
输出格式
表中的第 N 项。
01-1-2 输入输出样例
输入
7
输出
1/4
01-1-3 解决代码
#include <iostream>using namespace std;int main(){int n = 0, sum = 0, i = 1;cin >> n;while(sum < n){++i;//这里用for在循环上不太好，一定要让i先自增再求和，否则求出来的和少一项sum = i*(i - 1)/2;//首项公差均为1的等差数列求和，此处的和为第i行为止的Cantor表的总项数}//总项数与所找项的项数的差int sub = sum - n;if(i % 2 != 0)//如果i奇数，从左开始数cout << i - 1 - sub << "/" << 1 + sub;else//第i行为偶数行，从右边数cout << 1 + sub<< "/" << i - 1 - sub;}
01-2 P1035 [NOIP2002 普及组] 级数求和
01-2-1 题目描述
已知：
S_n= 1+\\frac{1}{2}+\\frac{1}{3}+…+\\frac{1}{n}
显然对于任意一个整数 k，当 n 足够大的时候，有Sn>k；现给出一个整数 k，要求计算出一个最小的 n，使得 Sn > k。
输入格式
一个正整数 k。
输出格式
一个正整数 n。
01-2-2 输入输出样例
输入
1
输出
2
01-2-3 解决代码
这个题没什么好说的，唯一值得注意的是C语言除法里的类型转换，由于sum是double，如果两个整数用 ‘/’ 运算符，会得到一个整数，所以得用
1./i
。
#include<iostream>using namespace std;int main(){int k;cin >> k;double sum = 0;int count = 0,i = 1;while(sum <= k){sum += 1./i;count = i;i++;}cout << count << endl;return 0;}//思路很简单，但最重要的是要注意1./i的数据类型转换//改为1/i就会死循环
01-3 P1046 [NOIP2005 普及组] 陶陶摘苹果
01-3-1 题目描述
陶陶家的院子里有一棵苹果树，每到秋天树上就会结出 10 个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个 30 厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知 10 个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。
输入格式
输入包括两行数据。第一行包含 10 个 100 到 200 之间（包括 100 和 200 ）的整数（以厘米为单位）分别表示 10 个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个 100 到 120 之间（包含 100 和 120 ）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。
输出格式
输出包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。
01-3-2 输入输出样例
输入
100 200 150 140 129 134 167 198 200 111110
输出
5
01-3-3 解决代码
一遍过了，就是循环 / 判断结构。
#include<iostream>using namespace std;int main(){int apple[10]={0};for(int i = 0; i < 10; i++){cin >> apple[i];}int height;cin >> height;int count = 0;for(int i = 0; i < 10; i++){if((height+30) >= apple[i]){count++;}}cout << count;return 0;}//值得注意的是够不着会踩板凳 +30
02 0311
02-1 P1047 [NOIP2005 普及组] 校门外的树
02-1-1 题目描述
某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位置；数轴上的每个整数点，即 0,1,2,...,L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
第一行有两个整数，分别表示马路的长度 L 和区域的数目 m。接下来 m 行，每行两个整数 u, v，表示一个区域的起始点和终止点的坐标。
输出格式
输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。
02-1-2 输入输出样例
输入
500 3150 300100 200470 471
输出
298
说明 / 提示 | 数据范围：
-
对于 20% 的数据，保证区域之间没有重合的部分。
-
对于 100% 的数据，保证：
1 \\leq L \\leq 10^4 \\\\1 \\leq m \\leq 100，\\\\0 \\leq u \\leq v \\leq L
02-1-3 解决代码
这基本就是查表思想，如果树在拆的范围内，就给标志一下，重复拆也是给相同的标志，最后遍历输出树的数组，如果没有标志，则说明是剩余下来的。
不过值得注意的代码后面我也列出来了：
- 弄清楚取值范围，题目中是从0到L，左闭右闭；
- 提交代码要注释掉测试的代码；
#include<iostream>using namespace std;int main(){int n,m;cin >> n >> m;int A[n+1]={0};// for(int i = 0; i < n; i++){// A = 1;// }int B[m][2];for(int i = 0; i < m; i++){for(int j = 0; j < 2; j++){cin >> B[i][j];}}// for(int i = 0; i < m; i++){// for(int j = 0; j < 2; j++){// cout << B[i][j]<<endl;// }// }for(int i = 0; i < m; i++){for(int cnt = B[i][0];cnt<=B[i][1];cnt++){A[cnt] = 1;}}// for(int i = 0; i < n; i++){// cout << A[i]<<endl;// }int count = 0;for(int i = 0; i <= n; i++){//cout << A[i]<<endl;if(A[i]==0){count++;}}cout << count;return 0;}//这个题不难，遇到了几个问题：1.题目审题，数组的范围是什么，是0到l，左闭右闭2.提交代码，把一些测试用的代码没有注释掉就交了
02-2 P1059 [NOIP2006 普及组] 明明的随机数
02-2-1 题目描述
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数(N≤100)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式
输入有两行，第1行为1个正整数，表示所生成的随机数的个数N*第2行有N*个用空格隔开的正整数，为所产生的随机数。
输出格式
输出也是两行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M*个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
02-2-2 输入输出样例
输入
1020 40 32 67 40 20 89 300 400 15
输出
815 20 32 40 67 89 300 400
02-2-3 解决代码
这道题在大体思路上很清晰，但在具体细节上还是有点意思的。所以虽然是一遍过，但是花费时间还是久了点。
具体细节就是：
- 排序可以直接排。
- 删除元素我有两种考虑，一种是双指针，即一个为主指针，另一个辅助指针以主指针为起点向后探测，如果与主指针值相同则继续向后，直到不同，再让主指针直接跳跃过去，这种需要建立一个新数组来存主指针指到过的值。
- 另外一种就是哈希表了，毕竟也是学过数据结构刷过几道力扣的人了，哈希表虽然空间复杂度高一些，但时间上很不错，思路实现上更简单。于是最终使用的是哈希表。4.由于对于STL的不熟悉，在原数组上动刀的事情目前干不出来。说来也是惭愧，STL当初在一个项目上好好学了，现在却不能熟练的用出来。
#include<iostream>#include<algorithm>using namespace std;int main(){int N;cin >> N;int A;for(int i = 0; i < N; i++){cin >> A[i];}sort(A,A+N);// for(int i = 0; i < N; i++){// cout << A[i] << " ";// }// 排序完成，下面看看能不能删掉重复的int hash[1000]={0};for(int i = 0; i < 1000;i++){for(int j = 0; j < N; j++){if(A[j]==i){hash[i]=1;}}}//cout << endl;int count = 0;int result[100]={0};int j = 0;for(int i = 0; i < 1000; i++){if(hash[i]==1){//cout << i+1 << " ";result[count++]=i;}}cout << count << endl;for(int i = 0; result[i]!=0&&i<100;i++){cout << result[i]<< " ";}//哈希表实现//双指针// for(int i = 0; i<N;i++){// for(int j = i+1; j < N;j++){// if(A[j]!=A[i]){// break;// }// }// }return 0;}
02-3 P1075 [NOIP2012 普及组] 质因数分解
02-3-1 题目描述
已知正整数n是两个不同的质数的乘积，试求出两者中较大的那个质数。
输入格式
一个正整数n。
输出格式
一个正整数p*，即较大的那个质数。
02-3-2 输入输出样例
输入
21
输出
7
说明/提示
n\\le 2\\times 10^9
02-3-3 解决代码
这道题考察一个基础的数论知识：
唯一分解定理:一个数能且只能分解为一组质数的乘积。
并且还要明白，题目中的一个正整数，可以被分解为两个质数对于测试数据的限制，自己就不要打23或是45这种数据来测试，因为根本就不在范围内。
#include<iostream>using namespace std;int main(){long int num, i;cin >> num;for( i = 2 ; i * i < num; i++){if(num%i==0){break;}}cout << num/i <<endl;}//实现挺简单的，可以从num开始--，也可以从2开始++求出小质数再求大质数。
02-4 P1085 [NOIP2004 普及组] 不高兴的津津
02-4-1 题目描述
津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。
输入格式
输入包括7行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。
输出格式
一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1, 2, 3, 4, 5, 6, 71,2,3,4,5,6,7分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。
02-4-2 输入输出样例
输入
5 36 27 25 35 40 40 6
输出
3
02-4-3 解决代码以及优化
思路很简单，甚至我写起来还会显得笨手笨脚的（代码有点啰嗦）一步一步的太笨重。
值得注意的是最后的tag判断，如果把放到最外一层的for循环内部，最后一组数据会出错，当时结果出来还有点头疼，后来意识到是放在循环里可能会导致一些不能预料的结果。
#include<iostream>#include<algorithm>using namespace std;int main(){int data[7][2],sum[7];for(int i = 0 ; i < 7; i++){for(int j = 0; j < 2; j++){cin >> data[i][j];}}for(int i = 0; i < 7; i++){sum[i] = data[i][0] + data[i][1];}int count = 0, tag = 0;for(int i = 0; i < 7; i++){if(sum[i]<=8){tag++;continue;}else{int* temp = max_element(sum,sum+7);for(int j = 0; j < 7; j++){if(sum[j]==*temp){cout << j+1 <<endl;break;}}break;}}if(tag==7){cout << 0 << endl;}return 0;}//奥对，最重点的是使用了一个直接求数组中最大值的函数max_element,返回值是一个指针//还是被此前项目函数调包什么的惯坏了，数据结构老师要是知道了得骂死我。
由于觉得自己写的实在是太笨重了，我决定看看题解，发现我被数组牢牢地束缚住了，离开数组就很难做事情。就比如下面洛谷题解中赞最多的这一个(个人手打，原作者争持Zill）：
#include<iostream>using namespace std;int main(){int num1，num2, sum;int day = 0, max = 0;for(int i = 1; i < 8; i++){cin >> a >>b;sum = num1 + num2;if((s > max)&&(sum>8)){max = sum;day =i;}}cout << day;return 0;}
还有一个作者，直接顺序分支结构，确实，题目中明确只有七组数，七个if语句就可以解决。按照复杂度理论，将会是O(1)，hhhh。（实际上是用手写所有if来代替循环了。
03 0312 / 0315
事实上这期间只写了这一道题（除了上一道题在0312也有一些工作，比如看题解），因为有其他的事情，练题计划中断了（比如写Java作业、复变、概率论作业等等）。0312的思路没写出来，0315晚上灵机一动，有了另一种解决方案。
03-1 P1089 [NOIP2004 提高组] 津津的储蓄计划
津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。例如11月初津津手中还有83元，妈妈给了津津300元。津津预计1111月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。
输入格式
12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。
输出格式
一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到20042004年年末津津手中会有多少钱。注意，洛谷不需要进行文件输入输出，而是标准输入输出。
03-1-2 输入输出样例
输入1
29023028020030017034050908020060
输出1
-7
输入2
29023028020030017033050908020060
输出2
1580
03-1-3 解决代码
这道题在说法上比较绕。
第一步，输入当月预算cost，+上月剩余last1到剩下的钱last2，300+0-290=10，
第二步，判断是否>=100：
如果大于，则减去整百部分，
如果小于，继续一二步。
第三步，如果12个月循环完毕一直是小于，那就输出last+save*1.2
如果>=100后，last取负值，则输出当月的月份。
上述编程的逻辑问题就在一处，即，第三步中的，last取负值的判定，我采用的是last<0，则输出此前记录的月份的负值，问题就在于last最后不一定<0
//上面思路走不下去，借鉴题解再来一次#include<iostream>using namespace std;int main(){int money = 0, cost[12] = {0}, save = 0, flag = 1, failid = 0;for(int i = 0; i < 12; i++){cin >> cost[i];}for(int i = 1; i <= 12; i++){money+=300;//cin >> cost;money-=cost[i-1];if(money<0){flag = 0;//说明已经透支failid = i;break;}save+=money/100;//用100的个数代替100money%=100;//存款后剩余的前//与我最初的思路相差在于，我冗余了一个判断是否超过100的语句//事实上money不超过100的话，%100还是它自己。}if(flag==1){money+=save*120;cout << money;}else{cout <<-failid;}return 0;}
