PAT乙级

suichentree 8/12/2018 算法/数据结构

# PAT 乙级（Basic Level）

链接：PAT官网 (opens new window)

考生应具备以下基本能力：

基本的C/C++的代码设计能力，以及相关开发环境的基本调试技巧；
理解并掌握最基本的数据存储结构，即：数组、链表；
理解并熟练编程实现与基本数据结构相关的基础算法，包括递归、排序、查找等；
能够分析算法的时间复杂度、空间复杂度和算法稳定性；
具备问题抽象和建模的初步能力，并能够用所学方法解决实际问题。

# PAT乙级真题及训练集

链接：PAT乙级真题及训练集 (opens new window)

# 1001. 害死人不偿命的(3n+1)猜想 (15分)

卡拉兹(Callatz)猜想：

对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证(3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？

输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。

输出格式：输出从n计算到1需要的步数。

输入样例： 3 输出样例： 5

==C==

#include<stdio.h>
int main(){
	
	int n;
	int i=0;
	
	scanf("%d",&n);          //输入n 
	 
        while(n!=1){        //当n==1，跳出循环 
            
            if(n%2==0){     //判断n是不是偶数 
                n=n/2; 
                i=i+1;      //计算多少步 
            }else{
                n=(3*n+1)/2;
                i=i+1;
            }
        }
		
	printf("%d\n",i);
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 1002. 写出这个数 (20分)：

读入一个自然数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。

输入格式：每个测试输入包含1个测试用例，即给出自然数n的值。这里保证n小于10100。

输出格式：在一行内输出n的各位数字之和的每一位，拼音数字间有1 空格，但一行中最后一个拼音数字后没有空格。

输入样例： 1234567890987654321123456789 输出样例： yi san wu

==C++==

#include<iostream>
#include<string>
using namespace std;
int main(){
    string n;
	int sum=0;     //n的各个位数之和
	
	string str[10]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
	  
	cin>>n;			//读入自然数n 


	//由于 n 不是传统的数字，是一串数字组成的字符串，下面是对字符串的数字进行求和
	for(int i=0;i<n.size();i++){
		sum = sum+n[i]-'0' ;		//sum是n的各个数之和 
	}

	//取出sum的各个位数
	int bai=sum/100; 
	int shi=(sum/10)%10;
	int ge=sum%10;

	if(bai!=0){
		cout<<str[bai]<<" ";
		cout<<str[shi]<<" ";
		cout<<str[ge];          //题目要求个位数后面无空格

	}else if(shi!=0){
		cout<<str[shi]<<" ";
		cout<<str[ge];

	}else if(ge!=0 || ge==0){
		cout<<str[ge];
	}

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 1003. 我要通过！(20)

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于PAT的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：

字符串中必须仅有P, A, T这三种字符，不可以包含其它字符；
任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a, b, c 均或者是空字符串，或者是仅由字母 A 组成的字符串。

现在就请你为PAT写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：每个测试输入包含1个测试用例。第1行给出一个自然数n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过100，且不包含空格。

输出格式：每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出YES，否则输出NO。

输入样例： 8 PAT PAAT AAPATAA AAPAATAAAA xPATx PT Whatever APAAATAA

输出样例： YES YES YES YES NO NO NO NO

# 1004. 成绩排名 (20)

读入n名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。

输入格式：每个测试输入包含1个测试用例，格式为

第1行：正整数n 第2行：第1个学生的姓名学号成绩第3行：第2个学生的姓名学号成绩 ... ... ... 第n+1行：第n个学生的姓名学号成绩

其中姓名和学号均为不超过10个字符的字符串，成绩为0到100之间的一个整数，这里保证在一组测试用例中没有两个学生的成绩是相同的。输出格式：对每个测试用例输出2行，第1行是成绩最高学生的姓名和学号，第2行是成绩最低学生的姓名和学号，字符串间有1空格。

输入样例： 3 Joe Math990112 89 Mike CS991301 100 Mary EE990830 95

输出样例： Mike CS991301 Joe Math990112

==C++==

#include<iostream>
#include<string>
using namespace std;

//构造学生结构体
struct stu     
{
   string name;
   string sid;
   int score;
   
};

int main(){
	int n;
	int max_score,min_score;      //最高分与最低分

	cin>>n;
	struct stu s[100];

	//输入信息给 结构体数组
	for(int i=0;i<n;i++){
		cin>>s[i].name>>s[i].sid>>s[i].score;
	}

	//找出结构体数组中的最高分
	max_score=s[0].score; 
	for(int j=0;j<n-1;j++){
		if(max_score<s[j+1].score){
			max_score=s[j+1].score;
		}
	}

	//找出结构体数组中的最低分
	min_score=s[0].score;
	for(int j=0;j<n-1;j++){
		if(min_score>s[j+1].score){
			min_score=s[j+1].score;
		}
	}

	
	int max=0;    //分数最大的是结构体数组中的第几个，max为下标
	int min=0;

	//通过最高分与最低分的对比，来找出最高分与最低分的学生是谁？
	for(int k=0;k<n;k++){
		if(s[k].score==max_score){
			max=k;       //最高分学生在数组的位置
		}
		if(s[k].score==min_score){
			min=k;
		}
		
	}

	cout<<s[max].name<<' '<<s[max].sid<<endl;   //输出最高分学生的下标
	cout<<s[min].name<<' '<<s[min].sid<<endl;
	

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

# 1005. 继续(3n+1)猜想 (25):

卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。

当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对n=3进行验证的时候，我们需要计算3、5、8、4、2、1，则当我们对n=5、8、4、2进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这4个数已经在验证3的时候遇到过了，我们称5、8、4、2是被3“覆盖”的数。我们称一个数列中的某个数n为“关键数”，如果n不能被数列中的其他数字所覆盖。

现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。==你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。==

输入格式：每个测试输入包含1个测试用例，第1行给出一个正整数K(<100)，第2行给出K个互不相同的待验证的正整数n(1<n<=100)的值，数字间用空格隔开。

输出格式：每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用1个空格隔开，但一行中最后一个数字后没有空格。

输入样例： 6 3 5 6 7 8 11

输出样例： 7 6

==C++==

# 1006. 换个格式输出整数 (15)

让我们用字母B来表示“百”、字母S表示“十”，用“12...n”来表示个位数字n（<10），换个格式来输出任一个不超过3位的正整数。例如234应该被输出为BBSSS1234，因为它有2个“百”、3个“十”、以及个位的4。

输入格式：每个测试输入包含1个测试用例，给出正整数n（<1000）。

输出格式：每个测试用例的输出占一行，用规定的格式输出n。

输入样例1： 234

输出样例1： BBSSS1234

输入样例2： 23

输出样例2： SS123

==C++==

#include<iostream>
#include<string>
using namespace std;

int main(){
	int n;
	cin>>n;      //输入n

	 // n 的个十百上的数字
	int ge=0;
	int shi=0;
	int bai=0;

	
	if(n>=100){

		ge=n%10;			 //若n>100,则个十百上的数字是
		shi=(n/10)%10;
		bai=(n/100)%10;

		for(int i=0;i<bai;i++){    //百位数是几，就输出几个B
			cout<<'B'; 
		}
		for(int i=0;i<shi;i++){
			cout<<'S';
		}
		for(int i=1;i<ge+1;i++){   //由于个位数，若为 4，则输出1234，所有 i=1,且 i<ge+1
			cout<<i;
		}

	}else if(n>=10&&n<100){

		ge=n%10;
		shi=(n/10)%10;
		
		for(int i=0;i<shi;i++){
			cout<<'S';
		}
		for(int i=1;i<ge+1;i++){
			cout<<i;
		}

	}else if(n>0&&n<10){
		
		ge=n%10;

		for(int i=1;i<ge+1;i++){
			cout<<i;
		}
	}

	return 0;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# 1007. 素数对猜想 (20):

让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N (< 105)，请计算不超过N的满足猜想的素数对的个数。

输入格式：每个测试输入包含1个测试用例，给出正整数N。

输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例： 20

输出样例： 4

==C++==

# 1008. 数组元素循环右移问题 (20):

一个数组A中存有N（N>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A0 A1……AN-1）变换为（AN-M …… AN-1 A0 A1……AN-M-1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式：每个输入包含一个测试用例，第1行输入N ( 1<=N<=100)、M（M>=0）；第2行输入N个整数，之间用空格分隔。

输出格式：在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例： 6 2 1 2 3 4 5 6

输出样例： 5 6 1 2 3 4

==C++==

#include<iostream>
#include<string>
using namespace std;

int main(){
	/*
	例子：
		1. n=5 , m=2
	       输出： 4 5 1 2 3

		2. n=5 , m=7
		   输出： 4 5 1 2 3

	    3. n=5 , m=12
    	   输出： 4 5 1 2 3
	
	思路：
		1.不需要直接对数组的数字进行交换后，再输出数组
		
		2.可以转换思想，在本例1中可以直接输出后两位，在输出前三位即可。
		
		3.在例2,3中，由于m>n,且 m%n==2,这个余数就相当于例1的m。此时的2，就是新的m，不是本例的旧的m，12
	
	总结：
		当 n>m 时，m的值就是m。
		当 m>n 时, m%n的值就是m。
	*/


	int n,m;
	int a[100];
	int k;       //k就是当m>n时，k==m%n 

	cin>>n>>m;

	for(int i=0;i<n;i++){
		cin>>a[i];
	}

	//当n>=m时，
	if(n>=m){
		for(int i=n-m;i<n;i++){       //这个for循环，输出数组中后面m个数字。后面有空格
			cout<<a[i]<<" ";
		}
		for(int i=0;i<n-m-1;i++){    // 这个for循环，输出数组其余数据，除了最后一个数字。后面有空格
			cout<<a[i]<<" ";
		}
		cout<<a[n-m-1];              //输出最后一个数字，后面没有空格
		
	 //当 m>n 时
	}else if(m>n){
		k=m%n;
		
		for(int i=n-k;i<n;i++){
			cout<<a[i]<<" ";
		}
		for(int i=0;i<n-k-1;i++){
			cout<<a[i]<<" ";
		}

		cout<<a[n-k-1];
	}

	return 0;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

# 1009. 说反话 (20)

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。

输入格式：测试输入包含一个测试用例，在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用1个空格分开，输入保证句子末尾没有多余的空格。

输出格式：每个测试用例的输出占一行，输出倒序后的句子。

输入样例： Hello World Here I Come

输出样例： Come I Here World Hello

==C++==

这个是借鉴别人的思路，思路清奇。但这个有运行超时的可能，

#include <iostream>
#include <string>
using namespace std;
int main()
{
string in, out;
cin>>out;                  //输入第一个字符

do{
cin>>in;					//再输入其余字符
out = in + " " + out;			  //把其余字符与第一个字符用空格连接。其中第一个字符在最后。相当于倒序连接

}while(cin.get()!='\n');                //当输入回车符时，终止while循环


cout<<out<<endl;           //输出字符

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

==C++==

#include <iostream>
#include <string>
#include<stack>    //引入栈的数据结构
using namespace std;
int main()
{
	string str;       //字符串变量
	
	int a;           //记录栈内元素个数
 
	stack<string> stk;

	do{
		cin>>str;                //使用cin从键盘输入字符串时，读取到空格就断开
		stk.push(str);
	}while(cin.get()!='\n');     //读入回车符，停止while循环


	a=stk.size();               //栈内元素个数

	for(int i=0;i<a-1;i++){     //除了栈底元素，其余元素全部输出，后面有空格
		     
		cout<<stk.top()<<" ";
		stk.pop();             //移除栈顶元素，让下一个元素变成栈顶
	}

	cout<<stk.top();           //输出最后一个栈底元素，后面没有空格

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 1010. 一元多项式求导 (25)：

设计函数求一元多项式的导数。（注：xn（n为整数）的一阶导数为n*xn-1。）

输入格式：以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式：以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。注意“零多项式”的指数和系数都是0，但是表示为“0 0”。

输入样例： 3 4 -5 2 6 1 -2 0

输出样例： 12 3 -10 1 6 0

C++

#include <iostream>
using namespace std;
int main()
{
	int a,b;
    bool t=true;           //t用于判断是否是 第一个a与b

	/*
	思路：
	  1. 一般情况下，输入a b,则输出a*b b-1, 注意a*b前面没有空格，a*b与b-1之间有空格。

	  2. 当输入第一个a，b时，若b==0,则输出0 0，若b==1,由于b-1==0，因此输出a*b,后面的b-1==0就不输出了。
	
	  3. 当输出由第一个a，b得出的两个数，t从true --> false。防止程序在进入if循环中。
	  
	  ----

	  4. 若不是第一个a,b. 若b==0,则输出 0（单个0），若b==1,由于b-1==0，因此输出 a*b,后面的b-1==0就不输出了。

	  5. 注意从第二个a,b开始，输出的第一个数前面有空格，第二个数无空格。
	  

	  ps: 测试例子都是： 第一个b为0，或者最后一个b为0的情况。


	*/


	while(cin>>a>>b){
        if(t){
            if(b==0){
              cout<<0<<" "<<0;
            }else if(b==1){
              cout<<a*b;
            }else{
              cout<<a*b<<" "<<b-1;
            }
            
            t=false;
            
        }else{
            if(b==0){
              cout<<" "<<a*b;
            }else if(b==1){
              cout<<" "<<a*b;
            }else{
              cout<<" "<<a*b<<" "<<b-1;
           }
            
        }
		
	}

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

# 1011: A+B和C (15)

给定区间[-2的31次方, 2的31次方]内的3个整数A、B和C，请判断A+B是否大于C。

输入描述: 输入第1行给出正整数T(<=10)，是测试用例的个数。随后给出T组测试用例，每组占一行，顺序给出A、B和C。整数间以空格分隔。

输出描述: 对每组测试用例，在一行中输出“Case #X: true”如果A+B>C，否则输出“Case #X: false”，其中X是测试用例的编号（从1开始）。

输入例子: 4

1 2 3

2 3 4

2147483647 0 2147483646

0 -2147483648 -2147483647

输出例子: Case #1: false

Case #2: true

Case #3: true

Case #4: false

==C++==

#include <iostream>
using namespace std;
int main()
{
	int a,b,c,t;              //t输出示例的个数
	int s[100];               //用于存放每个示例的结果，若a+b>c,则对应的数组位置存放1，否则为0； 
	cin>>t;

	for(int i=0;i<t;i++){         //循环输入示例
		
		cin>>a>>b>>c;

		if(a<0&&a==b&&b==c){       
			//特殊情况下，若 a,b,c 为 -1 -1 -1，则a+b<c,则在数组的对应位置赋值为0。
			
			s[i]=0;
		}else if(a==2147483647&&a==b&&b==c){  
			//特殊情况下，若a,b,c 为 2147483647 2147483647 2147483647 ，则a+b<c,因为int的数据溢出。
			
			s[i]=1;
		}else{
			if(a+b>c){    //一般情况
				s[i]=1;
			}else{
				s[i]=0;
			}
		}

	}

	for(int i=0;i<t;i++){    //循环数组，若对应数组值为0，1则输出不同的内容。

		if(s[i]==1){
			cout<<"Case #"<<i+1<<": "<<"true"<<endl;
		}else{
			cout<<"Case #"<<i+1<<": "<<"false"<<endl;
		}
		
	}

  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 1012：数字分类 (20)

给定一系列正整数，请按要求对数字进行分类，并输出以下5个数字：

A1 = 能被5整除的数字中所有偶数的和；

A2 = 将被5除后余1的数字按给出顺序进行交错求和，即计算n1-n2+n3-n4...；

A3 = 被5除后余2的数字的个数；

A4 = 被5除后余3的数字的平均数，精确到小数点后1位；

A5 = 被5除后余4的数字中最大数字。

输入描述: 每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N，随后给出N个不超过1000的待分类的正整数。数字间以空格分隔。

输出描述: 对给定的N个正整数，按题目要求计算A1~A5并在一行中顺序输出。数字间以空格分隔，但行末不得有多余空格。

==若其中某一类数字不存在，则在相应位置输出“N”。==

输入例子:

13 1 2 3 4 5 6 7 8 9 10 20 16 18

输出例子:

30 11 2 9.7 9

C++

#include<iostream>
using namespace std;
int main(){
    
    int n;
    int a[1000];                         //存放输入的数字
    int a1=0,a2=0,a3=0,a5=0;             //a1~a5默认值为0，注意a4为float类型
    float a4=0;
    
    int b2=1;            //b2是计算a2的辅助参数
    float b4=0,j=0;       //b4，j是计算a4的辅助参数,其中j用于计数
    int b5;				//b5是计算a5的辅助参数
    
    cin>>n;
    
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    
    for(int i=0;i<n;i++){
        if(a[i]%5==0&&a[i]%2==0){
            a1+=a[i];
        }else if(a[i]%5==1){
            a2=a2+b2*a[i];
            b2=-1*b2;					//b2在循环中为 1，-1，1，-1，1，~
            
        }else if(a[i]%5==2){
            a3++;
        }else if(a[i]%5==3){
            j++;
            b4=b4+a[i];
        }else if(a[i]%5==4){
            if(a5<a[i]){			//找出最大的
                b5=a5;
                a5=a[i];
                a[i]=b5;
            }
        }
    }
    
	if(j==0){         //由于a4=b4/j,其中若j==0，则a4不存在。
		a4=0;
	}else{
	    a4=b4/j;
	}

		if(a1==0){
			cout<<'N'<<" ";
		}else{
			cout<<a1<<" ";
		}
		if(a2==0){
			cout<<'N'<<" ";
		}else{
			cout<<a2<<" ";
		}
		if(a3==0){
			cout<<'N'<<" ";
		}else{
			cout<<a3<<" ";
		}
		if(a4==0){
			cout<<'N'<<" ";
		}else{
			printf("%.1f",a4);          //保留一位小数
			cout<<" ";
		}
		if(a5==0){
			cout<<'N';
		}else{
			cout<<a5;
		}
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# 1013: 数素数 (20)

令Pi表示第i个素数。现任给两个正整数M <= N <= 10000，请输出PM到PN的所有素数。

输入描述: 输入在一行中给出M和N，其间以空格分隔。

输出描述: 输出从PM到PN的所有素数，每10个数字占1行，其间以空格分隔，但行末不得有多余空格。

输入例子: 5 27

输出例子:

11 13 17 19 23 29 31 37 41 43

47 53 59 61 67 71 73 79 83 89

97 101 103

==C++==

#include<iostream>
#include<math.h>
using namespace std;
int isPrime(int n) {

	/*
		素数又叫质数。

		有两种求法：
			筛选法：从小到大筛去一个已知素数的所有倍数。
				   依次删除可被2整除，3整除。。。。的数字，剩下的则为素数 。

		开根号法：如果一个数（>2），对这个数求平方根，
		         如果这个数能被这个数的平方根到2之间的
				 任何一个（只要有一人就行）整除说明就不是质数，如果不能就说明是质数！
	
	*/

	int b=sqrt(n*1.0);           //b为n的平方根，sqrt函数里的参数为double型

    for (int i = 2; i <= b; ++i) {   //注意这里是 <= b ，否则求素数错误
		if (n % i == 0){
			return 0;  
        }  
	}

    return 1;  
}  
int main(){
    
	int m,n;
	int a[20000];        //这里数组大小要大一些，有些测试的例子太大了，不然不好装
	
	int isPrime(int n);  //函数声明

	int b=2,t=0,k=1;   //b为求素数的范围， t是辅助把求出来的素数放到数组a中，为数组下标
					   // k 用计算每行素数的个数

	cin>>m>>n;

	while(b<=200000){      //这里是求 2~200000 之间的所有素数
	
		if(isPrime(b)){
			a[t]=b;
			t++;           //t对应的数组下标
		}
		
		b++;
	}

	if(m==n){		//若例子为10000 10000 ，则输出第10000个素数，即a[9999].
		cout<<a[m-1];
	}else{
		
		for(int i=m-1;i<n-1;i++){     //输出第m个 ~ 第n-1个素数。
		
			if(k%10==0){
				cout<<a[i]<<endl;    //每输出10个素数，末尾无空格
			}else{
				cout<<a[i]<<" ";     //一般情况下，每输出一个素数，后面有空格
			}
		
			k++;              //每输出一个素数，k++,计算每行素数的个数。
		}

		cout<<a[n-1];         //输出第n个（最后一个）素数，后面无空格
	}


		return 0;
}

# 1014：福尔摩斯的约会 (20)

大侦探福尔摩斯接到一张奇怪的字条： “我们约会吧！ 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm”。

大侦探很快就明白了，字条上奇怪的乱码实际上就是约会的时间“星期四 14:04”，因为前面两字符串中第1对相同的大写英文字母（大小写有区分）是

第4个字母'D'，代表星期四；第2对相同的字符是'E'，那是第5个英文字母，代表一天里的第14个钟头（于是一天的0点到23点由数字0到9、

以及大写字母A到N表示）；后面两字符串第1对相同的英文字母's'出现在第4个位置（从0开始计数）上，代表第4分钟。现给定两对字符串，

请帮助福尔摩斯解码得到约会的时间。

输入描述: 输入在4行中分别给出4个非空、不包含空格、且长度不超过60的字符串。

输出描述: 在一行中输出约会的时间，格式为“DAY HH:MM”，其中“DAY”是某星期的3字符缩写，即MON表示星期一，TUE表示星期二，WED表示星期三，THU表示星期四，FRI表示星期五，SAT表示星期六，SUN表示星期日。题目输入保证每个测试存在唯一解。

输入例子:

3485djDkxh4hhGE

2984akDfkkkkggEdsb

s&hgsfdk

d&Hyscvnm

输出例子:

THU 14:04

==C++==


#include<iostream>
#include<string>
#include <cctype>
using namespace std;
int main(){

	//这题有几个注意点：
	/*
	①： 找出的第一个字符为：两字符串中第1对相同的大写英文字母。
	②： 第二个字符为：可以是字母与数字，但寻找范围是从第一个字符串的tag1+1位置，
					与第二个字符串的tag2+1的位置开始找。
			
		 举例：   
			3485djDkxh4hhGE
			2984akDfkkkkggEdsb
			其中第一个字符为D，则第二个字符应该在：
												kxh4hhGE
												fkkkkggEdsb
			两个字符串从D之后截取的字符串的范围中找。

			其中tag1 是第一个字符串中D的下标，tag2是第二个字符串中D的下标

	③:  第三个字符是第三个与第四个字符串中相同位置的相同字母所在的下标。

	④： 找第三个字符的遍历次数为两个字符串中长度小的次数。
	*/

	string s1,s2,s3,s4;

	char a;      //c为通过s1 s2 找出的第一个大写字母
	char b;		 //e为通过s1 s2 找出的第二个字符，可以为字母或数字

	int tag1=0,tag2=0;    //通过s1 s2 找出的第二个字符，所需要的辅助条件

	int d=0;               //记录s3,s4 第一对相同位置的相同字母，并存放其下标位置
	int t;				  //辅助变量，记录s3,s4字符串中小的字符串的长度

	int s1tag=0;    //若sb为0，则为没找到第一个大写字母，为1 表示找到
	int s2tag=0;

	cin>>s1>>s2>>s3>>s4;

	//遍历s1，s2，找出第一个字符
	for(int i=0;i<s1.size();i++){
		if(isupper(s1[i])){						//若s1中某个字符为大写字母
			for(int j=0;j<s2.size();j++){	    
				if(s1tag==0){
					if(isupper(s2[j])){        //若s2中某个字符为大写字母
						if(s1[i]==s2[j]){
								a=s1[i];                     
								tag2=j;         //记录此时第一个字符在两个字符串的位置
								tag1=i;
								s1tag=1;
						}
					}
				}
		    }
		}
	}

	for(int i=tag1+1;i<s1.size();i++){
		if(s2tag==0){
			if(!(islower(s1[i]))){          
				for(int j=tag2+1;j<s2.size();j++){
					if(!(islower(s2[j]))){
						if(s1[i]==s2[j]){
							b=s1[i];
							s2tag=1;
						}
					}
				}
			}
		}
	}

	//共同遍历s3,s4，找出位置相同的字母,并记下下标位置，遍历次数t为短的字符串的字符个数

	t=s3.size()>s4.size()?s4.size():s3.size();
	for(int i=0;i<t;i++){
		if(isalpha(s3[i])){       //判断s3[i]是否为英文字母
			if(s3[i]==s4[i]){
				d=i;              //若字母相同则记录下标数，只记录第一对的
				break;
			}
		}
	}

	//打印输出语句，通过给出的要求

	if(a=='A'){
		cout<<"MON"<<" ";
	}else if(a=='B'){
		cout<<"TUE"<<" ";
	}else if(a=='C'){
		cout<<"WED"<<" ";
	}else if(a=='D'){
		cout<<"THU"<<" ";
	}else if(a=='E'){
		cout<<"FRI"<<" ";
	}else if(a=='F'){
		cout<<"SAT"<<" ";
	}else if(a=='G'){
		cout<<"SUN"<<" ";
	}

	if(b=='0'){
		cout<<"00"<<":";
	}else if(b=='1'){
		cout<<"01"<<":";
	}else if(b=='2'){
		cout<<"02"<<":";
	}else if(b=='3'){
		cout<<"03"<<":";
	}else if(b=='4'){
		cout<<"04"<<":";
	}else if(b=='5'){
		cout<<"05"<<":";
	}else if(b=='6'){
		cout<<"06"<<":";
	}else if(b=='7'){
		cout<<"07"<<":";
	}else if(b=='8'){
		cout<<"08"<<":";
	}else if(b=='9'){
		cout<<"09"<<":";
	}else if(b=='A'){
		cout<<"10"<<":";
	}else if(b=='B'){
		cout<<"11"<<":";
	}else if(b=='C'){
		cout<<"12"<<":";
	}else if(b=='D'){
		cout<<"13"<<":";
	}else if(b=='E'){
		cout<<"14"<<":";
	}else if(b=='F'){
		cout<<"15"<<":";
	}else if(b=='G'){
		cout<<"16"<<":";
	}else if(b=='H'){
		cout<<"17"<<":";
	}else if(b=='I'){
		cout<<"18"<<":";
	}else if(b=='J'){
		cout<<"19"<<":";
	}else if(b=='K'){
		cout<<"20"<<":";
	}else if(b=='L'){
		cout<<"21"<<":";
	}else if(b=='M'){
		cout<<"22"<<":";
	}else if(b=='N'){
		cout<<"23"<<":";
	}

	if(d<10){
		cout<<"0"<<d;
	}else{
		cout<<d;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

# 1015: 德才论 (25)

题目描述宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之

小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”

现给出一批考生的德才分数，请根据司马光的理论给出录取排名。

输入描述: 输入第1行给出3个正整数，分别为：N（<=105），即考生总数；L（>=60），为录取最低分数线. 即德分和才分均不低于L的考生才有资格被考虑录取；H（<100），为优先录取线——德分和才分均不低于此线的被定义为“才德全尽”，此类考生按德才总分从高到低排序；才分不到但德分到线的一类考生属于“德胜才”，也按总分排序，但排在第一类考生之后；德才分均低于H，但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者，按总分排序，但排在第二类考生之后；其他达到最低线L的考生也按总分排序，但排在第三类考生之后。随后N行，每行给出一位考生的信息，包括：准考证号、德分、才分，其中准考证号为8位整数，德才分为区间[0, 100]内的整数。数字间以空格分隔。

输出描述: 输出第1行首先给出达到最低分数线的考生人数M，随后M行，每行按照输入格式输出一位考生的信息，考生按输入中说明的规则从高到低排序。当某类考生中有多人总分相同时，按其德分降序排列；若德分也并列，则按准考证号的升序输出。

输入例子:

14 60 80

10000001 64 90

10000002 90 60

10000011 85 80

10000003 85 80

10000004 80 85

10000005 82 77

10000006 83 76

10000007 90 78

10000008 75 79

10000009 59 90

10000010 88 45

10000012 80 100

10000013 90 99

10000014 66 60

输出例子:

10000013 90 99

10000012 80 100

10000003 85 80

10000011 85 80

10000004 80 85

10000007 90 78

10000006 83 76

10000005 82 77

10000002 90 60

10000014 66 60

10000008 75 79

10000001 64 90

==C++==

这个demo有问题，题目给出的示例过了，但测试没过，我也不知为什么？

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Student{
	int id;		//id:准考证号（8位数字），dscore:德分，cscore:才分。德才分为区间[0, 100]内的整数。数字间以空格分隔。
	int dscore;
	int cscore;
	int kind;				// sum:德才总分,kind表示这个考生是第几类
	int sum;

};

int cmp(struct Student a, struct Student b) {
    if ((a.sum) != (b.sum))
        return (a.sum) > (b.sum);
    else if (a.dscore != b.dscore)
        return a.dscore > b.dscore;
    else
        return a.id < b.id;
}

int main() {

	int N,L,H;              //N:考生总数 ，L:录取最低分数线, H：为优先录取线

	cin>>N>>L>>H;
	
	int nopass=0;
	struct Student stu;
	vector<Student> Set_stu[4];

	for(int i=0;i<N;i++){
		cin>>stu.id>>stu.dscore>>stu.cscore;

		if(stu.dscore < L || stu.cscore < L){
			nopass++;	

		}else{
			
			if(stu.dscore >= H && stu.cscore >= H){								//才德全尽的人
				
				stu.sum=stu.cscore + stu.dscore;
				stu.kind=1;

				Set_stu[0].push_back(stu);               //把第一类的学生的插入到set集合中


			}else if(stu.dscore >= H && stu.cscore < H){   //德胜才的人
				
				stu.sum=stu.cscore + stu.dscore;
				stu.kind=2;

				Set_stu[1].push_back(stu);               //把第二类的学生的插入到set集合中


			}else if(stu.dscore < H && stu.cscore < H && stu.dscore >= L){  //才德兼亡”但尚有“德胜才”的人 

				stu.sum=stu.cscore + stu.dscore;
				stu.kind=3;
				Set_stu[2].push_back(stu);               //把第三类的学生的插入到set集合中

			}else{
				stu.sum=stu.cscore + stu.dscore;
				stu.kind=4;
				Set_stu[3].push_back(stu);               //把第四类的学生的插入到set集合中

			}
		}

	}



	cout<<N-nopass<<endl<<endl;
	for(int i=0;i<4;i++){

		sort(Set_stu[i].begin(), Set_stu[i].end(), cmp);

		for(int j = 0; j < Set_stu[i].size(); j++){ 
			 printf("%d %d %d\n", Set_stu[i][j].id, Set_stu[i][j].dscore, Set_stu[i][j].cscore);
		}
	
	}


    
	return 0;
}

# 1016: 部分A+B (15)

题目描述正整数A的“DA（为1位整数）部分”定义为由A中所有DA组成的新整数PA。例如：给定A = 3862767，DA = 6，则A的“6部分”PA是66，因为A中有2个6。

现给定A、DA、B、DB，请编写程序计算PA + PB。

输入描述: 输入在一行中依次给出A、DA、B、DB，中间以空格分隔，其中0 < A, B < 1010。

输出描述: 在一行中输出PA + PB的值。

输入例子: 3862767 6 13530293 3

输出例子: 399

==C++==

#include<iostream>
#include<cmath>
using namespace std;
int main() {

	long A,B,C,D;

	int a,ai=0,c,ci=0;           //a，ai是A B的辅助变量
	long pa=0,pb=0;

	cin>>A>>B>>C>>D;

	while(A>0){     
		a=A%10;           //取A的最后一位数。如123 -> 3
		if(a==B){        //当A的最后一个数字与B相同时，ai++
			ai++;
		}
		A=A/10;         //A去掉最后一位数，如123 -> 12
	}

	while(C>0){
		c=C%10;
		if(c==D){
			ci++;
		}
		C=C/10;
	}

	//懒得写for循环，直接写这种计算公式
	if(ai==1){
		pa=B;
	}else if(ai==2){
		pa=B*10+B;
	}else if(ai==3){
		pa=B*100+B*10+B;
	}else if(ai==4){
		pa=B*1000+B*100+B*10+B;
	}else if(ai==5){
		pa=B*10000+B*1000+B*100+B*10+B;
	}else if(ai==6){
		pa=B*100000+B*10000+B*1000+B*100+B*10+B;
	}else if(ai==7){
		pa=B*1000000+B*100000+B*10000+B*1000+B*100+B*10+B;
	}else if(ai==8){
		pa=B*10000000+B*1000000+B*100000+B*10000+B*1000+B*100+B*10+B;
	}else if(ai==9){
		pa=B*100000000+B*10000000+B*1000000+B*100000+B*10000+B*1000+B*100+B*10+B;
	}


	if(ci==1){
		pb=D;
	}else if(ci==2){
		pb=D*10+D;
	}else if(ci==3){
		pb=D*100+D*10+D;
	}else if(ci==4){
		pb=D*1000+D*100+D*10+D;
	}else if(ci==5){
		pb=D*10000+D*1000+D*100+D*10+D;
	}else if(ci==6){
		pb=D*100000+D*10000+D*1000+D*100+D*10+D;
	}else if(ci==7){
		pb=D*1000000+D*100000+D*10000+D*1000+D*100+D*10+D;
	}else if(ci==8){
		pb=D*10000000+D*1000000+D*100000+D*10000+D*1000+D*100+D*10+D;
	}else if(ci==9){
		pb=D*100000000+D*10000000+D*1000000+D*100000+D*10000+D*1000+D*100+D*10+D;
	}

	
	cout<<pa+pb;


	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

# 1017：A除以B (20)：

本题要求计算A/B，其中A是不超过1000位的正整数，B是1位正整数。你需要输出商数Q和余数R，使得A = B * Q + R成立。

输入描述: 输入在1行中依次给出A和B，中间以1空格分隔。

输出描述: 在1行中依次输出Q和R，中间以1空格分隔。

输入例子: 123456789050987654321 7

输出例子: 17636684150141093474 3

==C++==


#include<iostream>
#include<string>
using namespace std;
int main(){

	/*
	算法思想：

	比如 100/2 等价于 1/2 商为0,余数为1,商为0的情况下不能输输出, 
	然后余数和下一位 即0 组合为1*10+0=10,就变成10/2 商为5余数为0,此时输出商数。
	然后0和下一位0组合为0*10+0=0 0/2余数为0,此时运算完毕。
	
	*/


	string a,q;    //a,b 为除数与被除数，q,r为商数，余数。
	int b=0,r=0;
	int c=0;       //c为临时变量

	cin>>a>>b;

	for(int i = 0; i < a.length(); i++){           //a的每一位数字与b相除
				
		c = r * 10 + (a[i] - '0');                 //由于从一开始，所以商的第一位数有一个0，要去除0
				
		q= c / b +'0';
				
		r = c % b;
				
		if(i == 0 && q[0] =='0'){                 //这里是去除0
			continue;
		}else{
			cout << q;							//打印此时的商数，最终的商数有许多给不同的时候的商数拼成的
		}
			
	}
		cout <<' ';                         
		cout << r;                              //商数打印完，输出余数
			

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# 1018：锤子剪刀布 (20)

题目描述大家应该都会玩“锤子剪刀布”的游戏：

现给出两人的交锋记录，请统计双方的胜、平、负次数，并且给出双方分别出什么手势的胜算最大。

输入描述: 输入第1行给出正整数N（<=105），即双方交锋的次数。随后N行，每行给出一次交锋的信息，即甲、乙双方同时给出的的手势。C代表“锤子”、J代表“剪刀”、B代表“布”，第1个字母代表甲方，第2个代表乙方，中间有1个空格。

输出描述: 输出第1、2行分别给出甲、乙的胜、平、负次数，数字间以1个空格分隔。第3行给出两个字母，分别代表甲、乙获胜次数最多的手势，中间有1个空格。如果解不唯一，则输出按字母序最小的解。

输入例子: 10

C J

J B

C B

B B

B C

C C

C B

J B

B C

J J

输出例子: 5 3 2

2 3 5

B B

==C++==


#include<iostream>
#include<string>
using namespace std;
int main(){
    
    char a,b;          //a,b,表示甲乙双方给出的手势
    int n;             //n 表示进行多少轮比试
    
    int j[3]={0,0,0},y[3]={0,0,0};      //j[3]表示甲的三种手势的胜利次数，j[0]:剪刀，j[1]:石头，j[2]:布
	int c[3]={0,0,0},d[3]={0,0,0};      //c[3]表示甲的正负平的次数，c[0]:胜，c[1]:平，c[2]:负
    
	char jmax;                        //jamx 表示甲win的最多的手势
	char ymax;					      //yamx 表示乙win的最多的手势

    cin>>n;
    
    for(int i=0;i<n;i++){
        cin>>a>>b;                          //每比一局，就记录一次
        
        if(a=='J'){         //若甲出剪刀                                  
            if(b=='J'){     //平局
                c[1]++;
                d[1]++;
            }else if(b=='C'){    //甲输了
                d[0]++;                  //乙win
                y[1]++;                  //乙靠石头win
                c[2]++;                  //甲输了
                
            }else if(b=='B'){     //甲win
                d[2]++;
                c[0]++;
                j[0]++;
            }
        }else if(a=='C'){
            if(b=='J'){
                d[2]++;
                c[0]++;
                j[1]++;
            }else if(b=='C'){
                c[1]++;
                d[1]++;
            }else if(b=='B'){
                d[0]++;
                y[2]++;
                c[2]++;
            }
        }else if(a=='B'){
            if(b=='J'){
                d[0]++;
                y[0]++;
                c[2]++; 
            }else if(b=='C'){
                d[2]++;
                c[0]++;
                j[2]++;
            }else if(b=='B'){
                c[1]++;
                d[1]++;
            }
        }
    }

	//找出甲乙胜利最大的手势
	if(j[0]>j[1]){
		if(j[0]>j[2]){
			jmax='J';
		}else{
			jmax='B';
		}
	}else{
		if(j[1]>j[2]){
			jmax='C';
		}else{
			jmax='B';
		}
	}

	if(y[0]>y[1]){
		if(y[0]>y[2]){
			ymax='J';
		}else{
			ymax='B';
		}
	}else{
		if(y[1]>y[2]){
			ymax='S';
		}else{
			ymax='B';
		}
	}

    cout<<c[0]<<" "<<c[1]<<" "<<c[2]<<endl;
    cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;
    cout<<jmax<<" "<<ymax;
    
}

# 1019. 数字黑洞 (20)

题目描述给定任一个各位数字不完全相同的4位正整数，如果我们先把4个数字按非递增排序，再按非递减排序，然后用第1个数字减第2个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的6174，这个神奇的数字也叫Kaprekar常数。

例如，我们从6767开始，将得到

7766 - 6677 = 1089 9810 - 0189 = 9621 9621 - 1269 = 8352 8532 - 2358 = 6174 7641 - 1467 = 6174 ... ...

现给定任意4位正整数，请编写程序演示到达黑洞的过程。

输入描述: 输入给出一个(0, 10000)区间内的正整数N。

输出描述: 如果N的4位数字全相等，则在一行内输出“N - N = 0000”；否则将计算的每一步在一行内输出，直到6174作为差出现，输出格式见样例,每行中间没有空行。注意每个数字按4位数格式输出。

输入例子: 6767

输出例子: 7766 - 6677 = 1089 9810 - 0189 = 9621 9621 - 1269 = 8352 8532 - 2358 = 6174

注意：

输出的数字都是字符串的形式，否则不符合要求。
注意四个数都相同的情况。
注意两数之差也是字符串的形式的输出。

C++

#include<iostream>
#include<string>
#include <sstream>
#include<algorithm>			
using namespace std;
bool up(int i,int j){ return (i<j);}    //升序排列字符串
bool down(int i,int j){ return (i>j);}  //降序排列字符串

string intToString(int a);				//int -> string
int StringToint(string str);			// string -> int

string subtractionToString(string big,string small);     //把排序后的两个字符串之差，进行补零
string upsort(string n);                //对字符串进行升序处理
string downsort(string n);				//对字符串进行降序处理

bool inequal(string n);					//判断字符串的数字元素是否全部相同
int main(){
	int big,small;
    string str;
	cin>>str;
	str.insert(0,4-str.size(),'0');            //不足4位的补零
	
	//判断数字是否全相同
	if(!inequal(str)){
		cout<<upsort(str)<<" - "<<downsort(str)<<" = "<<subtractionToString(upsort(str),downsort(str))<<endl;
	}else{
		do{
		cout<<upsort(str)<<" - "<<downsort(str)<<" = "<<subtractionToString(upsort(str),downsort(str))<<endl;
		str=subtractionToString(upsort(str),downsort(str));

		}while(StringToint(str)!=6174);
	
	}

	return 0;
}

// 对两个字符串数之间的差转换为string，并补零
string subtractionToString(string big,string small){
	int b=StringToint(big);
	int s=StringToint(small);
	int c=b-s;
	string sc=intToString(c);          //把int-> string
	sc.insert(0,4-sc.size(),'0');      //补零
	return sc;
}

//判断字符串数字是否全相同
bool inequal(string n){
	bool t=false;
	int a[4];
	for (int i = 0;i<n.size();i++){    //把字符串的数字一个个赋值给数组
		a[i]=n[i] - '0';   
	}
	for(int i=0;i<4;i++){    //判断数组元素是否全相同
		if(a[0]!=a[i]){
			t=true;
		}
	}
	return t;
}

//对字符串数字进行升序处理，并返回
string upsort(string n){
	string r;
	stringstream sum;
	int a[4];

	for (int i = 0;i<n.size();i++){    //把字符串的数字一个个赋值给数组
		a[i]=n[i] - '0';   
	}
	sort(a,a+4,up);						//升序排序数组
	sum<<a[0]+a[1]*10+a[2]*100+a[3]*1000;         
	r=sum.str();
	r.insert(0,4-r.size(),'0');            //不足4位的补零

	return r;
}

//对字符串数字进行降序处理，并返回
string downsort(string n){
	string r;
    stringstream sum;
	int a[4];

	for(int i=0;i<n.size();i++){
		a[i]=n[i]-'0';
	}
	sort(a,a+4,down);   
	sum<<a[0]+a[1]*10+a[2]*100+a[3]*1000;
    r=sum.str();
	r.insert(0,4-r.size(),'0');            //不足4位的补零

	return r;
}

// int->string
string intToString(int a){
	stringstream s;
	s<<a;
	return s.str();
}

// string->int
int StringToint(string str){
	int n;
	n = atoi(str.c_str());    //把string -> int
	return n;
}

# 1020：月饼 (25)

题目描述月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需

求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有3种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最大需求量只有20万吨，那么我们最大收益策略应该是卖出全部15万吨第2种月饼、以及5万吨第3种月饼，获得72 + 45/2 = 94.5（亿元）。

输入描述: 每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数、以及不超过500（以万吨为单位）的正整数D表示市场最大需求量。随后一行给出N个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出描述: 对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后2位。

输入例子: 3 20

18 15 10

75 72 45

输出例子: 94.50

==C++==


#include<iostream>
#include<string>
#include<algorithm>			
using namespace std;
struct yuebing{
	double price;
	double sumprice;
	double stock;
};
int down(struct yuebing a,struct yuebing b)    //对结构体进行单价的降序处理
{
	return a.price>b.price;
}
int main(){

	/*
	思路： 求出每种月饼的单价，
		  最大收益就是先把单价最高（利润最大的）先卖完。
		  在卖其次的月饼。
	*/


	int kind,max_need,max_stock=0;  //max_need 是给出的最大需求量，max_stock是所有月饼的存储量之和
	struct yuebing yb[10000];
	double sum_money=0;              //最大收益

	cin>>kind>>max_need;  
	for(int i=0;i<kind;i++){
		cin>>yb[i].stock;
		max_stock=max_stock+yb[i].stock;
	}
	for(int i=0;i<kind;i++){   //输入总价，并计算出单价
		cin>>yb[i].sumprice;
		yb[i].price=yb[i].sumprice/yb[i].stock;
	}
	
	sort(yb,yb+kind,down);      //对月饼进行单价的降序排序

	if(max_need>max_stock){
		for(int i=0;i<kind;i++){
			sum_money=sum_money+yb[i].sumprice;
		}
		 
		 printf("%.2f\n",sum_money); //保留两位小数输出
	}else{

	
		for(int i=0;i<kind;i++){
			if(max_need>yb[i].stock){
				sum_money=sum_money+yb[i].sumprice;
				max_need=max_need-yb[i].stock;
			}else{
				sum_money=sum_money+yb[i].price*max_need;
				break;
			}
		}

		printf("%.2f\n",sum_money); //保留两位小数输出
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

# 1021: 个位数统计 (15)

题目描述给定一个k位整数N = dk-110k-1 + ... + d1101 + d0 (0<=di<=9, i=0,...,k-1, dk-1>0)，请编写程序统计每种不同的个位数字出现的次数。例如：给定N = 100311，则有2个0，3个1，和1个3。

输入描述: 每个输入包含1个测试用例，即一个不超过1000位的正整数N。

输出描述: 对N中每一种不同的个位数字，以D:M的格式在一行中输出该位数字D及其在N中出现的次数M。要求按D的升序输出。

输入例子: 100311

输出例子: 0:2

1:3

3:1

==C++==


#include<iostream>
#include<string>
using namespace std;
int main(){
   
	string n;
	int a[10]={0,0,0,0,0,0,0,0,0,0};   //a[0] 就是表示0出现的个数

	cin>>n;

	for(int i=0;i<n.size();i++){

		if((n[i]-'0')==0){              //n[i]-'0': 表示把数字的string类型转换为int类型。
			a[0]++;
		}else if((n[i]-'0')==1){
			a[1]++;
		}else if((n[i]-'0')==2){
			a[2]++;
		}else if((n[i]-'0')==3){
			a[3]++;
		}else if((n[i]-'0')==4){
			a[4]++;
		}else if((n[i]-'0')==5){
			a[5]++;
		}else if((n[i]-'0')==6){
			a[6]++;
		}else if((n[i]-'0')==7){
			a[7]++;
		}else if((n[i]-'0')==8){
			a[8]++;
		}else if((n[i]-'0')==9){
			a[9]++;
		}
	}


	for(int i=0;i<10;i++){           //循环输出
		if(a[i]!=0){
			cout<<i<<":"<<a[i]<<endl;
		}
	}
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# 1022: D进制的A+B (20)

题目描述输入两个非负10进制整数A和B(<=230-1)，输出A+B的D (1 < D <= 10)进制数。

输入描述: 输入在一行中依次给出3个整数A、B和D。

输出描述: 输出A+B的D进制数。

输入例子: 123 456 8

输出例子: 1103

==C++==


#include<iostream>
#include<string>
using namespace std;
int main()
{	
	/*
	 转换进制的思想就相当于求余数。
	*/

	int a,b,c,sum;   //c为输入的进制
	int d[100];      //存放sum转换后的每位数字
	int i=0;
	cin>>a>>b>>c;
	sum=a+b;

	while(sum!=0){
		d[i]=sum%c;        //对sum,c 之间求余数，结果存放在d数组中
		i++;
		sum=sum/c;
	}

	//最后所得到的数组就是一个个余数的组合，把它逆序输出就是sum转换为c进制的数
	for(int j=i-1;j>=0;j--){
		cout<<d[j];
	}
	
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 1023: 组个最小数 (20)

题目描述给定数字0-9各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意0不能做首位）。

例如：给定两个0，两个1，三个5，一个8，我们得到的最小的数就是10015558。

现给定数字，请编写程序输出能够组成的最小的数。

输入描述: 每个输入包含1个测试用例。每个测试用例在一行中给出10个非负整数，顺序表示我们拥有数字0、数字1、……数字9的个数。整数间用一个空格分隔。10个数字的总个数不超过50，且至少拥有1个非0的数字。

输出描述: 在一行中输出能够组成的最小的数。

输入例子: 2 2 0 0 0 3 0 0 1 0

输出例子: 10015558

==C++==


#include<iostream>
using namespace std;
int main()
{	
	/*
	2 2 0 0 0 3 0 0 1 0
	10015558

	解题思路：
		1.如果有0的话，找到只比0大的且存在的数字，取一个放到输出的第一个。
		2.其余的按从小到大的顺序排列这些数字就够了。

	*/

	int a[10];
	for(int i=0;i<10;i++){
		cin>>a[i];
	}

	for(int i=0;i<10;i++){    //用于输出第一个数，该数只比0大，并且把该数的数量-1
		if(a[i]!=0&&i!=0){
			cout<<i;
			a[i]=a[i]-1;
			break;
		}
	}

	for(int i=0;i<10;i++){   //按从小到大的顺序排列这些数字
		if(a[i]!=0){
			for(int j=0;j<a[i];j++){
				cout<<i;
			}
		}
	}
	
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 1024: 科学计数法 (20)

题目描述科学计数法是科学家用来表示很大或很小的数字的一种方便的方法，其满足正则表达式[+-][1-9]"."[0-9]+E[+-][0-9]+，即数字的整数部分

只有1位，小数部分至少有1位，该数字及其指数部分的正负号即使对正数也必定明确给出。

现以科学计数法的格式给出实数A，请编写程序按普通数字表示法输出A，并保证所有有效位都被保留。

输入描述: 每个输入包含1个测试用例，即一个以科学计数法表示的实数A。该数字的存储长度不超过9999字节，且其指数的绝对值不超过9999。

输出描述: 对每个测试用例，在一行中按普通数字表示法输出A，并保证所有有效位都被保留，包括末尾的0。

输入例子: +1.23400E-03

输出例子: 0.00123400

==C++==

1
2

# 1025: 反转链表 (25)

题目描述给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为

3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。

输入描述: 每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 105)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为： Address Data Next

其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。

输出描述: 对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入例子: 00100 6 4

00000 4 99999

00100 1 12309

68237 6 -1

33218 3 00000

99999 5 68237

12309 2 33218

输出例子: 00000 4 33218

33218 3 12309

12309 2 00100

00100 1 99999

99999 5 68237

68237 6 -1

==C++==

1
2

# 1026:程序运行时间(15)

题目描述要获得一个C语言程序的运行时间，常用的方法是调用头文件time.h，其中提供了clock()函数，可以捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。同时还有一个常数CLK_TCK，给出了机器时钟每秒所走的时钟打点数。

于是为了获得一个函数f的运行时间，我们只要在调用f之前先调用clock()，获得一个时钟打点数C1；在f执行完成后再调用clock()，获得另一个时钟打点数C2；两次获得的时钟打点数之差(C2-C1)就是f运行所消耗的时钟打点数，再除以常数CLK_TCK，就得到了以秒为单位的运行时间。

这里不妨简单假设常数CLK_TCK为100。现给定被测函数前后两次获得的时钟打点数，请你给出被测函数运行的时间。

输入描述: 输入在一行中顺序给出2个整数C1和C1。注意两次获得的时钟打点数肯定不相同，即C1 < C2，并且取值在[0, 107]

输出描述: 在一行中输出被测函数运行的时间。运行时间必须按照“hh:mm:ss”（即2位的“时:分:秒”）格式输出；不足1秒的时间四舍五入到秒。

输入例子: 123 4577973

输出例子: 12:42:59

==C++==


#include<iostream>
#include<string>
using namespace std;
int main(){
   
	long c1=0,c2=0,c3=0;           //c3为函数运行的时间，以秒为单位
	int h,m,s;				//h代表小时，m代表分钟，s代表秒

	cin>>c1>>c2;

	c3=(c2-c1)/100;        
	
	h=c3/3600;             //计算h的多少
	m=(c3-h*3600)/60;
	s=c3-h*3600-m*60;

	if(h<10){                    //若h<10,例如 h=8,则打印输出为 08
		cout<<"0"<<h;
	}else{
		cout<<h;
	}

	if(m<10){
		cout<<":0"<<m;
	}else{
		cout<<":"<<m;
	}

	if(s<10){
		cout<<":0"<<s;
	}else{
		cout<<":"<<s;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 1027:打印沙漏(20)

题目描述本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个“*”，要求按下列格式打印

*****
 ***
  *
 ***
*****

1
2
3
4
5

所谓“沙漏形状”，是指每行输出奇数个符号；各行符号中心对齐；相邻两行符号数差2；符号数先从大到小顺序递减到1，再从小到大顺序递增；首尾符号数相等。

给定任意N个符号，不一定能正好组成一个沙漏。要求打印出的沙漏能用掉尽可能多的符号。

输入描述: 输入在一行给出1个正整数N（<=1000）和一个符号，中间以空格分隔。

输出描述: 首先打印出由给定符号组成的最大的沙漏形状，最后在一行中输出剩下没用掉的符号数。

输入例子:

19 *

输出例子:

*****

 ***

 *

 ***

*****

2

1
2
3
4
5
6
7
8
9
10
11

==C++==

1
2

# 1028:人口普查(20)

题目描述某城镇进行人口普查，得到了全体居民的生日。现请你写个程序，找出镇上最年长和最年轻的人。

这里确保每个输入的日期都是合法的，但不一定是合理的——假设已知镇上没有超过200岁的老人，而今天是2014年9月6日，所以超过200岁的生日和未出生的生日都是不合理的，应该被过滤掉。

输入描述: 输入在第一行给出正整数N，取值在(0, 105]；随后N行，每行给出1个人的姓名（由不超过5个英文字母组成的字符串）、以及按“yyyy/mm/dd”（即年/月/日）格式给出的生日。题目保证最年长和最年轻的人没有并列。

输出描述: 在一行中顺序输出有效生日的个数、最年长人和最年轻人的姓名，其间以空格分隔。

输入例子: 5

John 2001/05/12

Tom 1814/09/06

Ann 2121/01/30

James 1814/09/05

Steve 1967/11/20

输出例子: 3 Tom John

==C++==

1
2

# 1029:旧键盘 (20)

题目描述旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。

输入描述: 输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。

输出描述: 按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。

输入例子: 7_This_is_a_test

_hs_s_a_es

输出例子: 7TI

==C++==

1
2

# 1030:完美数列(25)

题目描述给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。

现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入描述: 输入第一行给出两个正整数N和p，其中N（<= 105）是输入的正整数的个数，p（<= 109）是给定的参数。第二行给出N个正整数，每个数不超过109。

输出描述: 在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入例子: 10 8

2 3 20 4 5 1 6 7 8 9

输出例子: 8

==C++==

1
2

# 1031. 查验身份证(15)

题目描述一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：

首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得

到值Z；最后按照以下关系对应Z值与校验码M的值：

Z：0 1 2 3 4 5 6 7 8 9 10

M：1 0 X 9 8 7 6 5 4 3 2

现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。

输入描述: 输入第一行给出正整数N（<= 100）是输入的身份证号码的个数。随后N行，每行给出1个18位身份证号码。

输出描述: 按照输入的顺序每行输出1个有问题的身份证号码。这里并不检验前17位是否合理，只检查前17位是否全为数字且最后1位校验码计算准确。如果所有号码都正常，

则输出“All passed”。

输入例子: 4

320124198808240056

12010X198901011234

110108196711301866

37070419881216001X

输出例子: 12010X198901011234

110108196711301866

37070419881216001X

==C++==

1
2

# 1032:挖掘机技术哪家强(20)

题目描述为了用事实说明挖掘机技术到底哪家强，PAT组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入描述: 输入在第1行给出不超过105的正整数N，即参赛人数。随后N行，每行给出一位参赛者的信息和成绩，包括其所代表的学校的编号（从1开始连续编号）、及其比赛成绩（百分制），中间以空格分隔。

输出描述: 在一行中给出总得分最高的学校的编号、及其总分，中间以空格分隔。题目保证答案唯一，没有并列。

输入例子: 6

3 65

2 80

1 100

2 70

3 40

3 0

输出例子: 2 150

==C++==

1
2

# 1033:旧键盘打字(20)

题目描述旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键，打出的结果文字会是怎样？

输入描述: 输入在2行中分别给出坏掉的那些键、以及应该输入的文字。其中对应英文字母的坏键以大写给出；每段文字是不超过10^5个字符的串。可用的字符包括字母[a-z, A-Z]、数字0-9、以及下划线“_”（代表空格）、“,”、“.”、“-”、“+”（代表上档键）。题目保证第2行输入的文字串非空。

注意：如果上档键坏掉了，那么大写的英文字母无法被打出。

输出描述: 在一行中输出能够被打出的结果文字。如果没有一个字符能被打出，则输出空行。

输入例子: 7+IE.

7_This_is_a_test.

输出例子: _hs_s_a_tst

==C++==

1
2

# 1034:有理数四则运算(20)

题目描述本题要求编写程序，计算2个有理数的和、差、积、商。

输入描述: 输入在一行中按照“a1/b1 a2/b2”的格式给出两个分数形式的有理数，其中分子和分母全是整型范围内的整数，负号只可能出现在分子前，分母不为0。

输出描述: 分别在4行中按照“有理数1 运算符有理数2 = 结果”的格式顺序输出2个有理数的和、差、积、商。注意输出的每个有理数必须是该有理数的最简形式“k a/b”，其中k是整数部分，a/b是最简分数部分；若为负数，则须加括号；若除法分母为0，则输出“Inf”。题目保证正确的输出中没有超过整型范围的整数。

输入例子: 5/3 0/6

输出例子: 1 2/3 + 0 = 1 2/3

1 2/3 - 0 = 1 2/3

1 2/3 * 0 = 0

1 2/3 / 0 = Inf

C++

1
2

# 1035: 插入与归并(25)

题目描述根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成N个只包含1个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下1个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入描述: 输入在第一行给出正整数N (<=100)；随后一行给出原始序列的N个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出描述: 首先在第1行中输出“Insertion Sort”表示插入排序、或“Merge Sort”表示归并排序；然后在第2行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行末不得有多余空格。

输入例子: 10

3 1 2 8 7 5 9 4 6 0

1 2 3 7 8 5 9 4 6 0

输出例子: Insertion Sort

1 2 3 5 7 8 9 4 6 0

==C++==

1
2

# 1036:跟奥巴马一起编程(15)

题目描述美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！

输入描述: 输入在一行中给出正方形边长N（3<=N<=20）和组成正方形边的某种字符C，间隔一个空格。

输出描述: 输出由给定字符C画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的50%（四舍五入取整）。

输入例子: 10 a

输出例子: aaaaaaaaaa

a a

aaaaaaaaaa

==C++==

1
2

# 1037:在霍格沃茨找零钱（20）

题目描述如果你是哈利·波特迷，你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的：“十七个银西可(Sickle)兑一个加隆(Galleon)，二十九个纳特(Knut)兑一个西可，很容易。”现在，给定哈利应付的价钱P和他实付的钱A，你的任务是写一个程序来计算他应该被找的零钱。

输入描述: 输入在1行中分别给出P和A，格式为“Galleon.Sickle.Knut”，其间用1个空格分隔。这里Galleon是[0, 107]]区间内的整数，Sickle是[0, 17)区间内的整数，Knut是[0, 29)区间内的整数。

输出描述: 在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。

输入例子: 10.16.27 14.1.28

输出例子: 3.2.1

==C++==

1
2

# 1038:统计同成绩学生(20)

题目描述本题要求读入N名学生的成绩，将获得某一给定分数的学生人数输出。

输入描述: 输入在第1行给出不超过105的正整数N，即学生总人数。随后1行给出N名学生的百分制整数成绩，中间以空格分隔。最后1行给出要查询的分数个数K（不超过N的正整数），随后是K个分数，中间以空格分隔。

输出描述: 在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。

输入例子: 10

60 75 90 55 75 99 82 90 75 50

3 75 90 88

输出例子: 3 2 0

==C++==

1
2

# 1039:到底买不买（20）

题目描述小红想买些珠子做一串自己喜欢的珠串。卖珠子的摊主有很多串五颜六色的珠串，但是不肯把任何一串拆散了卖。于是小红要你帮忙判断一下，某串珠子里是否包含了全部自己想要的珠子？如果是，那么告诉她有多少多余的珠子；如果不是，那么告诉她缺了多少珠子。

为方便起见，我们用[0-9]、[a-z]、[A-Z]范围内的字符来表示颜色。例如，YrR8RrY是小红想做的珠串；那么ppRYYGrrYBR2258可以买，因为包含了全部她想要的珠子，还多了8颗不需要的珠子；ppRYYGrrYB225不能买，因为没有黑色珠子，并且少了一颗红色的珠子。

输入描述: 每个输入包含1个测试用例。每个测试用例分别在2行中先后给出摊主的珠串和小红想做的珠串，两串都不超过1000个珠子。

输出描述: 如果可以买，则在一行中输出“Yes”以及有多少多余的珠子；如果不可以买，则在一行中输出“No”以及缺了多少珠子。其间以1个空格分隔。

输入例子: ppRYYGrrYBR2258

YrR8RrY

输出例子: Yes 8

==C++==

1
2

# 1040: 有几个PAT（25）

题目描述字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。

现给定字符串，问一共可以形成多少个PAT？

输入描述: 输入只有一行，包含一个字符串，长度不超过105，只包含P、A、T三种字母。

输出描述: 在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。

输入例子: APPAPT

输出例子: 2

==C++==

1
2

suichentree's blog

PAT乙级

PAT乙级

# PAT 乙级（Basic Level）

# PAT乙级真题及训练集

# 1001. 害死人不偿命的(3n+1)猜想 (15分)

# 1002. 写出这个数 (20分)：

# 1003. 我要通过！(20)

# 1004. 成绩排名 (20)

# 1005. 继续(3n+1)猜想 (25):

# 1006. 换个格式输出整数 (15)

# 1007. 素数对猜想 (20):

# 1008. 数组元素循环右移问题 (20):

# 1009. 说反话 (20)

这个是借鉴别人的思路，思路清奇。但这个有运行超时的可能，

# 1010. 一元多项式求导 (25)：

# 1011: A+B和C (15)

# 1012：数字分类 (20)

# 1013: 数素数 (20)

# 1014：福尔摩斯的约会 (20)

# 1015: 德才论 (25)

这个demo有问题，题目给出的示例过了，但测试没过，我也不知为什么？

# 1016: 部分A+B (15)

# 1017：A除以B (20)：

# 1018：锤子剪刀布 (20)

# 1019. 数字黑洞 (20)

# 1020：月饼 (25)

# 1021: 个位数统计 (15)

# 1022: D进制的A+B (20)

# 1023: 组个最小数 (20)

# 1024: 科学计数法 (20)

# 1025: 反转链表 (25)

# 1026:程序运行时间(15)

# 1027:打印沙漏(20)

# 1028:人口普查(20)

# 1029:旧键盘 (20)

# 1030:完美数列(25)

# 1031. 查验身份证(15)

# 1032:挖掘机技术哪家强(20)

# 1033:旧键盘打字(20)

# 1034:有理数四则运算(20)

# 1035: 插入与归并(25)

# 1036:跟奥巴马一起编程(15)

# 1037:在霍格沃茨找零钱（20）

# 1038:统计同成绩学生(20)

# 1039:到底买不买（20）

# 1040: 有几个PAT（25）