PAT甲级训练刷题代码记录

刷题链接：https://www.patest.cn/contests/pat-a-practise

1001

 1 #include <iostream>
 2 #include <stdio.h>
 3 
 4 using namespace std;
 5 int temp[10];
 6 int main()
 7 {
 8     int a,b,sum,index;
 9     while(scanf("%d%d",&a,&b)!=EOF){
10         sum=a+b;
11         if(sum<0){
12             printf("-");
13             sum=-sum;
14         }
15         index=0;
16 
17         while(sum>=1000){
18             temp[index++]=sum%1000;
19             sum=sum/1000;
20         }
21         printf("%d",sum);
22         for(int i = index-1;i >= 0;i--){
23             if(temp[i]>99)
24             printf(",%d",temp[i]);
25         else if(temp[i]>9)
26             printf(",0%d",temp[i]);
27         else
28             printf(",00%d",temp[i]);
29         }
30         printf("
");
31     }
32     return 0;
33 }

1001

数据结构初级入门第一题：https://pta.patest.cn/pta/test/17/exam/4/question/260

 1 #include <iostream>
 2 #include <stdio.h>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int a,h,ans,i,j,temp;char c;
 9     while(scanf("%d %c",&a,&c)!=EOF){
10         for(h=1;a+1>=2*h*h;h++);
11         if(a==0)h=0,ans=0;
12         else ans=a-2*(h-1)*(h-1)+1;
13         h=(h-2)*2+1;
14         //printf("h is %d and ans is %d
",h,ans);
15         //下面开始输出
16         temp=h;
17         for(i=0;i<h;i++){
18             if(i<(h+1)/2){
19                 for(j=0;j<i;j++)printf(" ");
20                 for(j=0;j<h-i*2;j++)printf("%c",c);
21                 printf("
");
22             }else{
23                 for(j=0;j<h-i-1;j++)printf(" ");
24                 for(j=0;j<2*i+2-h;j++)printf("%c",c);
25                 printf("
");
26             }
27         }
28         printf("%d
",ans);
29     }
30     return 0;
31 }

打印沙漏

第二题：思路是素数打表法，请注意做表的时候请将空间开到足够大，否则会出现越界错误。同时相对ACM来说PAT的OJ是有bug的，这也就是说明不管题目你是否会写，请得分，很简单的，至少都有分数的，加油。

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

#define NMAX 100000
int num[NMAX];
int main()
{
    int i,j;
    //思路：采用素数打表法对素数进行处理
    for(i=0;i < NMAX-1;i++){
        num[i]=0;
    }
    for(j=2;j < NMAX-1;j++){
        if(num[j]==0)for(int k =2*j;k<NMAX-1;k=k+j)num[k]=1;
    }
    //上边首先是对表进行初始化

    int n,count;
    while(scanf("%d",&n)!=EOF){
        count=0;
        for(i=2;i<n-1;i++){
            if(num[i]==0&&num[i+2]==0)count++;
        }
        printf("%d
",count);
    }

    return 0;
}

View Code

第三题：佷常见的一个题目，但是要考虑到特殊的数据集的时候，你会发现你以前不严谨的代码错误百出。还好是PAT对于结果会给你一定的提升，请考虑提高数据集的复杂性，将问题考虑全面

#include <iostream>
#include <stdio.h>

using namespace std;
int num[103];

void reserve(int *,int,int);

int main()
{
    int i,n,offset;
    while(scanf("%d%d",&n,&offset)!=EOF){
        if(n==0)continue;
        offset%=n;
        for(i=0;i<n;i++)scanf("%d",&num[i]);
        reserve(num,0,n-offset-1);
        reserve(num,n-offset,n-1);
        reserve(num,0,n-1);

        for(i=0;i<n;i++)
            if(i!=n-1)
        printf("%d ",num[i]);
        else
            printf("%d",num[i]);
        printf("
");
    }
    return 0;
}

void reserve(int *a,int b,int c){
    int temp;
    if(b>=c)return;
    for(int i=b;i <= b+(c-b)/2;i++){
        temp=a[i];
        a[i]=a[c-(i-b)];
        a[c-(i-b)]=temp;
    }
}

View Code

第四题：这个题真的是靠着PAT的提示给整出来的，这个编译器的是好到爆，希望考试要有这样一个效果就好了

这个题目要特别注意！！！进位问题

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
using namespace std;
#define NMAX 100
char num1[NMAX],num2[NMAX];
int demo1[10],demo2[10];

int main()
{
    int i,j,add,count;bool flag;
    while(scanf("%s",num1)!=EOF){
        flag=true;
        for(i=0;i<10;i++)demo1[i]=demo2[i]=0;
        for(i=0;i<strlen(num1);i++)demo1[num1[i]-'0']++;

        add=count=0;
        for(i=strlen(num1)-1;i>=0;i--){
            j=num1[i]-'0';
            j*=2;
            num2[count++]=(j+add)%10+'0';
            add=(j+add)/10;
        }
        if(add!=0)num2[count++]=add%10+'0';
        num2[count]='';
        for(i=0;i<strlen(num2);i++)demo2[num2[i]-'0']++;

        for(i=0;i<10;i++){
            if(demo1[i]!=demo2[i]){
                flag=false;
                break;
            }
        }
        if(flag)printf("Yes
");
        else printf("No
");

        for(i=count-1;i>=0;i--)printf("%c",num2[i]);
        printf("
");

    }
    return 0;
}

View Code

第五题：终于是通关了，这个题目用的最笨的一种方法搞定的。同时也是因为自己没有理解题意，数据量太大，没法调试，卡壳了好久。参考了网上的代码后修改自己的把题目弄出来了。也是，代码这种东西满分不易，且行且珍惜。

#include <iostream>
#include <stdio.h>

using namespace std;
#define MAX 60
#define COUNT 54
int place[MAX];
int temp_num[MAX];
int place_num[MAX];

int main()
{
    int n,temp;
    char* ans[]={
        "TEMP","S1","S2","S3","S4","S5","S6","S7","S8","S9","S10","S11","S12","S13",
        "H1","H2","H3","H4","H5","H6","H7","H8","H9","H10","H11","H12","H13",
        "C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13",
        "D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","D13",
        "J1","J2"};
    while(scanf("%d",&n)!=EOF){
        for(int i =1;i <= COUNT;i++){
            scanf("%d",&temp_num[i]);
            place[i]=place_num[i]=i;
        }

        for(int j=1;j <= n;j++){

            for(int t=1;t<=COUNT;t++){
                place_num[temp_num[t]]=place[t];
            }
            for(int t=1;t<=COUNT;t++){
                place[t]=place_num[t];
            }
        }

        //最后是输出结果

        for(int i = 1;i<=COUNT;i++)
            if(i!=COUNT)printf("%s ",ans[place_num[i]]);
            else printf("%s",ans[place_num[i]]);
        printf("
");
    }

    return 0;
}

View Code

参考代码：

 1 参考代码
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <queue>
 6 #include <cmath>
 7 #include <iostream>
 8 using namespace std;
 9 char f[5]={'S','H','C','D','J'};
10 int main(){
11     //freopen("D:\INPUT.txt","r",stdin);
12     int time;
13     scanf("%d",&time);
14     int card1[55],card2[55],i,j;
15     for(i=0;i<=54;i++){
16         card1[i]=i;
17     }
18     int order[55];
19     for(i=1;i<=54;i++){
20         scanf("%d",&order[i]);
21     }
22     for(i=1;i<=time;i++){
23         for(j=1;j<=54;j++){
24             card2[order[j]]=card1[j];
25         }
26         for(j=1;j<=54;j++){
27             card1[j]=card2[j];
28         }
29     }
30     printf("%c%d",f[(card1[1]-1)/13],card1[1]%13==0?13:card1[1]%13);
31     for(i=2;i<=54;i++){
32         printf(" %c%d",f[(card1[i]-1)/13],card1[i]%13==0?13:card1[i]%13);
33     }
34     printf("
");
35     return 0;
36 }

View Code

牛客网二叉搜索树：https://www.nowcoder.com/practice/3d6dd9a58d5246f29f71683346bb8f1b?tpId=40&tqId=21455&tPage=7&rp=7&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

参考博客：http://www.cnblogs.com/rickhsg/p/3650875.html

自己的题解：

 1 #include <stdio.h>
 2 #include <string>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 
 6 typedef struct Node{
 7     int key;
 8     struct Node *left;
 9     struct Node *right;
10 }Node;
11 ///申请一个树的根节点，并将其初始设置为空
12 Node * Tree=NULL,* p,* temp_p;
13 char tempa[12],tempb[12],temp_str[12];
14 
15 int length,i;
16 ///先将对应的二叉树构造出来
17 void Creat(char* temp){
18         for(i=0;i<strlen(temp);i++){
19                 p=(Node *)malloc(sizeof(Node));
20                 p->key=temp[i]-'0';
21                 p->left=p->right=NULL;
22 
23                 if(Tree==NULL){
24                     Tree=p;
25                 }else{
26                     temp_p=Tree;
27                     while(1){
28                         if(temp_p->key==p->key)break;
29                         else if(temp_p->key<p->key){
30                                 if(temp_p->right==NULL){
31                                     temp_p->right=p;
32                                     break;
33                                 }else
34                                     temp_p=temp_p->right;
35                             }else
36                                 if(temp_p->key>p->key){
37                                     if(temp_p->left==NULL){
38                                     temp_p->left=p;
39                                     break;
40                                 }else
41                                     temp_p=temp_p->left;
42                             }
43                         }
44                     }
45                 }
46 }
47 
48 void pre_order(Node* Tree){
49     ///使用前应当将长度设置为0初始化
50     if(Tree==NULL)return;
51     else{
52         temp_str[length++]=(char)(Tree->key+'0');
53         //printf("+%c",temp_str[length-1]);
54         pre_order(Tree->left);
55         pre_order(Tree->right);
56     }
57 }
58 int main()
59 {
60     int T;
61     while(scanf("%d",&T)!=EOF){
62         if(0==T)break;
63         scanf("%s",tempa);
64         Tree=NULL;
65         ///先将对应的二叉树构造出来
66         Creat(tempa);
67 
68         ///对构造好的排序二叉树进行前序遍历进行唯一性标识
69         length=0;
70         pre_order(Tree);
71         strcpy(tempa,temp_str);
72 
73         ///上边已经将二叉树构造好了，现在只要进行一个判断的工作就ok
74         while(T--){
75             scanf("%s",tempb);
76             Tree=NULL;
77 
78             ///先将对应的二叉树构造出来
79             Creat(tempb);
80 
81         ///对构造好的排序二叉树进行前序遍历进行唯一性标识
82         length=0;
83         pre_order(Tree);
84         strcpy(tempb,temp_str);
85 
86             if(strcmp(tempa,tempb))printf("NO
");
87             else printf("YES
");
88     }
89     }
90     return 0;
91 }

View Code

题解思路：https://www.nowcoder.com/questionTerminal/3d6dd9a58d5246f29f71683346bb8f1b

我要坚持一年，一年后的成功才是我想要的。