此篇博客以牛客平台为例,只适用于刚入门的朋友,请选择自己需要的部分查阅。
文章目录
一道题的组成
每个题目都由问题信息、题目描述(Description)、输入描述(Input)、输出描述(Output)、样例(Samples)五个部分组成,其中样例又分为样例输入(Samples Input)和样例输出(Samples Output)。
Part1.问题信息
很多刚开始做信息学题目的朋友可能会觉得这一部分是无关紧要的,但实际上,这一部分也提供了很多信息,甚至会影响你做题的方法。这一部分最关键的信息就是 时间限制1s (or 1000ms) 以及 空间限制32768K(or 32M) 。时间限制和空间限制的具体作用会在后面的常见错误类型与解决方法中进一步解释。
这里只说明一个情况 —— 特判(Special Judge)
关于特判(Special Judge)
大多数题目的正确答案是唯一的,而特判是指本题的正确答案不是唯一的。
举个例子:输出一个数字x,且10<x<20
那么我的输出是11是正确的,输出15同样也是正确的。
Part2.题目描述(Description)
这部分没有什么特殊的,就是对一道题目的陈述,值得一体的是信息学的题目大多数可是英文题目哦^^(国际大学生程序设计大赛ICPC以及中国大学生程序设计大赛CCPC等很多高级比赛大都是英文题目)。所以读不懂题目或者对题目理解有偏差也是很令人抓狂的一件事情o(╥﹏╥)o
Part3.输入描述(Input)
首先我们要知道,输入这件事情是计算机去做的而不是正在做题的你!(具体是计算机把已经准备好了的样例输入到你的程序中对比是否和结果一致)所以输入描述中给定的范围不是让你去限定的,而是告诉你计算机对你的程序进行测试的数据范围。 你需要做的是计算机输入给定区间数值时,你的程序能得出正确的答案!
比如:上面告诉你1<A,B<1000000,并不是让你去if(1<A<1000000 && 1<B<1000000)
。而是提醒你计算机要测试什么数据(肯定是这里面的)!这影响的是运行时间!(具体参考下面的常见错误类型与解决方法)
这里说明几种输入方式
单组输入
程序只进行一次,题目描述为:输入一组a,b,计算a和b的和。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<a+b<<endl;
}//只进行一次。
N组输入
程序进行N次,题目描述为:输入一个n,表示测试次数,每次输入一组a,b,计算a和b的和。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,n;
cin>>n;
while(n--) {
cin>>a>>b;
cout<<a+b<<endl;
//注意N组输入和多组输入每次结束都需要空行。
}
}//进行n次。
或者
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,n;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a>>b;
cout<<a+b<<endl;
//注意N组输入和多组输入每次结束都需要空行。
}
}//进行n次。
多组输入
程序进行多次(不确定何时结束),题目描述为:多组输入,每次输入一组a,b,计算a和b的和。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
while(cin>>a>>b) {//测试完毕自动结束
cout<<a+b<<endl;
//注意N组输入和多组输入每次结束都需要空行。
}
}//进行多次。
或者
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
while(scanf("%d%d",&a,&b)!=EOF) {EOF是end of file文件结尾
cout<<a+b<<endl;
//注意N组输入和多组输入每次结束都需要空行。
}
}//进行多次。
或者
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
while(~scanf("%d%d",&a,&b)) {
cout<<a+b<<endl;
//注意N组输入和多组输入每次结束都需要空行。
}
}//进行多次。
多组输入(条件结束)
程序进行多次(确定何时结束),题目描述为:多组输入,每次输入一组a,b,计算a和b的和,当a=b=0时,输入结束。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
while(cin>>a>>b && a+b) { //如果a和b同时为0时,a+b=0。
cout<<a+b<<endl;
//注意N组输入和多组输入每次结束都需要空行。
}
}//进行多次。
Part4.输出描述(Output)
这里只要注意输出的格式(例如,每行结尾不能有空格、每组输出后空一行etc.)如果不注意输出的要求,很容易就会出现格式错误(后面会提到)。
Part5.样例(Samples)
样例就是给你一组满足输入描述和输出描述的数据,是为了方便你更好地理解题意的。
并不是说,你的程序能成功运行样例就一定可以通过。后台测试的样例有很多,并没有完全展示给你,而展示给你的往往是最没有特点的几组例子,而边缘数据、特殊情况大都不会展示给你。(所以样例可能具有迷惑性,一定要特别注意,不要迷信样例)
但是做一些英文题目的时候,样例确实可以帮你理解题意,甚至有时候“面向样例程序设计” 。
常见反馈类型及错误的解决方法
1.答案正确(Accept)
大家都喜欢答案正确,当然我们的目标也就是答案正确(简称AC)。当你做的一组题目全部AC那就是AK(All-Killed)。(¯﹃¯),当然AK可遇而不可求!
2.答案错误(Wrong Answer)
也就是我们常说的WA。如果一套题你一个写不出来那就是AF(All-Failed),不过大家更习惯与说“爆零”了。
解决方法
答案错误就是你的程序出现了问题,这时候你就应该去捋顺一下自己程序的逻辑是否有漏洞,尤其是看一下边缘数据(左右端点、0点 etc.)是否有考虑到,必须要严谨,考虑周全才能成功!
再者就是自己的语法掌握不熟练产生的错误,这一类问题新手更容易犯错(比如:①if或for后面没有加大括号 ②if、else if、else使用不当导致输出多次 ③计算和的数组sum没有赋初值0 ④在i的循环里又开了一个i的循环导致第一层循环被修改。 etc.)
3.编译错误(Compile Error)
程序本身无法运行。
解决方法
犯这种错误大多数是因为没有运行就提交,程序本身就无法运行。虽然大多数平台CE错误不会罚时,但是粗心是不可取的!还有添加库函数(比如 #include<math.h>
),当然如果使用万能头文件(#include<bits/stdc++.h>
)就不存在这个问题。
当然也有一种情况是判题机的编译环境与你的编译环境版本不同(一般就是平台判题机版本比较低,而你用了比较新的操作,导致判题机看不懂)。这种情况比较少,大多数都是第一种!
(别写int mian()!!!)
4.格式错误(Presentation Error)
你的输出格式出现了问题。
解决方法
这就要仔细看一下输出描述的要求了,是否需要每次输出多添加一行空行?是不是末尾不能加空格?
主要的错误情况就是多空格少空格,多空行少空行的问题了(题目上一般都会有详细描述,如果没有,那就倒霉了,只能挨着试了)
5.时间超限(Time Limit Exceeded)
你的程序运行的时间太长了,超过了题目描述中要求的最大时间!
关于时间复杂度的问题
通常我们把计算机计算一次的时间作为1,如果你的程序是for(int i=1;i<=n;i++)
,那么我们说你的程序的时间复杂度是O(N),O就代表时间复杂度。如果你的程序是两层for循环那么时间复杂度是O(N2) ,同理三层就是O(N3)。(当然复杂度可能是O(2*N),通常我们会省略系数直接表示为O(N) )
也就是说当N = 10时,一层for循环时间复杂度是10,两层是100,三层是1000。
知道这些,我们即可以大体计算自己程序的时间复杂度了,然后我们需要知道的是:
判题机一般1000ms(1s)能跑1e7 - 1e8次(一般来说为1e7为极限)
那么就是说如果N = 1000时,O(N^3)的程序很显然时间复杂度是1e9,已经超过了1e7,那么他就不可能在1000ms内通过测试!
问题:输入一个n,求1到n所有数的和。(1<n<1000)
//我可以用时间复杂度为O(N)的for循环来写
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,sum=0;//sum = 0!!!
cin>>n;
for(int i=1;i<=n;i++)
sum+=n;
cout<<sum<<endl;
}
***************************************************
这样做很简单,那么我把问题修改一下。
问题:输入一个n,求1到n所有数的和。(1<n<1e9)
//这样用O(N)时间复杂度的式子一定会超时!
#include<bits/stdc++.h>
using namespace std;
int main(){
ll n;
cin>>n;
cout<<(1+n)*n/2;
}
//我们高中都学过等差数列的和 (首项+末项)* 项数 / 2;
//这样我们就成功的把O(N)的时间复杂度变成了O(1)。
解决方法
我们把可能出现的每一种情况都运算一遍的方法叫做暴力 遍历,稍微难一点的题也不会让你那么轻易的通过遍历来完成,大多数需要你自己来优化。就比如上面举的例子,有的情况是找规律,也有的情况是需要更高级的数据结构或算法来解决。
6.空间超限(Memory Limit Exceeded)
你的程序变量占用的空间超过了题目描述所提及的最大值。
解决方法
每一个数据类型都会占用一定的空间,具体细节可以自行查找。新手基本上不会遇到这样的问题。通常就是以时间换空间的方法解决。
7.输出超限(Output Limit Exceeded)
你的程序在输出完正确答案后又输出了一些奇怪的东西。
解决方法
看一下是不是没有把测试用的步骤给注释掉,或者题目有某些限制。(新手有可能是if 、else if 、else没有用正确)
8.运行时错误(Runtime Error)
数组越界(定义了a[10]只能使用a[0]-a[9],不能使用a[10])、除数为0(a/0)等非法使用内存的情况。
解决方法
数组开大 / 改变等式。
9.系统错误(System Error)
后台没有数据,无法判题。
解决方法
联系管理员!
关于编译器的几个问题
使用编译器可能会出现的几种情况导致无法运行或编译。
①[Error] ld returned 1 exit status
重复打开运行界面,上一个运行界面还没有关闭或者还没有运行完(运行完算是关闭)。只要关掉上一个运行界面就可以解决。
②[Error] conflicting declaration ‘int a [100]’
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a;
int a[100];
cin>>a;
cout<<a;
return 0;
}
同一个名称重复定义了一次会产生冲突,修改掉其中一个即可。
③[Error] redeclaration of ‘int x’
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
int x;
return 0;
}
在同一级内,定义了两遍相同名称的变量(for里面一个x外面一个x是可以通过编译的,他们不是同一级的)
④[Error] no matching function for call to ‘max(int, long long int&)’
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long b;
cin>>b;
cout<<max(0,b);
return 0;
}
max函数内左右两边的数需要数据类型相同,只要把0强制转换成long long即可。max((long long)0,b)
。
…………
常见的一些问题
①定义数组变量的时候用变量做下标
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n];
return 0;
}
虽然在一些版本的编译器中是可以通过编译的,但是有的平台是不允许这样开数组的。
如果告诉了你最多有多少个数,就开一个足够大的数组即可,比如假设最多有1000个元素那么我们可以int a[1005];
To Be Continue……发现了再写。