PAT_B 分类题解

tuan_liu

2019-04-21

OJ, PAT

list:

two pointers

递推

1:1040 有几个PAT (25 分)

快排

1:1045 快速排序 (25 分)

简单模拟
1001 害死人不偿命的(3n+1)猜想（15 分)
题目链接
思路：
基本语句的使用，判断奇偶数的方法。（简单题）

#include <stdio.h>
int main(){
	int a;
	int cishu = 0;
	scanf("%d", &a);
	while (a != 1){
		if (a % 2 == 0){
			a /= 2;
			cishu++;
		}
		else if (a % 2 == 1){
			a = 3 * a + 1;
			a /= 2;
			cishu++;
		}
	}
	printf("%d", cishu);
	return 0;
}

1008 数组元素循环右移问题（20 分)
题目链接
思路：
要保证输入的m<n，不然不符合题意，令m=m%n即实现这个功能。
设置一个count变量可以实现输出或者不输出之类的不同输出形式的要求。

#include<stdio.h>
int main(){
    int a[110],n,m;
    scanf("%d%d",&n,&m);
    m=m%n;//notice
    int count=n;//控制是否在数字后面打印空格
    for(int i=0;i<n;i++){//首先先把数字给输入进去
        scanf("%d",&a[i]);
    }
    for(int i=n-m;i<n;i++){//输出n-m到n-1
        printf("%d",a[i]);//只要打印出来就行，而不需要存入数组中
        count--;
        if(count!=0)    printf(" ");
    }
    for(int i=0;i<n-m;i++){//输出0到n-m-1
        printf("%d",a[i]);
        count--;
        if(count!=0)    printf(" ");
    }
    return 0;
}

1011 A+B 和 C （15 分)
题目链接
思路：
数字的表示范围明显超出了int型表示的范围，所以可以用long long类型。
使用一个变量去输出case #1。

#include<stdio.h>
int main(){
    int t;
    scanf("%d",&t);
    long long a,b,c;
    int cases=0;
    for(int i=0;i<t;i++){
        cases++;
        scanf("%lld%lld%lld",&a,&b,&c);
        if(a+b>c){
            printf("Case #%d: true\n",cases);
        }else{
            printf("Case #%d: false\n",cases); 
        }
    }
    return 0;
}

1016 部分A+B （15 分)
题目链接
思路：
学会使用适当的除操作，取余操作去实现取出整数中的每一位。

#include<stdio.h>
int main(){
    long long a,b;
    long long da,db;
    long long pa=0,pb=0;
    scanf("%lld%lld%lld%lld",&a,&da,&b,&db);
    while(a!=0){
        if(a%10==da)    pa=pa*10+da;//important
        a=a/10;
    }
    while(b!=0){
        if(b%10==db)    pb=pb*10+db;//important
        b=b/10;
    }
    printf("%lld\n",pa+pb);
    return 0;
}

1026 程序运行时间（15 分)
题目链接
思路：
1：ans/100是因为要换算为s（秒）单位。
2：题目要求四舍五入，因此需要对c2-c1的末两位来判断四舍还是五入，当后两位不小于50时，则要进位。
如何看c2-c1的末两位？取余100。
3：类似的操作还有:看一个整数的个位:取余10（a%10）；看一个两位整数的十位，除10（a/10）；
看一个三位整数的十位，先除10再取余10（a/10%10）；看一个三位整数的百位，除100（a/100）;
看一个四位整数的百位，先除100，再取余10（a/100%10）…
4：ans/3600就是小时数，ans%3600就是去除小时数后剩余的部分，这个部分再除以60就是分钟数，取余就是秒数。

#include<stdio.h>
int main(){
    int c1,c2;
    scanf("%d%d",&c1,&c2);
    int ans=c2-c1;
    if(ans%100>=50){//要进位
        ans=ans/100+1;
    }else{//不需要进位
        ans=ans/100;
    }
    printf("%02d:%02d:%02d\n",ans/3600,ans%3600/60,ans%60);
    return 0;
}

1046 划拳（15 分)
题目链接

#include<stdio.h>
int main(){
    int cishu;
    scanf("%d",&cishu);
    int jhan,jhua,yhan,yhua;
    int jhe=0,yhe=0;
    for(int i=0;i<cishu;i++){
        scanf("%d%d%d%d",&jhan,&jhua,&yhan,&yhua);
        if(jhua==jhan+yhan&&yhua!=jhan+yhan){
            yhe++;
        }
        if(yhua==jhan+yhan&&jhua!=jhan+yhan){
            jhe++;
        }
    }
    printf("%d %d\n",jhe,yhe);
    return 0;
}

1012 数字分类（20 分)
题目链接
思路：
想到用数组去处理。
最后一个输出后面不能有空格，不然会有格式错误。

#include<stdio.h>
int main(){
    int count[5]={0};//存放五类数字的个数
    int ans[5]={0};//五类数字的输出结果
    int n,temp;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&temp);
        if(temp%5==0){
            if(temp%2==0){
                ans[0]+=temp;
                count[0]++;
            }
        }else if(temp%5==1){
            if(count[1]%2==0){
                ans[1]+=temp;
            }else{
                ans[1]-=temp;
            }
            count[1]++;
        }else if(temp%5==2){
            count[2]++;
            //printf("count[2]");
        }else if(temp%5==3){
            ans[3]+=temp;
            count[3]++;
            //ans[3]=ans[3]/count[3];
            //printf("%.1\n",ans[3]);
        }else{
            if(ans[4]<temp){
                ans[4]=temp;
            }
            count[4]++;
        }
        
    }

    if(count[0]==0) printf("N ");
    else    printf("%d ",ans[0]);
    if(count[1]==0) printf("N ");
    else    printf("%d ",ans[1]);
    if(count[2]==0) printf("N ");
    else    printf("%d ",count[2]);
    if(count[3]==0) printf("N ");
    else    printf("%.1f ",(double)ans[3]/count[3]);
    if(count[4]==0) printf("N");//这里的N后面没有空格
    else    printf("%d",ans[4]);//这里是"%d",不是"%d "
    return 0;
}

1018 锤子剪刀布（20 分)notice
题目链接
思路：
用changes函数，将字符与数字对应，这样可以更方便的实现石头剪刀布的游戏规则。
scanf(“%c”)会将你输入的\n等都输出到屏幕上，我们要避免这种情况，就需要用getchar()去吸取掉。

#include<stdio.h>

int changes(char a){
    if(a=='B')  return 0;
    if(a=='C')  return 1;
    if(a=='J')  return 2;
}

int main(){
    int frequency;
    scanf("%d",&frequency);
    char jia,yi;
    char mp[3]={'B','C','J'};
    int time_A[3]={0};
    int time_B[3]={0};
    int hand_A[3]={0},hand_B[3]={0};

    for(int i=0;i<frequency;i++){
        getchar();//
        scanf("%c %c",&jia,&yi);
        int k1=changes(jia);
        int k2=changes(yi);
        if((k1+1)%3==k2){//好好理解一下
            time_A[0]++;
            time_B[2]++;
            hand_A[k1]++;
        }else if(k1==k2){
            time_A[1]++;
            time_B[1]++;
        }else{
            time_A[2]++;
            time_B[0]++;
            hand_B[k2]++;
        }
    }
    printf("%d %d %d\n",time_A[0],time_A[1],time_A[2]);
    printf("%d %d %d\n",time_B[0],time_B[1],time_B[2]);

    int id1=0,id2=0;
    for(int i=0;i<3;i++){
        if(hand_A[i]>hand_A[id1])   id1=i;
        if(hand_B[i]>hand_B[id2])   id2=i;
    }
    printf("%c %c\n",mp[id1],mp[id2]);
    return 0;
}

** 1010 一元多项式求导（25 分) **
题目链接
思路：
使用数组a,将多项式的系数和次数的对应关系联系起来，即“a[多项式的指数]=对应多项式的系数”。
变量count是统计非零项的个数的。
注意输出的格式。

#include<stdio.h>
int main(){
    int coefficient;
    int index;
    int count=0;
    int a[1010]={0};
    while(scanf("%d %d",&coefficient,&index)!=EOF){
        a[index]=coefficient;//important
    }
    a[0]=0;//常数项求导为0
    for(int i=1;i<=1000;i++){
        a[i-1]=i*a[i];//求导公式
        a[i]=0;//
        if(a[i-1]!=0)//如果是非零项，个数就加一
            count++;
    }
    if(count==0)
        printf("0 0");//指数和系数都是0的情况
    else{
        for(int i=1000;i>=0;i--){
            if(a[i]!=0){
                printf("%d %d",a[i],i);
                count--;
                if(count!=0)//如果还有未输出的非零项，那么紧接着要输出空格
                    printf(" ");
            }
        }
    }
    return 0;
}

查找元素
1041 考试座位号（15 分)
题目链接
思路：
处理不同类型的数据，可以使用结构体，且将试机座位号作为数组下标更好。
准考证是14位数字，所以可以用long long型来存储他。

#include<stdio.h>
const int maxn=1010;
struct Student{
        long long id;
        int zuohao;
}testseat[maxn];

int main(){
    int n;
    int chaxun;
    scanf("%d",&n);
    long long id;
    int jihao,zuohao;
    for(int i=0;i<n;i++){
        scanf("%lld%d%d",&id,&jihao,&zuohao);
        testseat[jihao].id=id;
        testseat[jihao].zuohao=zuohao;
    }
    scanf("%d",&chaxun);
    for(int i=0;i<chaxun;i++){
        scanf("%d",&jihao);
        printf("%lld %d\n",testseat[jihao].id,testseat[jihao].zuohao);
    }
    return 0;
}

1004 成绩排名（20 分)
题目链接
思路：
使用结构体，因为是只需要输出得分最值，所以没有必要对输入的所有学生信息都存储下来，只需要在for循环的时候再用if语句判断一下。
结构体里的数组类型，在输入的时候，前面不需要加取地址符（&）。
name[]数组最少要有十一个空间，因为字符数组最后要多存储\n作为结尾标记，题目说明name和id是字符长度不超过10,所以至少要超过11位。
注意输出格式。

#include<stdio.h>
struct Student{
    char name[15];
    char id[15];
    int score;
}temp,maxn,minn;

int main(){
    int n;
    maxn.score=-1;
    minn.score=101;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s%s%d",temp.name,temp.id,&temp.score);//notice
        if(temp.score>maxn.score)
            maxn=temp;
        if(temp.score<minn.score)
            minn=temp;
    }
    printf("%s %s\n",maxn.name,maxn.id);
    printf("%s %s\n",minn.name,minn.id);
    return 0;
}

1028 人口普查（20 分)
题目链接
思路：
使用结构体，最好使用单独的函数来判断年轻和年长。
注意输入和输出的格式，这里年长的日期在数值上看是最小的，年轻的日期在数值上看是最大的，这个要转过弯来。

#include<stdio.h>

struct Person{
    char name[10];
    int year,month,day;
}old,young,temp,left,right;

bool lessEqu(Person a,Person b){
    if(a.year!=b.year)  return a.year<=b.year;
    else if(a.month!=b.month)   return a.month<=b.month;
    else    return a.day<=b.day;
}

bool moreEqu(Person a,Person b){
    if(a.year!=b.year)  return a.year>=b.year;
    else if(a.month!=b.month)   return a.month>=b.month;
    else    return a.day>=b.day;
}

void init(){
    young.year=left.year=1814;
    old.year=right.year=2014;
    young.month=old.month=left.month=right.month=9;
    young.day=old.day=left.day=right.day=6;

}
int main(){
    init();
    int n,hefarenshu=0;
    scanf("%d",&n);
    
    for(int i=0;i<n;i++){
        scanf("%s %d/%d/%d",temp.name,&temp.year,&temp.month,&temp.day);//notice
        if(moreEqu(temp,left)&&lessEqu(temp,right)){
            hefarenshu++;
            if(lessEqu(temp,old))
                old=temp;
            if(moreEqu(temp,young))
                young=temp;
        }  
    }
    if(hefarenshu==0)   printf("0\n");//notice
    else
        printf("%d %s %s\n",hefarenshu,old.name,young.name);//notice
    
    return 0;
}

1032 挖掘机技术哪家强（20 分)
题目链接

#include<stdio.h>
const int maxn=100010;
int school[maxn]={0};
int main(){
    int num;
    int id;
    int score=0;
    scanf("%d",&num);
    
    for(int i=0;i<num;i++){
        scanf("%d%d",&id,&score);
        school[id]+=score;
        
    }
    int maxscore=-1,maxid=1;
    for(int i=1;i<=num;i++){
        if(school[i]>maxscore){
            maxscore=school[i];
            maxid=i;
        }
    }
    
    printf("%d %d",maxid,maxscore);
    return 0; 
}

图形输出

1036 跟奥巴马一起编程（15 分)
思路：
题目要求高是宽的一半，且满足四舍五入，所以要判断奇偶。
注意输出格式。

#include<stdio.h>

int main(){
    int n;
    char zifu;
    int high;
    scanf("%d %c",&n,&zifu);
    if(n%2==0)
        high=n/2;
    else
        high=n/2+1;
    for(int i=0;i<n;i++){
        printf("%c",zifu);
    }
    printf("\n");
    for(int i=0;i<high;i++){
        printf("%c",zifu);
        for(int j=0;j<n-2;j++){
            printf(" ");
        }
        printf("%c\n",zifu);
    }
    for(int i=0;i<n;i++){
        printf("%c",zifu);
    }
    return 0;
}

1027 打印沙漏（20 分)
思路：
这里要先能够算出这个类似两个三角形的底边长，然后要找要输出的字符和空格之间的关系。


#include<stdio.h>
#include<math.h>
int main(){
    int n;
    char zifu;
    scanf("%d %c",&n,&zifu);
    int bottom=(int)sqrt(2.0*(n+1))-1;
    if(bottom%2==0) bottom--;
    int used=(bottom+1)*(bottom+1)/2-1;
    for(int i=bottom;i>=1;i-=2){
        for(int j=0;j<(bottom-i)/2;j++){
            printf(" ");
        }
        for(int j=0;j<i;j++){
            printf("%c",zifu);
        }
        printf("\n");
    }
    for(int i=3;i<=bottom;i+=2){
        for(int j=0;j<(bottom-i)/2;j++){
            printf(" ");
        }
        for(int j=0;j<i;j++){
            printf("%c",zifu);
        }
        printf("\n");
    }
    printf("%d\n",n-used);
    return 0;
}

进制转换

1022 D进制的A+B （20 分)
题目链接
思路：
这里就只考了除基取余法，直接用这个思路就行。
注意ans数组要倒着输出。

#include<stdio.h>
int main(){
    int a,b,d;
    scanf("%d%d%d",&a,&b,&d);
    int sum=a+b;
    int ans[31],num=0;
    do{//除基取余法
        ans[num++]=sum%d;
        sum/=d;
    }while(sum!=0);
    for(int i=num-1;i>=0;i--){//倒着输出
        printf("%d",ans[i]);
    }
    return 0;
}

1037 在霍格沃茨找零钱（20 分)
题目链接
思路：
将Galleon和Sickle都转化为Knut，然后再进行做差，就知道要找多少零钱了，在输出的时候再转化为各自的单位就行。
当实付的钱小于价格的时候，就要输出负值，如代码中的if语句。

#include<stdio.h>
const int Galleon=29*17;
const int Sickle=29;
int main(){
    int Galleona,Sicklea,Knuta,Galleonb,Sickleb,Knutb;
    scanf("%d.%d.%d %d.%d.%d",&Galleona,&Sicklea,&Knuta,&Galleonb,&Sickleb,&Knutb);//注意格式
    int price=Galleona*Galleon+Sicklea*Sickle+Knuta;
    int realp=Galleonb*Galleon+Sickleb*Sickle+Knutb;
    int chap=realp-price;
    if(chap<0){
        printf("-");//先输出负号
        chap=-chap;//再输出这个差价的绝对值
    }
    printf("%d.%d.%d\n",chap/Galleon,chap%Galleon/Sickle,chap%Sickle);//注意输出格式
    return 0;
}

1006 换个格式输出整数（15 分)
题目链接

#include<stdio.h>
int main(){
    int num;
    scanf("%d",&num);
    if(num/100!=0){
        int bai=num/100;
        for(int i=0;i<bai;i++){
            printf("B");
        }
    }
    if(num%100/10!=0){
        int shi=num%100/10;
        for(int i=0;i<shi;i++){
            printf("S");
        }
    }
    if(num%10!=0){
        int ge=num%10;
        for(int i=1;i<=ge;i++){
            printf("%d",i);
        }
    }
    return 0;
}

1021 个位数统计（15 分)
题目链接
思路：
用字符数组的形式输入题目中的正整数N，然后可以通过strlen获得N的长度。
其中str[i]-‘0’是将字符型数字转为整数型数字。

#include<stdio.h>
#include<string.h>

int main(){   
    char str[1000];
    gets(str);
    int len=strlen(str);
    int count[10]={0};
    for(int i=0;i<len;i++){
        count[str[i]-'0']++;
    }
    for(int i=0;i<10;i++){
        if(count[i]!=0)
            printf("%d:%d\n",i,count[i]);
    }
    return 0;
}

1031 查验身份证（15 分)
题目链接

#include<stdio.h>
#include<string.h>
int quanzhong[]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
char M[]={'1','0','X','9','8','7','6','5','4','3','2'};
int main(){
    int num;
    scanf("%d",&num);
    bool flag=true;
    char str[20];
    int last=0;
    int j;                           
    for(int i=0;i<num;i++){
        scanf("%s",str);//存储输入的身份证
        
        for(j=0;j<17;j++){
            if(!(str[i]>='0'&&str[j]<='9')) break;//非数字的话直接break
            last+=(str[j]-'0')*quanzhong[j];//记录了前17个数的加权和    
        }  
    }
    if(j<17){//这个if是在break跳出后会判定的地方，
        flag=false;//也即是有非数字存在后才会跳到这里
        printf("%s\n",str);//所以就是flag为false,打印身份证号码
    }else{
        if(M[last%11]!=str[17]){
            flag=false;
            printf("%s\n",str);//校验码不等于身份证最后一位的情况下
        }
    }
    if(flag==true){
        printf("All passed\n");
    }
    return 0;
}

1002 写出这个数 (20 分)
题目链接
思路：
用字符数组去存储输入的数，然后用for循环算出sum，接着使用while循环将sum中的每一个数字取出来放在ans数组中，最后以ans[i]作为shuzi[]数组的下标。

#include<stdio.h>
#include<string.h>
char shuzi[10][5]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
int main(){
    char str[110];
    gets(str);//用字符数组来存储
    int len=strlen(str);
    int sum;
    for(int i=0;i<len;i++){
        sum+=(str[i]-'0');//得到输入的数字的各位数的和
    }
    int num=0,ans[10];
    while(sum!=0){//将sum的每一位数字存在ans数组中
        ans[num]=sum%10;
        num++;
        sum/=10;
    }
    for(int i=num-1;i>=0;i--){
        printf("%s",shuzi[ans[i]]);
        if(i!=0)    printf(" ");
        else printf("\n");
    return 0;    
}

1009 说反话 (20 分)
题目链接
思路：
用二维数组去存储，要熟悉二维数组的操作，注意对是否输出空格的判断。

#include<stdio.h>
#include<string.h>
int main(){
    char str[90];
    gets(str);
    char ans[90][90];
    int len=strlen(str);
    int r,h=0;

    for(int i=0;i<len;i++){
        if(str[i]!=' '){
            ans[r][h++]=str[i];
        }else{
            ans[r][h]='\0';
            r++;
            h=0;
        }
    }
    for(int i=r;i>=0;i--){
        printf("%s",ans[i]);
        if(i>0) printf(" ");
    }
    return 0;
}

1014 福尔摩斯的约会 (20 分)
题目链接
思路：
注意理解清题意，然后使用二维数组去存储。

#include<stdio.h>
#include<string.h>
int main(){
    char riqi[7][5]={"MON","TUE","WED","THU","FRI","SAT","SUM"};//记得加分号
    char str1[70],str2[70],str3[70],str4[70];
    fgets(str1);
    fgets(str2);
    fgets(str3);
    fgets(str4);
    int len1=strlen(str1);
    int len2=strlen(str2);
    int len3=strlen(str3);
    int len4=strlen(str4);
    int i;
    for(i=0;i<len1&&i<len2;i++){
        if(str1[i]==str2[i]&&str1[i]>'A'&&str1[i]<'G'){
            printf("%s ",riqi[str1[i]-'A']);
            break;
        }
    }
    for(i++;i<len1&&i<len2;i++){
        if(str1[i]==str2[i]){
            if(str1[i]>='0'&&str1[i]<='9'){
                printf("%2d:",str1[i]-'0');
                break;
            }else if(str1[i]>='A'&&str1[i]<='G'){
                printf("%2d:",str1[i]-'A'+10);
                break;
            }
        }
    }
    for(int i=0;i<len3&&i<len4;i++){
        if(str3[i]==str4[i]){
            if(str3[i]>'A'&&str3[i]<'Z'||str3[i]>'a'&&str3[i]<'z'){
                printf("%02d",i);
                break;
            }
        }
    }
    return 0;
}

排序

1015 德才论 (25 分)
题目链接
思路：
要能够想到定义一个学生的类型
此题主要考察了sort函数的使用，需要同学们对stl有一个比较熟悉的理解，
还有就是考察了for循环语句的考察，尤其考察了if-else if语句的考察
还有就是结构体的使用

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

struct Student{
    char id[10];
    int de,cai,sum;
    int flag;//考生类别
}stu[100010];

bool cmp(Student a,Student b){
    
    if(a.flag!=b.flag)  return a.flag<b.flag;
    else if(a.sum!=b.sum) return a.sum>b.sum;
    else if(a.de!=b.de) return a.de>b.de;
    else return strcmp(a.id,b.id)<0;
}

int main(){
    int n,l,h,num=0;
    scanf("%d%d%d",&n,&l,&h);
    for(int i=0;i<n;i++){
        scanf("%s%d%d",stu[i].id,&stu[i].de,&stu[i].cai);
        stu[i].sum=stu[i].de+stu[i].cai;
        if(stu[i].de<l||stu[i].cai<l){
            stu[i].flag=5;
        }else if(stu[i].de>=h&&stu[i].cai>=h){
            stu[i].flag=1;
            num++;
        }else if(stu[i].de>=h&&stu[i].cai<=h){
            stu[i].flag=2;
            num++;
        }else if(stu[i].de<=h&&stu[i].de>=stu[i].cai){
            stu[i].flag=3;
            num++;
        }else{
            stu[i].flag=4;
            num++;
        }
            
    }
    
    sort(stu,stu+n,cmp);
    printf("%d\n",num);

    for(int i=0;i<num;i++){
        printf("%s %d %d\n",stu[i].id,stu[i].de,stu[i].cai);
    }
    return 0;
}

散列

1029 旧键盘 (20 分)
题目链接
思路：
两层for循环，用一个bool型数组hashtable来指明字符是否已经输出。

#include<stdio.h>

int main(){
    bool hashtable[128]={false};
    char yinggai[100];
    char shiji[100];
    gets(yinggai);
    gets(shiji);
    int len1=strlen(yinggai);
    int len2=strlen(shiji);
    for(int i=0;i<len1;i++){
        int j;
        char c1,c2;
        for(j=0;j<len2;j++){
            c1=yinggai[i];
            c2=shiji[j];
            if(c1>='a'&&c1<='z')    c1-=32;
            if(c2>='a'&&c2<='z')    c2-=32;
            if(c1==c2)  break;
        }
        if(j==len2&&hashtable[c1]==false){
            printf("%c",c1);
            hashtable[c1]=true;
        } 
    }
    return 0;
}

1033 旧键盘打字 (20 分)
题目链接

#include<stdio.h>
#include<string.h>
const int maxn=100010;
bool hashtable[256];
char str[maxn];
int main(){
    memset(hashtable,true,sizeof(hashtable));
    gets(str);//读入失效的键位
    int len=strlen(str);
    for(int i=0;i<len;i++){
        if(str[i]>='A'&&str[i]<='Z'){
            str[i]=str[i]-'A'+'a';//转为小写字母
        }
        hashtable[str[i]]=false;
    }
    gets(str);//读入要输入的字符串
    len=strlen(str);
    for(int i=0;i<len;i++){
        if(str[i]>='A'&&str[i]<='Z'){
            int low=str[i]-'A'+'a';//转为小写字母
        }
        if(hashtable[low]==true&&hashtable['+']=true){
            printf("%c",str[i]);
        }
    }
    printf("\n");
    return 0;
}

1038 统计同成绩学生 (20 分)
题目链接

#include<stdio.h>
int hashtable[110]={0};
int main(){
    int n,score,k;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&score);
        hashtable[score]++;
    }
    scanf("%d",&k);
    for(int i=0;i<k;i++){
        scanf("%d",&score);
        printf("%d",hashtable[score]);
        if(i<k-1){
            printf(" ");
        }
    }
    return 0;
}

1039 到底买不买 (20 分)
题目链接
思路：
因为颜色总共只有62种可能，26*2个大小字母+10个数字。所以我们完全可以开一个hashtable函数记录每一种颜色的珠子个数，这种想法是最基本的散列思想。

#include<stdio.h>
#include<string.h>

const int maxn=1010;

int change(char c){//将数字和字母转为hashtable的下标
    if(c>='0'&&c<='9')  return c-'0';
    if(c>='a'&&c<='z')  return c-'a'+10;
    if(c>='A'&&c<='Z')  return c-'A'+36;
}

int main(){
    int hashtable[80]={0};
    char xianyou[maxn],xuyao[maxn];
    int miss=0;
    gets(xianyou);
    gets(xuyao);
    int len1=strlen(xianyou);
    int len2=strlen(xuyao);
    for(int i=0;i<len1;i++){
        int id=change(xianyou[i]);
        hashtable[id]++;
    }
    for(int i=0;i<len2;i++){
        int id=change(xuyao[i]);
        hashtable[id]--;
        if(hashtable[id]<0){
            miss++;//miss是用来统计缺的珠子的个数
        }
    }
    if(miss>0)
        printf("No %d\n",miss);
    else{
        printf("Yes %d\n",len1-len2);//如果珠子多，只需相减就可以输出多的珠子的个数
    }
    return 0;
}

1042 字符统计 (20 分)
题目链接
思路：
基本题型。

#include<stdio.h>
#include<string.h>
const int maxn=1010;

int main(){
    int hashtable[30]={0};
    char shuru[maxn];
    gets(shuru);
    int len=strlen(shuru);
    for(int i=0;i<len;i++){
        if(shuru[i]>='a'&&shuru[i]<='z'){
            hashtable[shuru[i]-'a']++;
        }else if(shuru[i]>='A'&&shuru[i]<='Z'){
            hashtable[shuru[i]-'A']++;
        }
    }
    int k=0;
    for(int i=0;i<26;i++){
        if(hashtable[i]>hashtable[k]){
            k=i;
        }
    }
    printf("%c %d\n",'a'+k,hashtable[k]);
    return 0;
}

1020 月饼 (25 分)
题目链接
思路：
用结构体。
注意使用double型去定义库存，总售价，单价。
用sort排序，这样下面就可以使用for循环更方便的遍历处理。
根据这个月饼的库存和总需求之间的大小关系，用if-else去更新total_demand和ans。

#include<stdio.h>
#include<algorithm>
using namespace std;

struct mooncake{
    double store;//库存
    double price;//单价
    double total_revenue;//总售价
}cake[1010];

bool cmp(mooncake a,mooncake b){
    return a.price>b.price;
}

int main(){
    int kind;//种类
    double total_demand;//总需求
    
    scanf("%d%lf",&kind,&total_demand);
    for(int i=0;i<kind;i++){
        scanf("%lf",&cake[i].store); 
    }
    for(int i=0;i<kind;i++){
        scanf("%lf",&cake[i].total_revenue);
    }
    for(int i=0;i<kind;i++){
        cake[i].price=cake[i].total_revenue/cake[i].store;
    }
    sort(cake,cake+kind,cmp);//以单价从高到低排序
    double ans=0;//收益
    for(int i=0;i<kind;i++){//这里的逻辑要思考一下，注意
        if(cake[i].store<=total_demand){
            total_demand-=cake[i].store;
            ans+=cake[i].total_revenue;  
        }else{
           ans+=cake[i].price*total_demand;
           break;
        }
    }
    printf("%.2f\n",ans);
    return 0;
}

1023 组个最小数 (20 分)
题目链接
思路：
先从1-9中找出最小的数，输出在最前面，因为就算0存在，是最小，也不能输出在开头。这也是为什么从1开始遍历的原因。
输出最小的那个数之后，循环遍历输出剩余的数字，当这个数字的个数不为0时（也就是说这个数存在）就输出这个数字，且这个数字有多少个就输出多少个（这个数字对应的个数就是geshu[i]）。

#include<stdio.h>
int main(){
    int geshu[10];
    for(int i=0;i<10;i++){
        scanf("%d",&geshu[i]);
    }
    int min=0; //最小数
    for(int i=1;i<10;i++){//在1-9中找出最小数  
        if(geshu[i]!=0){
            geshu[i]--;
            min=i;
            break;//找到最小的数了就要break
        }
    }
    printf("%d",min);
    for(int i=0;i<10;i++){
        while(geshu[i]!=0){
            printf("%d",i);
            geshu[i]--;
        }
    }
    return 0;
}

1030 完美数列 (25 分)
题目链接
思路：
首先要知道能选出的数的个数最大的方案，一定是在该递增序列中选择连续的若干个数的方案。
先通过sort函数，将这输入的N个数递增排序。那么每截取一段数列，这个数列的最大值一定是在最右边，最小值一定是在最左边。
综上，这个问题就变为了：在输入的n个数中，截取出最长的数列，使得这个数列的最右边的数据小于等于最左边的数据乘以输入的数字p的乘积。
输出这个数列的长度。

#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100010;
int p,n,a[maxn];

int binarysearch(int i,long long x){//在i+1到n-1的范围内查找第一个大于x的数的位置
    if(a[n-1]<=x)   return n;
    int l=i+1,r=n-1,mid;
    while(l<r){
        mid=(l+r)/2;
        if(a[mid]<=x)   l=mid+1;
        else    r=mid;
    }
    return l;
}
int main(){
    scanf("%d%d",&n,&p);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    int ans=1;//最大长度，初始值为1
    for(int i=0;i<n;i++){
        int j=binarysearch(i,(long long)a[i]*p);
        ans=max(ans,j-i);
    }
    printf("%d\n",ans);
    return 0;
}

1035 插入与归并 (25 分)
题目链接

#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=111;
int origin[N],tempOri[N],changed[N];
int n;//元素个数
bool isSame(int A[],int B[]){
    for(int i=0;i<n;i++){
        if(A[i]!=B[i])
            return false;
    }
    return true;
}

bool showarray(int A[]){//输出数组
    for(int i=0;i<n;i++){
        printf("%d",A[i]);
        if(i<n-1)
            printf(" ");
    }
    printf("\n");
}

bool insertsort(){  //插入排序
    bool flag=false;
    for(int i=1;i<n;i++){
        if(i!=1&&isSame(tempOri,changed)){
            flag=true;
        }
        int temp=tempOri[i],j=i;
        while(j>0&&tempOri[j-1]>temp){
            tempOri[j]=tempOri[j-1];
            j--;
        }
        tempOri[j]=temp;
        if(flag==true){
            return true;
        }
    }
    return false;
}

void mergeSort(){
    bool flag=false;
    for(int step=2;step/2<=n;step*=2){
        if(step!=2&&isSame(tempOri,changed)){
            flag=true;
        }
        for(int i=0;i<n;i+=step){
            sort(tempOri+i,tempOri+min(i+step,n));
        }
        if(flag==true){
            showarray(tempOri);
            return;
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&origin[i]);
        tempOri[i]=origin[i];
    }
    for(int i=0;i<n;i++){
        scanf("%d",&changed[i]);
    }
    if(insertsort()){
        printf("Insertion Sort\n");
        showarray(tempOri);
    }else{
        printf("Merge Sort\n");
        for(int i=0;i<n;i++){
            tempOri[i]=origin[i];
        }
        mergeSort();
    }
    return 0;
}

1040 有几个PAT (25 分)
题目链接
思路：
对于输出PAT的个数，暴力会超时。可以确定一个处于中间位置的A（所谓的中间位置是指，左边和右边都有字母），去计算出这个A的左边的P的个数，以及A的右边的T的个数，那么PAT字符串的个数，就是左边P的个数与右边T的个数的乘积。所以，对于一个已经确定位置的中间的A而言，一共有这么多种PAT，同理，处于中间位置的其他A的对应的PAT的个数也可以这样得出，然后都加在一起，即为最后的答案。
上述过程只是方法论，下面的代码实际的操作不同于上面的思路。具体代码的操作是for循环从左到右的扫描字符串，以leftNump数组去统计这一位及这一位之前的字符串中有P的个数，记录在对应的tempNump[i]中，接着再从右至左的扫描这个字符串，统计右边的T的个数，在扫描的过程中，如果是T就让rightNumt加1，如果是A，就计算对应于这个A的ans，（用对应这个A的leftNump[i]*rightNumt去计算ans），累加各个对应的ans，即为最后的ans.
leftNump数组的使用要总结。
if else-if语句那是更简洁的处理方法，遇到A就计算ans，因为遇到A了，就说明对于这个A的右边的T的个数已经全都数完了。

#include<stdio.h>
#include<string.h>
const int maxn=100010;

const int Mod=1000000007;
int main(){
    int leftNump[maxn]={0};
    char shuru[maxn];
    int a;
    gets(shuru);
    int len=strlen(shuru);
    for(int i=0;i<len;i++){
        if(i>0){//不是非0号位
            leftNump[i]=leftNump[i-1];
        }
        if(shuru[i]=='P'){//如果当前位是p，
            leftNump[i]++;//那么就令leftNump[i]加1
        }
    }
    int ans=0,rightNumt=0;//ans为结果，rightNumt记录右边的T的个数
    for(int i=len-1;i>=0;i--){
        if(shuru[i]=='T'){//如果当前位是T,
            rightNumt++;//那么右边T的个数加1
        }else if(shuru[i]=='A'){//如果当前位是A
            ans=(ans+leftNump[i]*rightNumt)%Mod;//累计乘积
        }
    }
    printf("%d\n",ans);
    return 0;
}

1045 快速排序 (25 分)
题目链接

简单模拟

查找元素

图形输出

进制转换

字符串处理

排序

散列

贪心

二分

two pointers

递推

快排

图形输出

进制转换

排序

散列