PAT（乙级）2022年夏季考试 C语言AC代码

考试的时候最后一题没能AC，尝试重新做一下。

7-1 又是一道 A+B 分数 15

本题仍然是给出两个正整数 A 和 B，请你输出 A+B 的值。

只不过，A 和 B 是用发光二极管（LED）来显示的 —— 我们用 7 根 LED 段来显示一个数字，各段编号如图所示。当某一段管子被点亮的时候，我们将对应的位置状态标记为 1，否则为 0。例如数字 3 就会被表示为 1110011，即第 1、2、3、6、7 段是亮的，第 4、5 段是不亮的。当一个数字由多位数组成时，我们从左向右表示每一位，例如 24 会被表示为 1110110 0101011。

输入格式：

输入分为 2 行，分别给出 A 和 B 的 LED 表示。这里 A 和 B 都是固定的 5 位数，不足位的数字补齐前导 0。

输出格式：

输出 A+B 的值。

输入样例：

0000011 1111001 1111101 1011111 1110011
1000011 1011111 1111111 1111011 1011111

输出样例：

86493

样例说明：

A 等于 15603，B 等于 70890，所以输出 15603+70890 = 86493。

思路：

将输入的LED代码转化为数字然后求出A、B，最后输出和。 

#include
#include
char code[10][8]={"1011111","0000011","1110110","1110011","0101011","1111001","1111101","1000011","1111111","1111011"};
int main(void){
    int A=0,B=0;
    char input[8];
    for(int i=0;i<5;i++){//求A
        scanf("%s",input);
        for(int j=0;j<10;j++){
            if(strcmp(input,code[j])==0){
                A=A*10+j;
                break;
            }
        }
    }
    for(int i=0;i<5;i++){//求B
        scanf("%s",input);
        for(int j=0;j<10;j++){
            if(strcmp(input,code[j])==0){
                B=B*10+j;
                break;
            }
        }
    }
    printf("%d",A+B);
    return 0;
}

7-2 健身达人 分数 20

百腾非常重视小伙伴们的身体健康，要求每人每周至少健身打卡 3 次。最近姥姥想搞一场“健身达人”大赛，要求大家每天上报自己的健身运动量。每天运动量最大的那个人将获得“今日达人”奖；一周总运动量最大、并且运动了至少 3 天的那个人获得“本周达人”奖。

现在百腾只有十几人的规模，小拼姐姐人工就可以完成信息收集和评选了。但是如果有上万人呢…… 就需要请你写个程序来统计数据并给出达人名单了。

输入格式：

输入第一行给出一个不超过 104 的正整数 N，为员工总数。随后 N 行，每行给出一位员工的一周打卡信息，格式如下：

工号 周一运动量 周二运动量 …… 周日运动量

其中工号由 6 位阿拉伯数字组成，每天的运动量如果是 0 则表示没打卡，否则是一个不超过 104 的正整数。

输出格式：

首先输出每天的“今日达人”奖获得者，格式如下：

Star X
工号1
工号2
……

其中 X 是数字 1 到 7，顺序代表周一到周日；下面的每个工号是当天运动量最大的人，如果有并列，就按他们在输入中出现的顺序输出。如果那天一个人都没有，则在应该输出工号的位置输出 NONE。

最后输出“本周达人”奖得主，格式如下：

Star of the week
工号1
工号2
……

每个工号是一周总运动量最大、并且运动了至少 3 天的人，如果有并列，就按他们在输入中出现的顺序输出。题目保证至少有一个人（搞学长）会坚持打卡至少 3 次。

输入样例：

5
123456 123 0 233 0 1024 0 0
000101 666 7456 0 0 0 0 0
200789 10 0 0 2 0 122 0
987654 1024 233 0 0 120 3 0
981045 0 0 0 0 0 122 0

输出样例：

Star 1
987654
Star 2
000101
Star 3
123456
Star 4
200789
Star 5
123456
Star 6
200789
981045
Star 7
NONE
Star of the week
123456
987654

思路：

用一个结构体存放各项输入，每次输入更新最大值，最后输出满足条件的id。 

#include
typedef struct{
    int id,val[7],sum,flag;
}Staff;
int main(void){
    int N,max[7]={0},max_sum=0;
    Staff s[10000];
    scanf("%d",&N);
    memset(s,0,sizeof(s));
    
    for(int i=0;i0) s[i].flag++;//统计运动天数
            if(max[j]2&&s[i].sum>max_sum) max_sum=s[i].sum;//更新每周运动量最大值
    }
    for(int i=0;i<7;i++){//输出每天之星
        printf("Star %dn",i+1);
        if(max[i]==0){
            printf("NONEn");
        }else for(int j=0;j2) printf("%06dn",s[i].id);
    }
    return 0;
}

7-3 阶乘方程 分数 20 

已知存在无穷多组整数 0≤a 输入格式：

输入第一行首先给出一个正整数 N≤100，随后 N 行，每行给出一个有序递增的非负整数四元组，格式为：a b c d，其中 d 不超过 109，并且 a 与 b 之间、c 与 d 之间间隔均不超过 104。

输出格式：

对每个输入的四元组，判断其是否阶乘方程的解。若是则在一行中输出 YES，否则输出 NO。

输入样例：

6
0 6 7 10
18 22 54 57
7 14 62 68
300 302 90901 90902
350 680 920 1560
1 11 39916799 39916800

输出样例：

YES
YES
NO
YES
NO
YES

 思路：

暴力法，用一个浮点值存放结果，从方程一边把另一边所有值依次除掉，最后如果结果接近1则正确。

顺便一提，考试时的精度要求没有这么高，应该是修改过数据了。

#include
int main(void){
    int N,a,b,c,d;
    double res;
    scanf("%d",&N);
    for(int i=0;ic;d--,b--){//d!/c!每项中除掉b!/a!的每项
            res=res*(1.0*d/b);
        }
        for(;b>a;b--){//b!/a!一定比d!/c!更多项，所以接着除完
            res/=b;
        }
        if(res>0.999999999&&res<1.000000001) printf("YESn");
        else printf("NOn");
    }
    return 0;
}

7-4 今天是周几  分数 20

韩梅梅和李雷在吵吵今天是周几，他们的对话如下：

韩梅梅：今天是周五。
李雷：不对！今天是周六。
韩梅梅：但昨天是周三呀。
李雷：不可能！昨天是周四。
韩梅梅：那明天是周二了吧。
李雷：搞笑吗？明天是周一。

他俩的妈妈告诉你，每个熊孩子都只说对了一句话，就请你判断一下，今天到底是周几？

输入格式：

输入包含 2 行，每行给出一个熊孩子的声明，格式如下：

昨天 今天 明天

这里的日期是 0 到 6 的整数，依次对应周日到周六。

输出格式：

首先第一行输出“今天”是周几，要求输出其英文名称（对照表在样例之后给出）。输入保证每个熊孩子都只说对了一句话，“今天”的答案存在并且是唯一的。

随后 2 行依次打印出每个熊孩子答对的那天 —— 是昨天就输出 yesterday，或者是今天要输出 today，或者是明天要输出 tomorrow。

输入样例：

3 5 2
4 6 1

输出样例：

Friday
today
yesterday

注意： 日期的英文名称对照如下

周日：0 - Sunday
周一：1 - Monday
周二：2 - Tuesday
周三：3 - Wednesday
周四：4 - Thursday
周五：5 - Friday
周六：6 - Saturday

 思路：

遍历一周七天，假设该日期是今天（或昨天），当两人都只说对了一次时跳出循环，该日期就是真实的日期。

#include
char date[7][15]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
char istrue[3][10]={"yesterday","today","tomorrow"};
int main(void){
    int real[3],A[3],B[3],cnt1=0,cnt2=0;
    for(int i=0;i<3;i++) scanf("%d",&A[i]);
    for(int i=0;i<3;i++) scanf("%d",&B[i]);
    for(int i=0;i<7;i++){
        cnt1=0; cnt2=0;
        for(int j=0;j<3;j++){
            real[j]=(i+j)%7;
            if(real[j]==A[j]) cnt1++;
            if(real[j]==B[j]) cnt2++;
        }
        if(cnt1==cnt2&&cnt1==1) break;
    }
    printf("%sn",date[real[1]]);
    for(int i=0;i<3;i++){
        if(A[i]==real[i]) printf("%sn",istrue[i]);
    }
    for(int i=0;i<3;i++){
        if(B[i]==real[i]) printf("%sn",istrue[i]);
    }
}

 7-5 LRU缓存 分数 25

LRU 全称为 Least Recently Used，即“最近最少使用”。LRU 缓存机制是指，当缓存满了，而缓存区外面的一个新数据被调用的时候，将缓存中最近最少使用（即最长时间没有被使用过）的数据清除，为新数据开辟出空间。

你的任务就是实现这种 LRU 缓存机制。

输入格式：

输入第一行给出两个正整数 N (≤104) 和 M (≤105)，分别为缓存区的大小和被调用的数据的数量。随后一行给出 M 个被调用的数据的编号。编号为区间 [1,2×104] 内的一个整数。一行中的数字以空格分隔。

输出格式：

在一行中顺序输出被从缓存中删除的数据的编号。数据间以 1 个空格分隔，行首尾不得有多余空格。

题目保证至少有 1 个数据会被删除。

输入样例：

4 11
1 2 3 1 4 5 2 1 5 6 3

输出样例：

2 3 4 2

样例说明：

当数据 1、2、3 顺次到来时，它们都被直接放入缓存，此时 1 号数据是 LRU 数据。

当 1 号数据被调用时，2 号数据成为 LRU 数据。

4 号数据还是能放入缓存的，此时缓存区满了。所以当 5 号数据要进入缓存时，2 号被删除，3 号成为 LRU 数据。

随后 2 号数据又被调用了，此时删除 3 号数据，同时 1 号数据成为 LRU 数据。

随后 1 号数据被调用了，于是 4 号数据成为了 LRU 数据。

当 5 号数据再次被调用时，LRU 数据没有改变。随后 6 号进入，4 号被删除。现在 LRU 数据是 2 号。

最后，当 3 号 进入的时候，2 号被删除。

思路：

考试时一时没有好的解决办法，使用了暴力遍历，果然有一个测试点超时。 后来想了想链表可以比较方便地完成插入和删除操作。

用两个指针分别指向表头和表尾。头结点的下一个节点开始存放数据，每次新的输入在表尾加入，则链表中第二个节点是最早进入的。用一个数组存放数据对应的节点地址，若链表中已存在该数据，则将它原本节点删除后在表尾重新加入。

但是如果是需要删除表尾节点的情况，会导致表尾指针丢失，所以增加了两个特判的条件。

#include
#include
typedef struct CacheNode{
int data;
struct CacheNode *pre,*next;
}CacheNode;
void removenode(CacheNode *p);
CacheNode *newnode(int data,CacheNode *tail);
int main(void){
	int N,M,cnt=0,sflag=0;
    long isused[(int)2e4+10];
	CacheNode *head=(CacheNode *)malloc(sizeof(CacheNode));
	CacheNode *tail=head;
	head->pre=NULL;
	head->next=NULL;
	head->data=-1;
	memset(isused,-1,sizeof(isused));
	scanf("%d%d",&N,&M);
	for(int i=0,temp;inext->data);
			isused[head->next->data]=-1;
			removenode(head->next);
			tail=newnode(temp,tail);
			isused[temp]=(long)tail;
		}else if(cnt==N&&cnt==1){//此时tail一定是最后一个节点，不作删除
            if(sflag++) printf(" ");
			printf("%d",head->next->data);
			isused[head->next->data]=-1;
            tail->data=temp;
            isused[temp]=(long)tail;
        }
	}
	return 0;
}
void removenode(CacheNode *p){
	p->pre->next=p->next;
    p->next->pre=p->pre;
	free(p);
}
CacheNode * newnode(int data,CacheNode *tail){
	CacheNode *new=(CacheNode *)malloc(sizeof(CacheNode));
	tail->next=new;
	new->pre=tail;
	new->next=NULL;
	new->data=data;
	return new;
}