PAT培训教程课前说明：l自我介绍；l关于本次培训的举办；l特别说明l关于授课内容；l关于课堂纪律：禁食，禁铃；关于PATPATWHATWHAT： PAT PAT-Programming Ability TestProgramming Ability TestWHEREWHERE： Come from ACM/ICPC Come from ACM/ICPCWHYWHY： 客观、实践、实用、效率、快乐HOWHOW：7+17+1、入门培养、重在实践PATVSACMPATVSACM1 1、评测方式的区别 （单Case VS Case VS 多CaseCase）；2 2、评测结果的区别 （分数 VS VS 题数+ +罚时）；3 3、考核内容的区别；4 4、考核规则的区别 （单人闭卷 VS VS 组队开卷）；就业统计信息：n共27人合影（含4位老师），其余：n7位网易；4位百度；n3位微软；1位谷歌；n1位阿里；1位微策略；n1位腾讯；1位南宁烟草局；n4位在网新恒天、同花顺等；第一讲PATPAT入门基础(Introduction to PAT)第一部分预备知识让PATPAT从ACMACM起步 ACMACM题目特点: :由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。下面，分类介绍：先看一个超级简单的题目：nSampleinput:n15n1020nSampleoutput:n6n30初学者很常见的一种写法：n#includenvoid main()nn int a,b;n scanf(“%d %d”,&a,&b);n Printf(“%d”,a+b);n有什么问题呢？这就是下面需要解决的问题基本输入输出汇总输入_第一类：n输入不说明有多少个Input Block,以EOF为结束标志。 参见：HDOJ_1089Hdoj_1089源代码：#includeintmain()inta,b; while(scanf(%d%d,&a,&b)!=EOF)printf(%dn,a+b);本类输入解决方案：nC语法：while(scanf(%d%d,&a,&b)!=EOF).nC+语法：while(cinab).说明（1）：1.Scanf函数返回值就是读出的变量个数，如：scanf(“%d%d”,&a,&b);如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。2.EOF是一个预定义的常量，等于-1。输入_第二类：n输入一开始就会说有N个InputBlock,下面接着是N个InputBlock。参见：HDOJ_1090Hdoj_1090Hdoj_1090源代码：#includeintmain()intn,i,a,b;scanf(%d,&n);for(i=0;in;i+) scanf(%d%d,&a,&b);printf(%dn,a+b);本类输入解决方案：nC语法：scanf(%d,&n);for(i=0;in;for(i=0;in;i+).输入_第三类：n输入不说明有多少个InputBlock,但以某个特殊输入为结束标志。参见：HDOJ_1091Hdoj_1091Hdoj_1091源代码：#includeintmain()inta,b;while(scanf(%d%d,&a,&b)&(a!=0&b!=0)printf(%dn,a+b);上面的程序有什么问题？本类输入解决方案：nC语法：while(scanf(%d,&n)&n!=0).nC+语法：while(cinn&n!=0).输入_第四类：n以上几种情况的组合 输入_第五类：n输入是一整行的字符串的参见：HDOJ_1048 本类输入解决方案：nC语法：charbuf20;gets(buf);nC+语法：如果用stringbuf;来保存：getline(cin,buf);如果用charbuf255;来保存：cin.getline(buf,255);说明（5_1）：nscanf(“%s%s”,str1,str2)，在多个字符串之间用一个或多个空格分隔；n若使用gets函数，应为gets(str1);gets(str2);字符串之间用回车符作分隔。n通常情况下，接受短字符用scanf函数，接受长字符用gets函数。n而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。说明(5_2)(5_2)：cin.getlinecin.getline的用法：ngetline是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下：istream&getline(charline,intsize,charendchar=n);n不用管它的返回类型，来关心它的三个参数：ncharline：就是一个字符数组，用户输入的内容将存入在该数组内。nintsize:最多接受几个字符？用户超过size的输入都将不被接受。ncharendchar:当用户输入endchar指定的字符时，自动结束。默认是回车符。说明(5_2)(5_2)续n结合后两个参数，getline可以方便地实现：用户最多输入指定个数的字符，如果超过，则仅指定个数的前面字符有效，如果没有超过，则用户可以通过回车来结束输入。ncharname4;ncin.getline(name,4,n);n由于endchar默认已经是n，所以后面那行也可以写成：ncin.getline(name,4);思考：n以下题目属于哪一类输入？输出_第一类：n一个InputBlock对应一个OutputBlock，OutputBlock之间没有空行。参见：HDOJ_1089解决方案：nC语法：.printf(%dn,ans);nC+语法：.coutansendl;输出_第二类：n一个InputBlock对应一个OutputBlock，每个OutputBlock之后都有空行。参见：HDOJ_109510951095源代码#includeintmain()inta,b; while(scanf(%d%d,&a,&b)!=EOF) printf(%dnn,a+b);解决办法：nC语法：.printf(%dnn,ans);nC+语法：.coutansendlendl;输出_第三类：n一个InputBlock对应一个OutputBlock，OutputBlock之间有空行。参见：HDOJ_10961096源代码n#includenintmain()nninticase,n,i,j,a,sum;nscanf(%d,&icase);nfor(i=0;iicase;i+)nnsum=0;nscanf(%d,&n);nfor(j=0;jn;j+)nnscanf(%d,&a);nsum+=a;nnif(iicase-1)nprintf(%dnn,sum);nelsenprintf(%dn,sum);nn解决办法：nC语法：for(k=0;kcount;k+)while()printf(%dn,result);if(k!=count-1)printf(n);nC+语法：类似，输出语句换一下即可。思考：n以下题目属于哪一类输出？第二部分正式单元“依然”从简单题说起：nSUM(n) = 1 + 2 + 3 + . + nnYou may assume the result will be in the range of 32-bit signed integer.nSample input:n10nSample output:n55很常见的一种写法：n#includenint main()n int n, i, sum=0; n scanf(%d,&n);n for(i=1;i GCDGCD求解过程1014x10 10 4x104x24xx=2欧几里德算法nint gcd(int da,int xiao) n int temp; n while (xiao!=0) n n temp=da%xiao; n da=xiao; n xiao=temp; n n return(da);n 思考：递归的形式如何写？HDOJ_1061 nGivenapositiveintegerN,youshouldoutputthemostrightdigitofNN (1=N=1,000,000,000).n3n4n7n6HDOJ_1061 n数据规模 很大n暴力方法 该打n基本思路 规律HDOJ_2035人见人爱AB n求ABAB的最后三位数表示的整数（1=A,B=100001=A,B=10000）n2 3 2 3 n12 6 12 6 n8 8 n984984 HDOJ_2035人见人爱AB n最暴力的暴力？n改进的暴力？n如果：n( (1=A,B=100001=A,B=100000000)0000)怎么办？n二分加速？1021FibonacciAgain 题目分析：n能被3 3整除的整数的特点？还要看程序吗？n如果两个数的和能被3 3整除，这两个数有什么特点？n关于“和”能否被3 3整除，这两个数一共有多少种组合？n会不会出现某连续两项和后面连续两项相等的情况？如果出现，能得到什么信息？Hdoj_1021程序清单：n#includenintmain()nnlongn;nscanf(%ld,&n);nif(n%8=2|n%8=6)nprintf(yesn);nelsenprintf(non);nreturn0;nHDOJ_1005HDOJ_1005:NumberSequenceQuestion:暴力（Brute-ForceBrute-Force）能解决问题吗？题目分析：对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。现在对这题有什么想法?附：非典型数学题nHDOJ_1205 HDOJ_1205 吃糖果nGardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另一种；可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完？请你写个程序帮忙计算一下n对于每组数据，输出一行，包含一个Yes或者No。请自己仔细分析.n哪位同学做个陈述？学习方式n练习-练习-总结-ngoogle、baidu常见问题：1、需要什么基础？( C/C+ )5、其它问题？2、英语不好怎么办？(问题不大)3、多久能练成高手？4、从未练过acm，这次需要注意什么?6、特别说明：ACM/PAT训练的价值 实践能力、自学能力、学习的乐趣课后练习：杭电ACM-WebDIY:浙大软件学院PAT实训（1-1）作业密码：zjupat2012