PAT甲級題目（純C語言）

記一下刷題過程和思路，部落客是個菜鳥，隻有C語言用的順，如果有不足之處歡迎大家指正。

PAT甲級題目目錄

- 1001
- 1002
- 1003
- 1004
- 1005
- 1006
- 1007
- 1008
- 1009
- 1010
- 1011

1001

1001 A+B Format (20分)

Calculate a+b and output the sum in standard format – that is, the digits must be separated into groups of three by commas (unless there are less than four digits).

Input Specification:

Each input file contains one test case. Each case contains a pair of integers a and b where −10^6 ≤a,b≤ 10^6

. The numbers are separated by a space.

Output Specification:

For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.

思路：這道題由于a，b的範圍有限，于是選擇一種簡單粗暴的做法。

#include <stdio.h>
#include <math.h>
int main()
{
    int a,b,c,d[10],i=0;
    scanf("%d %d",&a,&b);
    c=a+b;
    if(c<0)
    {
        c=-c;
        printf("-");
    }
    if(c>=1000000)printf("%d,%03d,%03d\n",c/1000000, (c/1000)%1000, c%1000);
    else if(c>=1000) printf("%d,%03d\n",c/1000, c%1000);
    else printf("%d\n",c);
    return 0;
}

1002

1002 A+B for Polynomials (25分)

This time, you are supposed to find A+B where A and B are two polynomials.

思路：這道題我按照自己的思路做時，是類似于有序表的合并思路做的，不知道為什麼總是通過不了，在網上看到了别人的思路，覺得很好，可以把指數作為數組下标來存儲系數，這樣不容易出錯，還很清晰。

#include <stdio.h>
int main()
{
    int k1,k2,m,c=0;
    float n,a[1001]={0};
    int i,j;
    scanf("%d",&k1);
    for(i=0;i<k1;i++)
    {
        scanf(" %d %f",&m,&n);
        a[m]+=n;
    }
    scanf("%d",&k2);
    for(j=0;j<k2;j++)
    {
        scanf(" %d %f",&m,&n);
        a[m]+=n;
    }
    for(i=1000;i>=0;i--)
    {
        if(a[i]!=0) c++;
    }
    printf("%d",c);
    for(i=1000;i>=0;i--)
    {
        if(a[i]!=0)printf(" %d %.1f",i,a[i]);
    }
}

1003

1003 Emergency (25分)

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

思路：這道題我用迪傑斯特拉算法來做，思路還是挺清晰的，主要是三個循環：初始化、找到k、更新距離。有一個坑是這道題和迪傑斯特拉算法有一點不同是在初始化時起點C1的判斷是否走過的flag[C1]不要初始化為1，因為有多條最短路徑時還可以經過它。

#include <stdio.h>
#define max 505
#define INF 10000;
typedef struct
{
    int t;
}vex;

typedef struct
{
    int m[max][max];
    int vnum;
    int edgenum;
    vex v[max];
}graph;

void dijkstra(graph g,int c1,int c2,int n)
{
    int i,j,k,min,flag[n],dist[n],prev[n],temp,s[n],tnum[n];//s[i]是從起點到i節點的最短路徑條數，tnum[i]是能到達i、節點的隊伍總數
    for(i=0;i<n;i++)
    {
        flag[i]=0;
        prev[i]=0;
        dist[i]=g.m[c1][i];
        s[i]=0;
        tnum[i]=0;
    }
    dist[c1]=0;
    s[c1]=1;
    tnum[c1]=g.v[c1].t;
    for(i=0;i<n;i++)
    {
        k=-1;
        min=INF;
        for(j=0;j<n;j++)
        {
            if(flag[j]==0&&dist[j]<min)
            {
                min=dist[j];
                k=j;
            }

        }

        flag[k]=1;
        prev[k]=c1;
        for(j=0;j<n;j++)
        {
            temp=dist[k]+g.m[k][j];
            if(flag[j]==0&&temp<dist[j])
            {
                dist[j]=temp;
                prev[j]=k;
                s[j]=s[k];
                tnum[j]=g.v[j].t+tnum[k];
            }
            else if(flag[j]==0&&temp==dist[j])//有多條最短路徑的情況
            {
                s[j]+=s[k];
                tnum[j]=(g.v[j].t+tnum[k]>tnum[j]? g.v[j].t+tnum[k]:tnum[j]);
            }
        }
    }
    printf("%d %d",s[c2],tnum[c2]);
}

int main()
{
    int n,m,c1,c2;
    scanf("%d %d %d %d",&n,&m,&c1,&c2);
    graph g;
    g.vnum=n;
    g.edgenum=m;
    int i,j,t1,t2,t3;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            g.m[i][j]=INF;
        }
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",&g.v[i].t);
    }
    for(i=0;i<m;i++)
    {
        scanf("%d %d %d",&t1,&t2,&t3);
        g.m[t1][t2]=t3;
        g.m[t2][t1]=t3;
    }
    g.m[c1][c1]=0;
    dijkstra(g,c1,c2,n);
    return 0;
}

1004

1004 Counting Leaves (30分)

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

思路：這道題我看網上有人用層級周遊什麼的感覺有點想複雜了，其實隻要用到樹結構的存儲就可以了。有一個坑是在輸入時不能直接讓子節點的層數是父節點的層數+1，因為在沒有輸入完時可能還不知道父節點的層數，會導緻有兩個測試點不能通過。隻要在輸入時記錄每個節點的父節點即可，在輸入完成後再進行子節點的層數是父節點的層數+1。

#include <stdio.h>
#define max 200
typedef struct
{
    int id,level,flag,father;//flag用來判斷該節點是否為非葉子節點
}node;

typedef struct
{
    node nodes[max];
}tree;

int main()
{
    int n,m,i,j,t1,t2,t3,max_level=0,r[max]={0};
    tree t;
    scanf("%d %d",&n,&m);
    t.nodes[1].level=1;
    t.nodes[1].id=1;
    t.nodes[1].father=0;
    for(i=1;i<=n;i++)
    {
        t.nodes[i].flag=0;
    }
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&t1,&t2);
        t.nodes[t1].id=t1;
        t.nodes[t1].flag=1;
        for(j=0;j<t2;j++)
        {
            scanf("%d",&t3);
            t.nodes[t3].id=t3;
            t.nodes[t3].father=t1;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(t.nodes[j].father==i)
            {
                t.nodes[j].level=t.nodes[i].level+1;
                if(t.nodes[j].level>max_level)max_level=t.nodes[j].level;
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(t.nodes[i].flag==0)
        {
            r[t.nodes[i].level]++;//r[i]用來記錄第i層的葉子節點數目
        }
    }
    for(i=1;i<max_level;i++)
    {
        printf("%d ",r[i]);
    }
    printf("%d",r[i]);
}

1005

1005 Spell It Right (20分)

Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.

思路：這道題比較簡單，沒啥好說的。。。

#include <stdio.h>
#define max 150
int main()
{
    char n[max],d[10][10]={"zero","one","two","three","four","five","six","seven","eight","nine"};
    scanf("%s",n);
    int i,j,r[max],sum=0;
    for(i=0;n[i];i++)
    {
        sum+=n[i]-'0';
    }
    if(sum==0)
    {
        printf("zero");
        return 0;
    }
    for(i=0;sum;i++)
    {
        r[i]=sum%10;
        sum/=10;
    }
    i--;
    for(;i>0;i--)printf("%s ",d[r[i]]);
    printf("%s",d[r[i]]);
}

1006

1006 Sign In and Sign Out (25分)

At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.

思路：這道題也比較簡單，找出sign in的時間最小的和sign out的時間最大的就行。

#include <stdio.h>
#include <string.h>
#define max 100
typedef struct
{
    int h,m,s;
}time;

typedef struct
{
    char id[20];
    time in,out;
}person;

int main()
{
    int i,n;
    char min_id[20],max_id[20];
    scanf("%d",&n);
    time tmin={24,60,60};
    time tmax={0,0,0};
    person p[max];
    for(i=0;i<n;i++)
    {
        scanf("%s %d:%d:%d %d:%d:%d",p[i].id,&p[i].in.h,&p[i].in.m,&p[i].in.s,&p[i].out.h,&p[i].out.m,&p[i].out.s);
        if(p[i].in.h<tmin.h || (p[i].in.h==tmin.h&&p[i].in.m<tmin.m) || (p[i].in.h==tmin.h&&p[i].in.m==tmin.m&&p[i].in.s<tmin.s))
        {
            tmin=p[i].in;
            strcpy(min_id,p[i].id);
        }
        if(p[i].out.h>tmax.h || (p[i].out.h==tmax.h&&p[i].out.m>tmax.m) || (p[i].out.h==tmax.h&&p[i].out.m==tmax.m&&p[i].out.s>tmax.s))
        {
            tmax=p[i].out;
            strcpy(max_id,p[i].id);
        }
    }
    printf("%s %s",min_id,max_id);
    return 0;
}

1007

1007 Maximum Subsequence Sum (25分)

思路：s和e分别記錄目前子序列的起始點和終止點，t為目前子序列的和。從頭開始周遊，若t<0，則舍棄目前子序列，從下一個位置繼續尋找。

#include <stdio.h>
int main()
{
    int k,n[10001],i,j;
    scanf("%d",&k);
    for(i=0;i<k;i++)
    {
        scanf("%d",&n[i]);
    }
    int t=0,max=-1,s=0,e=k-1,p=0;
    for(i=0;i<k;i++)
    {
        t+=n[i];
        if(t<0)
        {
            t=0;
            p=i+1;
        }
        else if(t>max)
        {
            max=t;
            s=p;
            e=i;
        }
    }
    if(max<0)
    {
        printf("0 %d %d",n[0],n[k-1]);
    }
    else
    {
        printf("%d %d %d",max,n[s],n[e]);
    }
    return 0;
}

1008

1008 Elevator (20分)

The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.

For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.

思路：這題很簡單，了解題意就能做。

#include <stdio.h>
int main()
{
    int n,a[110],i,t,s=0;
    scanf("%d",&n);
    a[0]=0;
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        t=a[i]-a[i-1];
        if(t>0)
        {
            s+=t*6+5;
        }
        else
        {
            s+=(-t)*4+5;
        }
    }
    printf("%d",s);
}

1009

1009 Product of Polynomials (25分)

This time, you are supposed to find A×B where A and B are two polynomials.

思路：和之前的多項式加法思路比較相似，用數組下标記錄指數，數組元素記錄系數。

#include <stdio.h>
int main()
{
    int k1,k2,i,j,t1,maxn=0;
    float a[1005]={0},b[1005]={0},c[2005]={0},t2;
    scanf("%d",&k1);
    for(i=0;i<k1;i++)
    {
        scanf("%d %f",&t1,&t2);
        a[t1]=t2;
    }
    scanf("%d",&k2);
    for(i=0;i<k2;i++)
    {
        scanf("%d %f",&t1,&t2);
        b[t1]=t2;
    }
    for(i=0;i<1005;i++)
    {
        for(j=0;j<1005;j++)
        {
            c[i+j]+=a[i]*b[j];
        }
    }
    for(i=2005;i>=0;i--)
    {
        if(c[i]!=0.0)maxn++;
    }
    printf("%d",maxn);
    for(i=2005;i>=0;i--)
    {
        if(c[i]!=0.0)printf(" %d %.1f",i,c[i]);
    }
    return 0;
}

1010

010 Radix (25分)

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N1 and N2，your task is to find the radix of one number while that of the other is given.

思路：這道題的坑比較多，我的這個代碼目前還有兩個測試點沒有通過。

1.最大進制數很大，絕對不止36，要用long long int。

2.不能用順序周遊一個個嘗試可能的進制，這樣的話會運作逾時，需要使用二分法尋找進制。二分法查找進制的下界是未知進制數的最大數字 +1，因為每一位的數字都不能超過進制數，比如十進制的數字就隻能是 0-9，不可能會有 abcd。二分法查找進制的上界是已知進制數的數值。

3.當尋找的可能進制有多個的時候，需要找到最小的那個。

#include <stdio.h>
#include <string.h>
#include <math.h>
int main()
{
    char n1[600],n2[600],c[600];
    long long int radix,e=0,t=0,max_num=0,temp,i,j;
    int tag;
    scanf("%s %s %d %d",n1,n2,&tag,&radix);
    if(tag==2)
    {
        strcpy(c,n1);
        strcpy(n1,n2);
        strcpy(n2,c);
    }

        for(i=0;i<strlen(n2);i++)
        {
            if('0'<=n2[i]&&n2[i]<='9')
            {
                temp=(n2[i]-'0');
                if(temp>max_num)max_num=temp;
            }
            else if('a'<=n2[i]&&n2[i]<='z')
            {
                temp=(n2[i]-'a'+10);
                if(temp>max_num)max_num=temp;
            }
        }

        for(i=0;i<strlen(n1);i++)
        {
            if('0'<=n1[i]&&n1[i]<='9')
            {
                temp=(n1[i]-'0');
                e+=temp*pow(radix,strlen(n1)-1-i);
            }
            else if('a'<=n1[i]&&n1[i]<='z')
            {
                temp=(n1[i]-'a'+10);
                e+=temp*pow(radix,strlen(n1)-1-i);
            }
        }
        for(j=max_num+1;j<=e;j++)
        {
            t=0;
            for(i=0;i<strlen(n2);i++)
            {
                if('0'<=n2[i]&&n2[i]<='9')
                {
                    t+=(n2[i]-'0')*pow(j,strlen(n2)-1-i);
                }
                else if('a'<=n2[i]&&n2[i]<='z')
                {
                    t+=(n2[i]-'a'+10)*pow(j,strlen(n2)-1-i);
                }
            }
            if(t==e)
            {
                printf("%d",j);
                return 0;
            }
        }

    printf("Impossible");
    return 0;
}

1011

1011 World Cup Betting (20分)

With the 2010 FIFA World Cup running, football fans the world over were becoming increasingly excited as the best players from the best teams doing battles for the World Cup trophy in South Africa. Similarly, football betting fans were putting their money where their mouths were, by laying all manner of World Cup bets.

思路：這道題比較簡單，了解題意後代公式就行。

#include <stdio.h>
int main()
{
    float g[3][3],max=0.0,r=1.0;
    int i,j,k;
    char c[3]={'W','T','L'};
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            scanf("%f",&g[i][j]);
        }
    }
    for(i=0;i<3;i++)
    {
        max=0.0;
        for(j=0;j<3;j++)
        {
            if(g[i][j]>max)
            {
                max=g[i][j];
                k=j;
            }
        }
        printf("%c ",c[k]);
        r*=g[i][k];
    }
    printf("%.2f",(r*0.65-1)*2);
    return 0;
}

PAT甲級題目（純C語言）

PAT甲級題目目錄

1001

1002

1003

1004

1005

1006

1007

1008

1009

1010

1011

繼續閱讀

C語言-----初階指針詳解

輸出蛇形矩陣 C語言輸出蛇形矩陣

1.54寸TFT ST7789液晶屏圖檔如何取模

三子棋——年輕人的第一款小遊戲前言正文總結

DOG（4）：解析器的部分實作細節先來說說parser一些可能迷惑的地方結果如何傳回?pcd其實是一回事最後的一點說明

NYOJ 269--VF

二叉樹三種周遊(先序，中序，後序)----超詳細引入先序周遊後序周遊中序周遊總結

UVA 110 Meta-Loopless Sorts

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

結構體：typedef與struct的差別

hdu7108哈希