本文主要是介绍ACM—NYOJ小小结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
我觉得做题不是越多越好,而是善于总结!
做南阳理工题目也有一段时间了,我觉得还是有必要总结一下,把以前做过的题目再重新看看,提取其中的知识点,重点,达到灵活运用才是王道!
算法的五个特点: 1. 能行性(或有效的) 2. 有限性 3. 确定性 4. 输入 5. 输出
一、基本输入:
每道题目基本上都要求输入数据,因此你的程序要准确接收输入的数据,这步做好了,下面的才有可能进行,并且输入都得有个结束标示,不然一直输入是不可能的吧。下面对这些基本的输入做些总结。
1. 先输入一个整数,代表测试数据组数
例如:第一行输入一个数N(0<N<=100),表示有N组测试数据
我一般这样写代码
int n;
scanf("%d",&n);
while(n--)
{//........核心程序
}
这样看起来简洁,直接n--
不过结尾如果要求输出 case n : .....
用个for循环比较好,循环一次,case++;
2.没有说明几组测试数据的,一般是以EOF结束输入,或者指明EOF结束
C语法:while( scanf("%d %d",&a, &b) != EOF) { .... }
C++语法:while( cin >> a >> b ) { .... }
Scanf函数返回值就是读出的变量个数,
如:scanf( “%d %d”, &a, &b ); 如果a和b都被成功读入整数,那么scanf的返回值就是2; 如果只有a被成功读入整数,返回值为1;
如果a和b都未被成功读入整数,返回值为0;
如果遇到错误或遇到end of file,返回值为EOF
EOF是一个预定义的常量,等于-1。
3.输入不说明有多少个Input Block,但以某个特殊输入为结束标志。
Input contains multiple test cases. Each test case contains a pair of integers a and b, one pair of integers per line.
A test case containing 0 0 terminates the input and this test case is not to be processed.
2010-10-13
20
本类输入解决方案:
C语法:
while(scanf("%d",&n) && n!=0 ) { .... } C++语法:
while( cin >> n && n != 0 ) { .... }
4.输入是一整行字符串的:
C语法:char buf[20]; gets(buf);
C++语法:如果用string buf;来保存:getline( cin , buf ); 如果用char buf[ 255 ]; 来保存: cin.getline( buf, 255 );
scanf(“ %s%s”,str1,str2),在多个字符串之间用一个或多个空格分隔;
若使用gets函数,应为gets(str1); gets(str2); 字符串之间用回车符作分隔。
通常情况下,接受短字符用scanf函数,接受长字符用gets函数。
而getchar函数每次只接受一个字符,经常c=getchar()这样来使用。
getline 是一个函数,它可以接受用户的输入的字符,直到已达指定个数,或者用户输入了特定的字符。它的函数声明形式(函数原型)如下:
iostream& getline(char line[], int size, char endchar = '\n');
不用管它的返回类型,来关心它的三个参数:
char line[]: 就是一个字符数组,用户输入的内容将存入在该数组内。
int size : 最多接受几个字符?用户超过size的输入都将不被接受。
char endchar :当用户输入endchar指定的字符时,自动结束。默认是回车符。
结合后两个参数,getline可以方便地实现: 用户最多输入指定个数的字符,如果超过,则仅指定个数的前面字符有效,如果没有超过,则用户可以通过回车来结束输入。
char name[4];
cin.getline(name,4,'\n');
由于 endchar 默认已经是 '\n',所以后面那行也可以写成:
cin.getline(name,4);
5.接受字符串,以一个空行结束
while( gets(str) )
{....}
(粘贴吧,太累了。。)
二、输出问题
一个Input Block对应一个Output Block,OutputBlock之间空行。
l ProblemDescription
Your task is to calculate the sum of some integers.
l Input
Input contains an integer N in the first line, and then N lines follow. Eachline starts with a integer M, and then M integers follow in the same line.
l Output
For each group of input integers you should output their sum in one line, andyou must note that there is a blank line between outputs.
l Sampleinput
3
4 1 2 3 4
5 1 2 3 4 5
3 1 2 3
l Sampleoutput
10
15
6
C语法:{ .... printf("%d\n\n",ans);}C++语法:{ ... cout << ans << endl<< endl;
}
2.输出数据中间有空行,最后一个数据后面没有空行
C语法:{ .... printf("%d\n\n",ans);}C++语法:{ ... cout << ans << endl<< endl;
}
C语法:
for (k=0;k<count;k++)
{ while (…) { printf(" %d\n",result); } if (k!=count-1) printf("\n");
}
for (k=0;k<count;k++)
{ while (…) { printf(" %d\n",result); } if (k!=count-1) printf("\n");
}
l http://acm.hdu.edu.cn/showproblem.php?pid=1016
l http://acm.hdu.edu.cn/showproblem.php?pid=1017
初学者常见问题
编译错误
l Main函数必须返回int类型(正式比赛)
l 不要在for语句中定义类型
l __int64不支持,可以用long long代替
l 使用了汉语的标点符号
l itoa不是ANSI函数
能将整数转换为字符串而且与ANSI标准兼容的方法是使用sprintf()函数
int num = 100;
char str[25];
sprintf(str, " %d" , num);
l 另外,拷贝程序容易产生错误
不常规的编程方式
l Printf和cout混用的问题
l 以下的程序输出什么?
l #include<stdio.h>
l #include<iostream.h>
l int main()
l {
l int j=0;
l for(j=0;j<5;j++)
l {
l cout<<"j=";
l printf("%d\n",j);
l }
l return 0;
l }
什么问题?
l 一个带缓冲输出(cout)
l 一个不带缓冲输出(printf)
l Goole你的问题,充分利用网络资源
ACM菜鸟的21个经典错误
以HDU1089 A+B为例
l SampleInput
l 1 5
l 10 20
l SampleOutput
l 6
l 30
菜鸟之伤(1)
#include<stdio.h>void main(){l int a,b;scanf(“%d%d”,&a,&b);printf(“%d\n”,a+b);}
#include<stdio.h>void main(){l int a,b;scanf(“%d%d”,&a,&b);printf(“%d\n”,a+b);}
菜鸟之伤(1)
l 总结:
程序不能处理多组数据的问题是最常见的入门问题,只要掌握几种常见的类型,就可以轻松掌握了,具体处理方法曾在第一次课件有详细描述,这里省略了~
菜鸟之伤(2)
#include<stdio.h>void main()
{int a,b;while(scanf(“%d%d”,&a,&b)!=0)printf(“%d\n”,a+b);
}
菜鸟之伤(2)
l 总结:文件结束符EOF的值是-1而不是0,所以while(scanf(…)!=0)常常会因为死循环而造成TLE,这个必须牢记。
l 说明:不仅仅菜鸟,很多老鸟也常常因为不注意这点而犯错误,而且还常常因为想不到会犯这种低级错误而想不到原因。
菜鸟之伤(3)
#include<stdio.h>void main()
{int a,b;while(scanf(“%d%d”,&a,&b)!=EOF); //这里多了分号printf(“%d\n”,a+b);}
#include<stdio.h>void main()
{int a,b;while(scanf(“%d%d”,&a,&b)!=EOF); //这里多了分号printf(“%d\n”,a+b);}
菜鸟之伤(3)
l 总结:while 或者 for循环的条件外面误加了分号,编译不影响,但是结果循环体没有真正得到多次执行;
l 说明:菜鸟常犯的错误,往往因为编译能通过而不能迅速察觉,尤其比赛中~
l 提醒:当你将scanf();语句加上while循环以处理多组数据问题的时候尤其注意——因为之前有分号,很容易忘记去掉!
菜鸟之伤(4)
#include<stdio.h>void main(){int a,b;while(scanf(“%d%d”,&a,&b) =2) //应为-1 或 EOFprintf(“%d\n”,a+b);}
#include<stdio.h>void main(){int a,b;while(scanf(“%d%d”,&a,&b) =2) //应为-1 或 EOFprintf(“%d\n”,a+b);}
菜鸟之伤(4)
l 总结:
C语言中,赋值符号=和判断是否相等的逻辑符号==具有完全不同的含义,往往因为我们的习惯问题,在编程中误将判断是否相等的逻辑符号写成赋值符号=。同样的,这种失误也会因为不影响编译而影响查错的时间。
l 说明:菜鸟常犯的错误,但是有过几次教训就会牢记了,呵呵~
以HDU1001 Sum Problem为例
l SampleInput
l 1
l 100
l SampleOutput
l 1
l 5050
菜鸟之伤(5)
#include<stdio.h>void main(){ int i,n,s;while(scanf(“%d”,&n) ==1){for(i=1;i<=n;i++)s+=i; //s为初始化printf(“%d\n\n”,s);}}
#include<stdio.h>void main(){ int i,n,s;while(scanf(“%d”,&n) ==1){for(i=1;i<=n;i++)s+=i; //s为初始化printf(“%d\n\n”,s);}}
菜鸟之伤(5)
l 总结:
忘记变量的初始化是典型的菜鸟问题,不必紧张,多经历几次就牢记了~
l 说明:普通变量的初始化还比较容易查找,而用来保存计算结果的数组的初始化更是容易忘记!
菜鸟之伤(6)
#include<stdio.h>void main(){ int i,n,s=0;while(scanf(“%d”,&n) ==1){for(i=1;i<=n;i++)s+=i; //第二次循环s的初始值不一定为0printf(“%d\n\n”,s);}}
#include<stdio.h>void main(){ int i,n,s=0;while(scanf(“%d”,&n) ==1){for(i=1;i<=n;i++)s+=i; //第二次循环s的初始值不一定为0printf(“%d\n\n”,s);}}
菜鸟之伤(6)
l 总结:变量初始化放在循环外,是一个典型的ACM初级错误,因为ACM赛题的多组测试特性,如果不能在循环内初始化,将只能确保第一组数据没问题,而很多入门者习惯只测试一组数据,很容易忽略这个问题。
l
l 说明:菜鸟常犯的错误,关键是要理解为什么这样会有问题,真正理解后,修改也就不难了。
菜鸟之伤(7)
#include<stdio.h>void main(){int i,n,s;while(scanf(“%d”,&n) ==1){s=n*(n+1)/2; //s有可能越界溢出printf(“%d\n\n”,s);}}
#include<stdio.h>void main(){int i,n,s;while(scanf(“%d”,&n) ==1){s=n*(n+1)/2; //s有可能越界溢出printf(“%d\n\n”,s);}}
菜鸟之伤(7)
l 总结:
数组越界还能在提交后收到Runtime Error的信息反馈,而运算中的数据溢出则往往只能收到Wrong Answer的错误提示,所以这种错误往往容易被误导成算法问题;
l 说明:
不仅菜鸟,就是大牛甚至大神,也常常犯这种错误,只是情况复杂些而已~
菜鸟之伤(8)
#include<stdio.h>void main(){int i,n,s;while(scanf(“%d”,&n) ==1){s=n/2*(n+1);printf(“%d\n\n”,s);//结果为整数}}
#include<stdio.h>void main(){int i,n,s;while(scanf(“%d”,&n) ==1){s=n/2*(n+1);printf(“%d\n\n”,s);//结果为整数}}
菜鸟之伤(8)
l 总结:
当两个整数进行运算的时候,运算结果一定还是整数,所以不要因为常规数学惯性思维的影响而认为结果可能为浮点数;
而不同数据类型一同运算的时候,运算结果的数据类型和相对复杂的类型一致(比如 整数+实数,结果类型是实数)
菜鸟之伤(9)
#include<stdio.h>void main(){ int i,n,s;while(scanf(“%d”,&n)==1) //丢失大括号,使得循环体不完整而出错if(n%2==0)s=n/2*(n+1);elses=(n+1)/2*n;printf(“%d\n\n”,s);}
#include<stdio.h>void main(){ int i,n,s;while(scanf(“%d”,&n)==1) //丢失大括号,使得循环体不完整而出错if(n%2==0)s=n/2*(n+1);elses=(n+1)/2*n;printf(“%d\n\n”,s);}
菜鸟之伤(9)
l 总结:
写for或者while等任何循环语句的时候,不管循环体内有几个语句,务必养成都加上一对大括号的好习惯。
l 常常碰到的情况是这样的——本来循环体内只有一条语句,确实不用大括号,但是在修改程序的过程中,循环体内增加了其他语句,而这时却忘记了添加大括号!
l 所以说——好习惯很重要!
菜鸟之伤(10)
#include<stdio.h>void main(){ int i,n,s;while(scanf(“%d”,&n)==1){ if(n%2==0)s=n/2*(n+1);elses=(n+1)/2*n; }printf(“%d\n\n”,s); //没包含到大括号里面,没有循环}
#include<stdio.h>void main(){ int i,n,s;while(scanf(“%d”,&n)==1){ if(n%2==0)s=n/2*(n+1);elses=(n+1)/2*n; }printf(“%d\n\n”,s); //没包含到大括号里面,没有循环}
菜鸟之伤(10)
l 总结:
这也是一个经典错误,虽然为循环体加了大括号,但是并没有包含全部的信息,造成的后果是只有一次输出——尽管对于每组数据都处理了,但是只输出最后一组结果。
l 由于很多同学习惯每次只测试一组数据,就更容易忽略这个错误了...
l 再次证明——好习惯很重要!
菜鸟之伤(11)
l 假设不会中间溢出,下面的程序是否有问题?
l #include<stdio.h>
l void main()
l { int i,n,s;
l while(scanf(“%d”,&n) ==1)
l {
l s=n(n+1)/2;
l printf(“%d\n\n”,s);
l }
l }
菜鸟之伤(11)
l 总结:
这也是受数学习惯影响而可能出现的一个错误,当然,这个错误很好检查,因为编译不能通过的~
l 总结出这个只是因为确实会出现这个情况,而对于极度没有编程经验的同学来说,有时候也会带来困扰~
还是以A+B为例
l 题目描述:计算A+B的值,输入数据每行包含2个正整数,如果输入数据是两个负数,则结束输入。
l SampleInput
l 1 5
l -1 -1
l SampleOutput
l 6
菜鸟之伤(12)
#include<stdio.h>void main(){int a,b;while(scanf(“%d%d”,&a,&b)==2){ if(a==-1& b==-1) return; //相与应用 &&printf(“%d\n”,a+b);} }
#include<stdio.h>void main(){int a,b;while(scanf(“%d%d”,&a,&b)==2){ if(a==-1& b==-1) return; //相与应用 &&printf(“%d\n”,a+b);} }
菜鸟之伤(12)
l 总结:正如判断相等要用“==”一样,C语言中进行逻辑与的运算也是需要两个字符“&&”,类似的逻辑或运算也是两个字符“||”,如果是单个的字符,含义就完全不同了~
菜鸟之伤(13)
l 上一个程序的改进版:
#include<stdio.h>void main(){int a,b;while(scanf(“%d%d”,&a,&b)==2){ if(a==-1&& b==-1) return;printf(“%d\n”,a+b);} }
#include<stdio.h>void main(){int a,b;while(scanf(“%d%d”,&a,&b)==2){ if(a==-1&& b==-1) return;printf(“%d\n”,a+b);} }
菜鸟之伤(13)
l 总结:题目描述是负数结束输入,Sample Input最后给出的是-1,如果读题不仔细,很容易陷入思维定势,而会不加思索在程序中用-1判断,这样就真的会发生不幸的事件——尽管我也认为这个陷阱有点阴,而且未必有很大意义,但是题目并没错,而你确实读题不仔细~
l 说明:算是经典的小陷阱,现在很少出现了
继续以A+B为例
l 题目描述:给定2个整数A和B,如果A+B>0,请输出”OK!”,否则请输出”No~”
l SampleInput
l 1 5
l 1 -5
l SampleOutput
l OK!
l No~
菜鸟之伤(14)
#include<stdio.h>void main(){int a,b;while(scanf(“%d%d”,&a,&b)==2){if(a+b>0) printf(“OK!\n”);else printf(“NO~\n”); } //大小写与题目不符}
#include<stdio.h>void main(){int a,b;while(scanf(“%d%d”,&a,&b)==2){if(a+b>0) printf(“OK!\n”);else printf(“NO~\n”); } //大小写与题目不符}
菜鸟之伤(14)
l 总结:字符串输出的大小写问题对于菜鸟需要特别注意,其实,不管是——全大写、全小写,还是首字母大写,你尽管复制即可(没有电子版,另当别论),当然还要注意是否有标点符号等情况。
l 说明:菜鸟常犯错误,稍有经验即可避免
以1170Balloon Comes!为例
l SampleInput
l 4
l + 1 2
l - 1 2
l * 1 2
l / 1 2
菜鸟之伤(15)
int n,a,b,i;char p;scanf("%d",&n);for(i=0;i<n;i++){scanf("%c%d%d",&p,&a,&b); // 第一个%c接受的可能是输入n之后的换行符if( ……)}
int n,a,b,i;char p;scanf("%d",&n);for(i=0;i<n;i++){scanf("%c%d%d",&p,&a,&b); // 第一个%c接受的可能是输入n之后的换行符if( ……)}
菜鸟之伤(15)
刚才程序的改进版:int n,a,b,i;char p;scanf("%d",&n);getchar(); //这里吸收输入n之后的 ''for(i=0;i<n;i++){scanf("%c%d%d",&p,&a,&b);if( ...) ……}
刚才程序的改进版:int n,a,b,i;char p;scanf("%d",&n);getchar(); //这里吸收输入n之后的 ''for(i=0;i<n;i++){scanf("%c%d%d",&p,&a,&b);if( ...) ……}
l 是否还有问题?如何修改? (只接受的第一次的'\n')
菜鸟之伤(15)
l 总结:字符和数字的混合输入带来的问题,也是一个常常困扰使用C语言编程的同学的经典问题,关键就是程序未能及时接收回车符,而误将回车当作下一组数据的首字母,你可以通过添加一句getchar(); 轻松解决该问题。
l 说明:菜鸟的经典错误,如果之前没有遇到过,很难一下子反应过来,当然,遇到一次以后就不成为问题了~
2007 平方和与立方和
l 给定一段连续的整数,求出他们中所有偶数的平方和以及所有奇数的立方和。
l SampleInput
l 1 3
l 2 5
l SampleOutput
l 4 28
l 20 152
菜鸟之伤(16)
#include<stdio.h>void main(){ int m,n;while(scanf(“%d%d” ,&m,&n) ==2){ int i,x=0,y=0;for(i=m;i<=n;i++){ if(i%2==0) y=y+i*i;else x=x+i*i*i; }printf(“%d %d\n”,y,x);}}
#include<stdio.h>void main(){ int m,n;while(scanf(“%d%d” ,&m,&n) ==2){ int i,x=0,y=0;for(i=m;i<=n;i++){ if(i%2==0) y=y+i*i;else x=x+i*i*i; }printf(“%d %d\n”,y,x);}}
菜鸟之伤(16)
l 总结:题目并没有保证数据是递增的,但人往往有思维定势,而很多题目的设计就是针对这一点!不要埋怨,这种训练能很好的培养我们审慎的思维习惯。
l 说明:这种错误经历过以后还是比较容易牢记的,所以说有时候经验很重要。
菜鸟之伤(17)
l 以下的程序输出什么?
#include<stdio.h>#include<iostream.h>int main(){int j=0;for(j=0;j<5;j++){cout<<"j="; // 尽量不要c与c++混合使用printf("%d\n",j);}return 0;}
#include<stdio.h>#include<iostream.h>int main(){int j=0;for(j=0;j<5;j++){cout<<"j="; // 尽量不要c与c++混合使用printf("%d\n",j);}return 0;}
菜鸟之伤(17)
l 期望输出:
l j=0
l j=1
l j=2
l j=3
l j=4
菜鸟之伤(17)
l 总结:在一个程序中同时使用C和C++的输出语句,很容易带来问题,原因就是输出机制不完全一样(一个不带缓冲,一个带缓冲),所以尽量避免C和C++输出语句混用。
l 说明:这是传说中的经典错误,据说曾困扰某牛人于现场赛 :-)
以2004成绩转换为例
l 题目描述:输入一个百分制的成绩t,将其转换成对应的等级,具体转换规则如下:
90~100为A;
80~89为B;
70~79为C;
60~69为D;
0~59为E;
l 输出描述:对于每组输入数据,输出一行。如果输入数据不在0~100范围内,请输出一行:“Score iserror!”。
菜鸟之伤(18)
#include<stdio.h>int main(){ int t,a;while(scanf("%d",&t)!=EOF){ if(t>100||t<0) printf("Score iserror!\n");else{ a=(t-50)/10;switch(a) //注意case的break;{ case 5:case4:printf("A\n"); case3:printf("B\n");case2:printf("C\n"); case1:printf("D\n");default:printf("E\n"); } } }return 0;}
#include<stdio.h>int main(){ int t,a;while(scanf("%d",&t)!=EOF){ if(t>100||t<0) printf("Score iserror!\n");else{ a=(t-50)/10;switch(a) //注意case的break;{ case 5:case4:printf("A\n"); case3:printf("B\n");case2:printf("C\n"); case1:printf("D\n");default:printf("E\n"); } } }return 0;}
菜鸟之伤(18)
l 总结:C语言中的case语句要求在每个case的处理后面都要跟break;(特殊需求除外),而如果因为不了解或者不小心而缺少部分break;则执行的效果也许会不符合你最初的设计。
l 说明:C语言的基本功很重要~
以2046骨牌铺方格为例
l 题目描述:在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
l 输入描述:输入数据由多行组成,每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n(0<n<=50)。
菜鸟之伤(19)
#include<stdio.h>int main(){int i;__int64 a[50]={0,1,2};//数组开的小for(i=3;i<=50;i++)a[i]=a[i-1]+a[i-2];while(scanf("%d",&i)!=EOF){printf("%I64d\n",a[i]); }}
#include<stdio.h>int main(){int i;__int64 a[50]={0,1,2};//数组开的小for(i=3;i<=50;i++)a[i]=a[i-1]+a[i-2];while(scanf("%d",&i)!=EOF){printf("%I64d\n",a[i]); }}
菜鸟之伤(19)
l 总结:数组下标越界是最常见的Runtime Error,也是菜鸟常犯的错误,除了需要扎实的C语言基本功,编程中的注意力集中也是需要的(很多时候不是不知道理论,而是不注意)~
l 说明:一般情况,你可以通过将数组开的大点而尽量避免这个问题~
以1425Sort为例
l 题目描述:给你n个整数,请按从大到小的顺序输出其中前m大的数。
l 输入描述:每组测试数据有两行,第一行有两个数n,m(0<n,m<1000000),第二行包含n个各不相同,且都处于区间[-500000,500000]的整数。
菜鸟之伤(20)
#include<stdio.h>void main(){int n,m,i,num[1000000]; //大数组尽量放在main函数外面,全局变量while(scanf(“%d%d”,&n,&m)==2){ ...... }}
#include<stdio.h>void main(){int n,m,i,num[1000000]; //大数组尽量放在main函数外面,全局变量while(scanf(“%d%d”,&n,&m)==2){ ...... }}
菜鸟之伤(20)
l 总结:ACM编程中,使用很大的数组是很常见的做法,但如果超大的数组被定义成局部变量,则很容易出现Runtime Error,解决办法也很简单:定义成全局变量即可。原因是局部变量分配在栈(较小),全局变量分配在堆(较大);
l 说明:这里所说的超大也不能无限制的大,可以根据题目的内存限制进行估算
以3199 Hamming Problem为例
l 题目描述:For each three prime numbers p1, p2 and p3, let's define Hammingsequence Hi(p1, p2, p3), i=1, ... as containing in increasing order all thenatural numbers whose only prime divisors are p1, p2 or p3.
l Forexample, H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27,...
l So H5(2, 3,5)=6.
l 输出描述:The output file must contain the single integer - Hi(p1, p2, p3). Allnumbers in input and output are less than10^18.
菜鸟之伤(21)
l 典型错误——
l 没有仔细分析...
l 也不敢尝试...
l 直接被吓走了......
菜鸟之伤(21)
l 总结:这个题目从本质上来说,和1058Humble Numbers是一样的,唯一吓人的就是数据范围的描述,可能会有人想: i 这么大,没法开数组呀?
l 但是,你仔细分析一下会发现:因为输出也是小于10^18,而同时,即使一组内的三个素数是最小的2,3,5,增长的速度也是很快的,所以不必为数组太大而着急。当然,也不必因为发现i很小而觉得数据太水,那是因为只能如此,不然输出就要超范围了~
这篇关于ACM—NYOJ小小结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!