(PAT201201)PAT入门基础.ppt

PAT培训教程,杭州电子科技大学 刘春英 ,2019/9/6,2,自我介绍； 关于本次培训的举办； 特别说明 关于授课内容； 关于课堂纪律：禁食，禁铃；,课前说明：,2019/9/6,3,WHAT： PAT-Programming Ability Test WHERE： Come from ACM/ICPC WHY： 客观、实践、实用、效率、快乐 HOW： 7+1、入门培养、重在实践,关于PAT,2019/9/6,4,1、评测方式的区别 （单Case VS 多Case）； 2、评测结果的区别 （分数 VS 题数+罚时）； 3、考核内容的区别； 4、考核规则的区别 （单人闭卷 VS 组队开卷）；,PAT VS ACM,2019/9/6,5,2019/9/6,6,就业统计信息：,共27人合影（含4位老师），其余： 7位网易；4位百度； 3位微软；1位谷歌； 1位阿里；1位微策略； 1位腾讯；1位南宁烟草局； 4位在网新恒天、同花顺等；,2019/9/6,7,第一讲,PAT入门基础 (Introduction to PAT),2019/9/6,8,第一部分,预备知识,2019/9/6,9,让PAT从ACM起步,ACM题目特点: 由于ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。 下面，分类介绍：,2019/9/6,10,先看一个超级简单的题目：,/showproblem.php?pid=1089 Sample input: 1 5 10 20 Sample output: 6 30,2019/9/6,11,初学者很常见的一种写法：,#include void main() int a,b; scanf(“%d %d”, ,2019/9/6,12,有什么问题呢？,这就是下面需要解决的问题,2019/9/6,13,基本输入输出汇总,2019/9/6,14,输入_第一类：,输入不说明有多少个Input Block,以EOF为结束标志。 参见：HDOJ_1089 /showproblem.php?pid=1089,2019/9/6,15,Hdoj_1089源代码：,#include int main() int a,b; while(scanf(“%d %d“, ,2019/9/6,16,本类输入解决方案：,C语法： while(scanf(“%d %d“,&a, &b) != EOF) C+语法： while( cin a b ) ,2019/9/6,17,说明（1）：,Scanf函数返回值就是读出的变量个数，如：scanf( “%d %d”, 如果只有一个整数输入，返回值是1，如果有两个整数输入，返回值是2，如果一个都没有，则返回值是-1。 EOF是一个预定义的常量，等于-1。,2019/9/6,18,输入_第二类：,输入一开始就会说有N个Input Block,下面接着是N个Input Block。 参见：HDOJ_1090 /showproblem.php?pid=1090,2019/9/6,19,Hdoj_1090源代码：,#include int main() int n,i,a,b; scanf(“%d“, ,2019/9/6,20,本类输入解决方案：,C语法： scanf(“%d“, i+ ) ,2019/9/6,21,输入_第三类：,输入不说明有多少个Input Block,但以某个特殊输入为结束标志。 参见：HDOJ_1091 /showproblem.php?pid=1091,2019/9/6,22,Hdoj_1091源代码：,#include int main() int a,b; while(scanf(“%d %d“, ,上面的程序有什么问题？,2019/9/6,23,本类输入解决方案：,C语法： while(scanf(“%d“,&n) & n!=0 ) C+语法： while( cin n & n != 0 ) ,2019/9/6,24,输入_第四类：,以上几种情况的组合 /showproblem.php?pid=1092 /showproblem.php?pid=1093 /showproblem.php?pid=1094,2019/9/6,25,输入_第五类：,输入是一整行的字符串的 参见：HDOJ_1048 /showproblem.php?pid=1048,2019/9/6,26,本类输入解决方案：,C语法： char buf20; gets(buf); C+语法： 如果用string buf;来保存： getline( cin , buf ); 如果用char buf 255 ; 来保存： cin.getline( buf, 255 );,2019/9/6,27,说明（5_1）：,scanf(“ %s%s”,str1,str2)，在多个字符串之间用一个或多个空格分隔； 若使用gets函数，应为gets(str1); gets(str2); 字符串之间用回车符作分隔。 通常情况下，接受短字符用scanf函数，接受长字符用gets函数。 而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。,2019/9/6,28,说明(5_2)：cin.getline的用法：,getline 是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下： istream 不用管它的返回类型，来关心它的三个参数： char line： 就是一个字符数组，用户输入的内容将存入在该数组内。 int size : 最多接受几个字符？用户超过size的输入都将不被接受。 char endchar :当用户输入endchar指定的字符时，自动结束。默认是回车符。,2019/9/6,29,说明(5_2)续,结合后两个参数，getline可以方便地实现： 用户最多输入指定个数的字符，如果超过，则仅指定个数的前面字符有效，如果没有超过，则用户可以通过回车来结束输入。 char name4; cin.getline(name,4,n); 由于 endchar 默认已经是 n，所以后面那行也可以写成： cin.getline(name,4);,2019/9/6,30,思考：,以下题目属于哪一类输入？ /showproblem.php?pid=1018 /showproblem.php?pid=1013,2019/9/6,31,输出_第一类：,一个Input Block对应一个Output Block，Output Block之间没有空行。 参见：HDOJ_1089 /showproblem.php?pid=1089,2019/9/6,32,解决方案：,C语法： printf(“%dn“,ans); C+语法： . cout ans endl; ,2019/9/6,33,输出_第二类：,一个Input Block对应一个Output Block，每个Output Block之后都有空行。 参见：HDOJ_1095 /showproblem.php?pid=1095,2019/9/6,34,1095源代码,#include int main() int a,b; while(scanf(“%d %d“, ,2019/9/6,35,解决办法：,C语法： printf(“%dnn“,ans); C+语法： . cout ans endl endl; ,2019/9/6,36,输出_第三类：,一个Input Block对应一个Output Block，Output Block之间有空行。 参见：HDOJ_1096 /showproblem.php?pid=1096,2019/9/6,37,1096源代码,#include int main() int icase,n,i,j,a,sum; scanf(“%d“, ,2019/9/6,38,解决办法：,C语法： for (k=0;kcount;k+) while () printf(“ %dn“,result); if (k!=count-1) printf(“n“); C+语法： 类似，输出语句换一下即可。,2019/9/6,39,思考：,以下题目属于哪一类输出？ /showproblem.php?pid=1016 /showproblem.php?pid=1017,2019/9/6,40,第二部分,正式单元,2019/9/6,41,“依然”从简单题说起：,SUM(n) = 1 + 2 + 3 + . + n You may assume the result will be in the range of 32-bit signed integer. Sample input: 10 Sample output: 55 /showproblem.php?pid=1001,2019/9/6,42,很常见的一种写法：,#include int main() int n, i, sum=0; scanf(“%d“, ,2019/9/6,43,其它方法？,SUM(n) = 1 + 2 + 3 + . + n = n * (n+1) / 2 什么风险？ 如何处理？,2019/9/6,44,PAT评测原理,2019/9/6,45,有什么问题呢？,享受今天的慢车旅程吧,2019/9/6,46,HDOJ_1008: Elevator,2019/9/6,47,这是2004浙江省赛最简单的一题，当时训练水平相对较高的学校基本上10分钟之内解决该题，这是一个没有算法的简单模拟题目。 入门训练的好选择,题目评述：,2019/9/6,48,A+B for Polynomials,Sample Input 2 1 2.4 0 3.2 2 2 1.5 1 0.5 Sample Output 3 2 1.5 1 2.9 0 3.2 本题数据结构？（针对不同数据特点） 本题注意事项？,2019/9/6,49,HDOJ_1108 最小公倍数,给定两个正整数，计算这两个数的最小公倍数。 Input： 10 14 Output： 70 思考：如何求最小公倍数(LCM)？ LCM = GCD,2019/9/6,50,GCD求解过程,x=2,2019/9/6,51,欧几里德算法,int gcd(int da,int xiao) int temp; while (xiao!=0) temp=da%xiao; da=xiao; xiao=temp; return(da); ,思考： 递归的形式如何写？,2019/9/6,52,HDOJ_1061 Rightmost Digit,Given a positive integer N, you should output the most right digit of NN (1=N=1,000,000,000). 3 4 7 6,2019/9/6,53,HDOJ_1061 Rightmost Digit,数据规模 很大 暴力方法 该打 基本思路 规律,2019/9/6,54,HDOJ_2035 人见人爱AB,求AB的最后三位数表示的整数（1=A,B=10000） 2 3 12 6 8 984,2019/9/6,55,HDOJ_2035 人见人爱AB,最暴力的暴力？ 改进的暴力？ 如果： (1=A,B=100000000)怎么办？ 二分加速？,2019/9/6,56,1021 Fibonacci Again,2019/9/6,57,题目分析：,能被3整除的整数的特点？,还要看程序吗？,如果两个数的和能被3整除，这两个数有什么特点？,关于“和”能否被3整除，这两个数一共有多少种组合？,会不会出现某连续两项和后面连续两项相等的情况？如果出现，能得到什么信息？,2019/9/6,58,Hdoj_1021程序清单：,#include int main() long n; scanf(“%ld“, ,2019/9/6,59,HDOJ_1005: Number Sequence,2019/9/6,60,Question:,暴力（Brute-Force）能解决问题吗？,2019/9/6,