C语言-翁恺-PTA-161-207课后练习题-05

Posted on 2024-04-10 Edited on 2024-06-08 In C , PTA

7-161 帅到没朋友

当芸芸众生忙着在朋友圈中发照片的时候，总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。

输入格式：

输入第一行给出一个正整数N（≤100），是已知朋友圈的个数；随后N行，每行首先给出一个正整数K（≤1000），为朋友圈中的人数，然后列出一个朋友圈内的所有人——为方便起见，每人对应一个ID号，为5位数字（从00000到99999），ID间以空格分隔；之后给出一个正整数M（≤10000），为待查询的人数；随后一行中列出M个待查询的ID，以空格分隔。

注意：没有朋友的人可以是根本没安装“朋友圈”，也可以是只有自己一个人在朋友圈的人。虽然有个别自恋狂会自己把自己反复加进朋友圈，但题目保证所有K超过1的朋友圈里都至少有2个不同的人。

输出格式：

按输入的顺序输出那些帅到没朋友的人。ID间用1个空格分隔，行的首尾不得有多余空格。如果没有人太帅，则输出No one is handsome。

注意：同一个人可以被查询多次，但只输出一次。

输入样例1：

3
3 11111 22222 55555
2 33333 44444
4 55555 66666 99999 77777
8
55555 44444 10000 88888 22222 11111 23333 88888

输出样例1：

1	10000 88888 23333

输入样例2：

3
3 11111 22222 55555
2 33333 44444
4 55555 66666 99999 77777
4
55555 44444 22222 11111

输出样例2：

1	No one is handsome

错误原因：

我不清楚，我这个还真不晓得，我哪里错了

看了柳神的代码，才清楚，我错的多离谱，我这个都不晓得，

虽然有个别自恋狂会自己把自己反复加进朋友圈，但题目保证所有K超过1的朋友圈里都至少有2个不同的人

这句话的意思，就是K=1的时候，这个数字是没有用的，这个要注意

错误代码在这里

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int people[1000000] = { 0 };
int main() {
    for (int i = 0; i < 1000000; ++i)   people[i] = 0;
    int n = 0, k = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &k);
        for (int j = 1; j <= k; ++j) {
            int  temp = 0;
            scanf("%d", &temp);
            people[temp] = 1;
        }
    }
    int m = 0,flag=0,judge=0;
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        int temp = 0;
        scanf("%d", &temp);
        if (!people[temp]) {
            if (flag)    printf(" ");
            else flag = 1;
            printf("%05d", temp);
            people[temp] = 1;
            judge = 1;
        }
    }
    if (!judge)  printf("No one is handsome");
    return 0;
}

正确的代码：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int people[1000000] = { 0 };
int main() {
    for (int i = 0; i < 1000000; ++i)   people[i] = 0;
    int n = 0, k = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &k);
        for (int j = 1; j <= k; ++j) {
            int  temp = 0;
            scanf("%d", &temp);
            people[temp] = 1;
        }
    }
    int m = 0,flag=0,judge=0;
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        int temp = 0;
        scanf("%d", &temp);
        if (!people[temp]) {
            if (flag)    printf(" ");
            else flag = 1;
            printf("%05d", temp);
            people[temp] = 1;
            judge = 1;
        }
    }
    if (!judge)  printf("No one is handsome");
    return 0;
}

7-163 谷歌的招聘

2004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌（如下图）用于招聘。内容超级简单，就是一个以 .com 结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步

自然常数 e 是一个著名的超越数，前面若干位写出来是这样的：e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 10 位数就是答案。

本题要求你编程解决一个更通用的问题：从任一给定的长度为 L 的数字中，找出最早出现的 K 位连续数字所组成的素数。

输入格式：

输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和 K（小于 10 的正整数）。接下来一行给出一个长度为 L 的正整数 N。

输出格式：

在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在，则输出 404。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。

输入样例 1：

1 2	20 5 23654987725541023819

输出样例 1：

输入样例 2：

1 2	10 3 2468001680

输出样例 2：

鸣谢用户大冰补充数据！

代码长度限制

16 KB

时间限制

200 ms

内存限制

错误原因

我是傻逼，我

scanf(“%d %d”) 空格都能忘记掉，我确实是有点低能了

正确代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<string.h>
//1就代表是素数，0代表不是
int prime(int n) {
    if (n <2 )    return 0;
    for (int i = 2; i*i<= n ; ++i) {
        if (n % i == 0)  return 0;
    }
    return 1;
}
int main() {
    long long temp = 0;
    int l = 0, k = 0, flag = 0;
    char str[1001];
    char tc[1001];
    scanf("%d %d ", &l, &k);
    scanf("%s", str);
    for (int i = 0; i + k <= l; ++i) {
        strncpy(tc, str + i, k);
        tc[k]='\0';
        if (prime(atoi(tc))) {
            flag = 1;
            printf("%s", tc);
            return 0;
        }
    }
    printf("404");
    return 0;
}

7-175 口罩发放

为了抗击来势汹汹的 COVID19 新型冠状病毒，全国各地均启动了各项措施控制疫情发展，其中一个重要的环节是口罩的发放。

某市出于给市民发放口罩的需要，推出了一款小程序让市民填写信息，方便工作的开展。小程序收集了各种信息，包括市民的姓名、身份证、身体情况、提交时间等，但因为数据量太大，需要根据一定规则进行筛选和处理，请你编写程序，按照给定规则输出口罩的寄送名单。

输入格式:

输入第一行是两个正整数 D 和 P（1≤D,P≤30），表示有 D 天的数据，市民两次获得口罩的时间至少需要间隔 P 天。

接下来 D 块数据，每块给出一天的申请信息。第 i 块数据（i=1,⋯,D）的第一行是两个整数 T**i 和 S**i（1≤T**i,S**i≤1000），表示在第 i 天有 T**i 条申请，总共有 S**i 个口罩发放名额。随后 T**i 行，每行给出一条申请信息，格式如下：

1	姓名身份证号身体情况提交时间

给定数据约束如下：

姓名 是一个长度不超过 10 的不包含空格的非空字符串；
身份证号 是一个长度不超过 20 的非空字符串；
身体情况 是 0 或者 1，0 表示自觉良好，1 表示有相关症状；
提交时间 是 hh:mm，为24小时时间（由 00:00 到 23:59。例如 09:08。）。注意，给定的记录的提交时间不一定有序；
身份证号 各不相同，同一个身份证号被认为是同一个人，数据保证同一个身份证号姓名是相同的。

能发放口罩的记录要求如下：

身份证号 必须是 18 位的数字（可以包含前导0）；
同一个身份证号若在第 i 天申请成功，则接下来的 P 天不能再次申请。也就是说，若第 i 天申请成功，则等到第 i+P+1 天才能再次申请；
在上面两条都符合的情况下，按照提交时间的先后顺序发放，直至全部记录处理完毕或 S**i 个名额用完。如果提交时间相同，则按照在列表中出现的先后顺序决定。

输出格式:

对于每一天的申请记录，每行输出一位得到口罩的人的姓名及身份证号，用一个空格隔开。顺序按照发放顺序确定。

在输出完发放记录后，你还需要输出有合法记录的、身体状况为 1 的申请人的姓名及身份证号，用空格隔开。顺序按照申请记录中出现的顺序确定，同一个人只需要输出一次。

输入样例:

4 2
5 3
A 123456789012345670 1 13:58
B 123456789012345671 0 13:58
C 12345678901234567 0 13:22
D 123456789012345672 0 03:24
C 123456789012345673 0 13:59
4 3
A 123456789012345670 1 13:58
E 123456789012345674 0 13:59
C 123456789012345673 0 13:59
F F 0 14:00
1 3
E 123456789012345674 1 13:58
1 1
A 123456789012345670 0 14:11

输出样例:

D 123456789012345672
A 123456789012345670
B 123456789012345671
E 123456789012345674
C 123456789012345673
A 123456789012345670
A 123456789012345670
E 123456789012345674

样例解释：

输出中，第一行到第三行是第一天的部分；第四、五行是第二天的部分；第三天没有符合要求的市民；第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

这题是我花钱买的，所以我非常的重视：故记录：

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

#define MAX_PEOPLE 1010     // 每天最多申请口罩的人数
#define MAX_MAYBE 30010     // 总共可能有症状的人的最大数量
#define MAX_NAME 11         // 姓名的最大长度
#define MAX_ID 21           // 身份证号的最大长度
#define HASH_SIZE 10007     // 哈希表的大小

// 定义存储每个申请人的信息的结构体
typedef struct {
    char name[MAX_NAME];  // 申请人的姓名
    char id[MAX_ID];      // 申请人的身份证号
    int st;               // 身体状况 (0: 良好, 1: 有症状)
    int h;                // 提交时间的小时部分
    int m;                // 提交时间的分钟部分
    int no;               // 申请人在当天的序号
} People;

// 定义存储可能有症状的人的信息的结构体
typedef struct {
    char name[MAX_NAME];  // 可能有症状的人的姓名
    char id[MAX_ID];      // 可能有症状的人的身份证号
} Maybe;

// 定义存储申请记录的结构体，用于哈希表
typedef struct Record {
    char id[MAX_ID];      // 申请人的身份证号
    int day;              // 最后一次领取口罩的天数
    struct Record *next;  // 指向下一个记录的指针
} Record;

People people[MAX_PEOPLE];      // 存储每天申请人的信息
Maybe maybe[MAX_MAYBE];         // 存储所有可能有症状的人的信息
Record *hash_table[HASH_SIZE];  // 哈希表，用于快速查找申请记录
int idx = 0;                    // 记录可能有症状的人的数量

// 比较函数，用于qsort对申请人按时间和序号进行排序
int compare_people(const void *a, const void *b) {
    People *pa = (People *)a;
    People *pb = (People *)b;
    // 先按小时排序
    if (pa->h != pb->h) return pa->h - pb->h;
    // 小时相同则按分钟排序
    if (pa->m != pb->m) return pa->m - pb->m;
    // 时间相同则按当天的序号排序
    return pa->no - pb->no;
}

// 检查身份证号是否有效，必须为18位且全为数字
bool check(const char *id) {
    if (strlen(id) != 18) return false;
    for (int i = 0; i < 18; i++) {
        if (id[i] < '0' || id[i] > '9') return false;
    }
    return true;
}

// 将时间字符串转换为小时和分钟
void convert(int *h, int *m, const char *str) {
    sscanf(str, "%d:%d", h, m);
}

// 哈希函数，将字符串转换为哈希值
unsigned int hash(const char *str) {
    unsigned int hash = 0;
    while (*str) {
        hash = (hash * 31) + *str++;
    }
    return hash % HASH_SIZE;
}

// 在哈希表中查找记录
Record* find_record(const char *id) {
    unsigned int index = hash(id);
    Record *entry = hash_table[index];
    while (entry != NULL) {
        if (strcmp(entry->id, id) == 0) {
            return entry;
        }
        entry = entry->next;
    }
    return NULL;
}

// 向哈希表中插入记录
void insert_record(const char *id, int day) {
    unsigned int index = hash(id);
    Record *entry = (Record *)malloc(sizeof(Record));
    strcpy(entry->id, id);
    entry->day = day;
    entry->next = hash_table[index];
    hash_table[index] = entry;
}

// 清空哈希表，释放内存
void clear_records() {
    for (int i = 0; i < HASH_SIZE; i++) {
        Record *entry = hash_table[i];
        while (entry != NULL) {
            Record *temp = entry;
            entry = entry->next;
            free(temp);
        }
        hash_table[i] = NULL;
    }
}

int main() {
    int d = 0, p = 0;
    // 读取天数d和最少间隔天数p
    scanf("%d %d", &d, &p);

    // 处理每一天的数据
    for (int i = 1; i <= d; i++) {
        int n = 0, cnt = 0;
        // 读取当天申请人数n和可发放口罩的数量cnt
        scanf("%d %d", &n, &cnt);
        int k = 0;

        // 读取每个申请人的信息
        for (int j = 0; j < n; j++) {
            char name[MAX_NAME], id[MAX_ID], str[10];
            int h = 0, m = 0, st = 0;
            // 读取申请人的姓名、身份证号、身体状况和提交时间
            scanf("%s %s %d %s", name, id, &st, str);
            // 将时间字符串转换为小时和分钟
            convert(&h, &m, str);
            // 检查身份证号是否有效
            if (check(id)) {
                // 将有效申请人的信息存储到people数组中
                strcpy(people[k].name, name);
                strcpy(people[k].id, id);
                people[k].st = st;
                people[k].h = h;
                people[k].m = m;
                people[k].no = j;
                k++;
                // 如果有症状，将信息存储到maybe数组中
                if (st) {
                    strcpy(maybe[idx].name, name);
                    strcpy(maybe[idx].id, id);
                    idx++;
                }
            }
        }

        // 按提交时间和顺序对申请人进行排序
        qsort(people, k, sizeof(People), compare_people);

        // 发放口罩
        for (int j = 0; j < k && cnt > 0; j++) {
            Record *record = find_record(people[j].id);
            // 检查是否符合发放条件
            if (record == NULL || i >= record->day + p + 1) {
                // 打印领取口罩的人的姓名和身份证号
                printf("%s %s\n", people[j].name, people[j].id);
                if (record == NULL) {
                    insert_record(people[j].id, i);
                } else {
                    record->day = i;
                }
                cnt--;
            }
        }
    }

    // 输出可能有症状的人的信息，去重
    for (int j = 0; j < idx; j++) {
        Record *record = find_record(maybe[j].id);
        if (record == NULL || record->day != d + 1) {
            // 打印可能有症状的人的姓名和身份证号
            printf("%s %s\n", maybe[j].name, maybe[j].id);
            if (record == NULL) {
                insert_record(maybe[j].id, d + 1);
            } else {
                record->day = d + 1;
            }
        }
    }

    // 清空记录，释放内存
    clear_records();
    return 0;
}

这是我花了钱的，日了狗的

7-186 前世档案

分数 20

作者陈越

单位浙江大学

网络世界中时常会遇到这类滑稽的算命小程序，实现原理很简单，随便设计几个问题，根据玩家对每个问题的回答选择一条判断树中的路径（如下图所示），结论就是路径终点对应的那个结点。

现在我们把结论从左到右顺序编号，编号从 1 开始。这里假设回答都是简单的“是”或“否”，又假设回答“是”对应向左的路径，回答“否”对应向右的路径。给定玩家的一系列回答，请你返回其得到的结论的编号。

输入格式：

输入第一行给出两个正整数：N（≤30）为玩家做一次测试要回答的问题数量；M（≤100）为玩家人数。

随后 M 行，每行顺次给出玩家的 N 个回答。这里用 y 代表“是”，用 n 代表“否”。

输出格式：

对每个玩家，在一行中输出其对应的结论的编号。

输入样例：

3 4
yny
nyy
nyn
yyn

输出样例：

大佬的思路
地址

我要使用小黄鸭方法来分析这道题目。首先按照题目要求输入玩家做一次测试要回答的问题数量和玩家人数。然后针对每一个玩家输入其N个回答，显然的是，这些回答构成了一颗二叉树，题目要求输出其对应的结论的编号，也就是二叉树的叶子结点的编号（从左往右依次是1、2、3……）。以某玩家为例，假设他的回答是“yny”，那么可以理解为对应二进制代码010，转换为十进制数是2。由于叶子结点是从1开始编号，所以十进制数需要加1，最终结果是3。

别人的正确的代码如下：

#include <stdio.h>
#include <math.h>
int main()
{
    // input
    int n, m; scanf("%d%d", &n, &m);
    for (int i=0; i<m; i++){
        // 读走换行符
        getchar();
        // input + process
        // 叶子结点从1开始编号
        int sum = 1;
        for (int j=0; j<n; j++){
            char ch = getchar();
            if (ch == 'n')
              sum += pow(2, n-1-j); // 计数
        }
        // output
        printf("%d\n", sum);
    }
    return 0;
}