PAT乙级题解91-110

91

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m,n,k;
    scanf("%d",&m);
    for(int i=0;i<m;i++){                   //读取数字
        scanf("%d",&k);
        int temp,check;
        for(n=1;n<10;n++){
            temp=check=n*k*k;               //计算乘积
            if(temp%10==k) break;           //由于给出的数不超过1000，所有只有三位，直接判断取余判断即可
            else if(temp%100==k) break;
            else if(temp%1000==k) break; 
        }
        if(n==10) printf("No\n");           //如果没有遇到对应的K则输出no
        else printf("%d %d\n",n,temp);
    }
    return 0;
}

92

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m,n,max=0;
    scanf("%d %d",&n,&m);                   //读入参数
    int cnt[n+1]={0};                       //需要g++支持
    for(int i=0;i<m;i++){
        for(int j=1;j<=n;j++){
            int num;
            scanf("%d",&num);
            cnt[j]+=num;                    //累加每种月饼的销量
            max=cnt[j]>max?cnt[j]:max;
        }
    }
    int flag=0;                             //用于格式控制
    printf("%d\n",max);
    for(int i=1;i<=n;i++){
        if(cnt[i]==max){                    //从小到大的序号遍历，输出销量等于最高销量的月饼序号
            if(flag++) putchar(' ');
            printf("%d",i);
        }
    }
    return 0;
}

93

#include<bits/stdc++.h>
using namespace std;
int main(){
    int Table[127]={0};                     //用于记录是否已经出现过当前字符
    int cnt=0;                              //用于统计出现回车的次数，用于结束循环
    while(cnt<2){
        char ch=getchar();                  //读取字符
        if(ch=='\n') { cnt++;continue; }    //回车字符直接跳过
        if(Table[ch]==0){                   //如果没出现过，记录该字符并输出
            Table[ch]++;
            putchar(ch);
        }
    }
    return 0;
}
//题目样例可知大小写不同

94

#include<bits/stdc++.h>
using namespace std;
bool IsPrime(int x){
    if(x==0||x==1) return false;
    for(int i=2;i<sqrt(1.0*x);i++)
        if(x%i==0) return false;
    return true;
}
int main(){
    string str;
    int len,k;
    scanf("%d %d\n",&len,&k);
    cin>>str;
    for(int i=0;i+k<=len;i++){          //注意循环边界
        string num=str.substr(i,k);     //去除当前位置开始向后的k个字符
        if(IsPrime(stoi(num))){         //转化成数字并验证是不是素数，如果是则输出并返回
            cout<<num; return 0;
        }
    }
    cout<<"404";                        //如果找不到符合条件的素数，则输出404
    return 0;
}

95

#include<bits/stdc++.h>
using namespace std;
typedef struct{                                         //学生结构体
    string id;
    int score;
}ST;
bool cmp(ST a,ST b){                                    //排序规则
     if(a.score!=b.score) return a.score>b.score;
     else return a.id<b.id;
}
int main(void){
    int  n,m,case_tp;                                   //case_tp表示查验类型
    string temp,day,room;                               //临时变量，时间，考场
    cin>>n>>m;
    vector<ST> v(n),ans;                                //v用于存储数据，ans用于存放答案
    for(int i=0;i<n;i++)
        cin>>v[i].id>>v[i].score;                       //读入原始数据
    for(int i=1;i<=m;i++){                              //进行查验
        int cnt=0;                                      //用于输出个数
        cin>>case_tp>>temp;                             //读入查验类型和查验参数
        cout<<"Case "<<i<<": "<<case_tp<<' '<<temp<<'\n';
        ans.clear();                                    //初始化ans数组
        if(case_tp==1){                                 //第一种类型
            for(int j=0;j<n;j++)                        //找到同一个级别的考生放入输出的数组中
                if(v[j].id[0]==temp[0])    ans.push_back(v[j]);
            sort(ans.begin(),ans.end(),cmp);            //按照要求排序并输出
            for(int j=0;j<ans.size();j++){
                cout<<ans[j].id<<' '<<ans[j].score<<'\n';
                cnt++;
            }
        }
        else if(case_tp==2){                            //第二种类型
            int sum=0,num=0;                            //用于统计总人数和总分分数
            for(int j=0;j<n;j++){
                room=v[j].id.substr(1,3);               //遍历原始数据获取每个考生的考场号
                if(room==temp){                         //如果和查验的考场号相同，则累计人数和总分
                    num++;
                    sum+=v[j].score;
                }    
            }
            if(num) {printf("%d %d\n",num,sum);cnt++;}  //当人数不为0时，输出并把标记cnt+1
        }
        else{
            unordered_map<string,int> mp;               //创建考场和人数的对应关系
            for(int j=0;j<n;j++){                       //遍历数据，获取考试日期和考场号
                day=v[j].id.substr(4,6);
                room=v[j].id.substr(1,3);
                if(day==temp)                           //对应考场的人数统计+1
                    mp[room]++;
            }
            ST t;                                       //这里发现如果把人数放在学生分数位置，考场号放在准考证号位置，两者排序规则相同，所以用于借用
            for(auto it=mp.begin();it!=mp.end();it++){  //把考场号和人数组成结构体放入输出的数组中
                t.id=it->first;    t.score=it->second;
                ans.push_back(t);
            }
            sort(ans.begin(),ans.end(),cmp);            //按照要求排序后输出
            for(int j=0;j<ans.size();j++){
                cout<<ans[j].id<<' '<<ans[j].score<<'\n';
                cnt++;
            }
        }
        if(cnt==0) puts("NA");                          //如果当前类型没有输出，则查询结果为空，输出NA
    }
    return 0;
 }

96

#include<bits/stdc++.h>
using namespace std;
bool judge(int x){
    //计算因数
    vector<int> factor;
    for (int i = 1; i <= x; i++){
        if (x % i == 0)
            factor.push_back(i);
    }
    //四个数字之和是x的倍数，读题，整除和被整除不一样 a整除b应该是b%a==0
    int size = factor.size();   //至少有四个因子
    if(size >= 4){
        for (int i = 0; i < size; i++){
            for (int j = i + 1; j < size; j++){
                for (int m = j + 1; m < size; m++){
                    for (int n = m + 1; n < size; n++){
                        if ((factor[i] + factor[j] + factor[m] + factor[n]) % x == 0)
                            return true;
                    }
                }
            }
        }
    }
    return false;
}
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        if (temp <= 5)
            cout << "No\n";
        else
            cout << (judge(temp) ? "Yes\n" : "No\n");
    }
    return 0;
}

97

#include<bits/stdc++.h>
using namespace std;
int main(){ 
    int n,k,x;
    cin >> n >> k >> x;
    vector<int> ans(n,0);
    for (int i = 0; i < n; i++){
        int offset = (i % 2 == 0) ? ((i / 2) % k + 1) : 0;  //计算偏移量，奇数行下标为偶数，偶数行需要偏移，奇数不偏移
        for (int j = 0; j < n; j++){
            int temp;
            cin >> temp;
            if (offset == 0)                                //如果不偏移，则对应列相加
                ans[j] += temp;
            else{
                if (j + offset < n)                         //累加到偏移的列
                    ans[j + offset] += temp;  
                if (j < offset)                             //累加填充列
                    ans[j] += x;
            }
        }
    }
    for (int i = 0; i < n; i++){                            //输出结果
        if(i) putchar(' ');
        cout << ans[i];
    }
    return 0;
}

98

#include<bits/stdc++.h>
using namespace std;
int main(){ 
    int n;
    vector<int> up, down;
    cin >> n;
    up.resize(n);
    down.resize(n);
    for (int i = 0; i < n; i++){
        cin >> up[i];
    }
    for (int i = 0; i < n; i++){
        cin >> down[i];
    }
    int up_bound = *min_element(up.begin(), up.end());
    int down_bound = *max_element(down.begin(), down.end());
    if (up_bound > down_bound)
        cout << "Yes " << up_bound - down_bound;
    else
        cout << "No " << down_bound - up_bound + 1;
    return 0;
}

99

#include<bits/stdc++.h>
using namespace std;

bool isPrime(int n){
    if (n <= 1)         //判断0和1
        return false;
    int sqr = int(sqrt(1.0 * n));
    for (int i = 2; i <= sqr; i++){
        if (n % i == 0)
            return false;
    }
    return true;
}
bool isSexPrime(int n){
    int pre = n > 6 ? n - 6 : 0;
    int next = n + 6;
    return isPrime(n) && (isPrime(pre) || isPrime(next));
}
int main(){
    int n;
    cin >> n;
    if (isSexPrime(n)){
        puts("Yes");
        int pre = n > 6 ? n - 6 : 0;
        int next = n + 6;
        cout << (isPrime(pre) ? pre : next);
    }
    else{
        puts("No");
        while(n++){
            if(isSexPrime(n))
                break;
        }
        cout << n;
    }
    return 0;
}

100

#include<bits/stdc++.h>
using namespace std;
int main(){
    unordered_set<string> uset;
    int n;
    int maxGuest = 99999999;
    int maxAlumni = 99999999;
    cin >> n;
    string str, strGuest, strAlumni;
    for (int i = 0; i < n; i++){
        cin >> str;
        uset.insert(str);
    }
    cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; i++){
        cin >> str;
        int year = stoi(str.substr(6, 8));
        //保存校友的最大年龄
        if (uset.find(str) != uset.end())
        {
            cnt++;
            if (year < maxAlumni){
                strAlumni = str;
                maxAlumni = year;
            }
        }//保存访客中非校友的最大年龄
        else{
            if (year < maxGuest){
                strGuest = str;
                maxGuest = year;
            }
        }
    }
    cout << cnt << endl;
    cout << (cnt == 0 ? strGuest : strAlumni);
    return 0;
}

101

#include <bits/stdc++.h>
using namespace std;
int main() {
    string num;
    int n, num1, num2, size;
    cin >> num >> n;
    size = num.size();
    string tmp = num.substr(size - n, n) + num.substr(0, size - n);
    printf("%.2lf", stod(tmp) / stod(num));
    return 0;
}

102

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    string id, maxCountID, maxSalesID;
    int count, price;
    int maxSales = -1;
    int maxCount = -1;
    for (int i = 0; i < n; i++) {
        cin >> id >> price >> count;
        int tmp = price * count;
        if (tmp > maxSales) {
            maxSales = tmp;
            maxSalesID = id;
        }
        if (count > maxCount) {
            maxCount = count;
            maxCountID = id;
        }
    }
    cout << maxCountID << " " << maxCount << endl;
    cout << maxSalesID << " " << maxSales << endl;
    return 0;
}

103

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int low, high, count = 0;
    cin >> low >> high;
    if (low == 1)                               // 1特判  1 和 0的立方差是1，不是另一个数字
        low++;
    for (int i = low; i <= high; i++) {
        ll tmp = 3 * i * (i - 1) + 1;           //化简结果
        int bound = int(pow(tmp / 4.0, 0.25));
        for (int j = bound + 1; j >= 1; j--) {
            ll target = j * j + (j - 1) * (j - 1);
            if (tmp == target * target) {
                cout << i << " " << j << endl;
                count++;
                break;
            }
        }
    }
    if (count == 0)
        cout << "No Solution";
    return 0;
}

104

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE = 100;
bool PRIMER[MAXSIZE];
//分析最后一位是1-8
//最后一位是9
//最后两位是99  这些情况gcd的值，可以发现规律，之后最后两位是99的才符合条件
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
void getPrimerTable() {
    fill(PRIMER, PRIMER + MAXSIZE, true);
    for (int i = 2; i < MAXSIZE; i++) {
        if (PRIMER[i]) {
            for (int j = i + i; j < MAXSIZE; j += i) PRIMER[j] = false;
        }
    }
    PRIMER[0] = PRIMER[1] = PRIMER[2] = false;
}
int digitSum(ll n) {
    int sum = 0;
    while (n) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
void processData(int k, int m) {
    //需要排序
    set<pair<int, int>> result;
    int cnt = 0;
    for (ll i = 99 + pow(10, k - 1); i <= pow(10, k) - 1; i += 100) {
        int digit_sum_i = digitSum(i);
        int digit_sum_i1 = digitSum(i + 1);
        if (digit_sum_i == m && PRIMER[gcd(m, digit_sum_i1)]) {
            result.insert(pair<int, int>{digit_sum_i1, i});
            cnt++;
        }
    }
    if (cnt == 0)
        cout << "No Solution" << endl;
    else {
        for (auto item : result) {
            cout << item.first << " " << item.second << endl;
        }
    }
}
int main() {
    getPrimerTable();
    int n, k, m;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "Case " << i + 1 << endl;
        cin >> k >> m;
        processData(k, m);
    }
    return 0;
}

105

#include <bits/stdc++.h>
using namespace std;
//链表节点
struct node {
    int val, next;
    node(int _val = -1, int _next = -1) : val(_val), next(_next) {}
};
//用于存放链表
node Data[100001];
//读取链表长度
int getLen(int head) {
    int len = 0;
    while (head != -1) {
        len++;
        head = Data[head].next;
    }
    return len;
}
//链表逆置，返回新的头节点指针
int reverseList(int head) {
    int newHead = 100000;
    while (head != -1) {
        int next = Data[head].next;
        Data[head].next = Data[newHead].next;
        Data[newHead].next = head;
        head = next;
    }
    return Data[newHead].next;
}
int main() {
    int head1, head2, n;
    cin >> head1 >> head2 >> n;
    int id, val, next;
    for (int i = 0; i < n; i++) {
        cin >> id >> val >> next;
        Data[id] = node(val, next);
    }
    int len1 = getLen(head1);
    int len2 = getLen(head2);
    if (len1 < len2)  //保证head1为长的链表
        swap(head1, head2);
    head2 = reverseList(head2);
    int p = head1;
    int cnt = 1;
    while (head2 != -1) {
        if (cnt % 2 == 0) {
            //保存后续链表
            int list1_next = Data[p].next;
            int list2_next = Data[head2].next;
            //勾链
            Data[p].next = head2;
            Data[head2].next = list1_next;
            //更新p和head2
            p = list1_next;
            head2 = list2_next;
        } else {
            p = Data[p].next;
        }
        cnt++;
    }
    //输出，最后一个链表节点单独处理
    cnt = 0;
    while (Data[head1].next != -1) {
        if (cnt)
            putchar(' ');
        printf("%05d %d %05d\n", head1, Data[head1].val, Data[head1].next);
        head1 = Data[head1].next;
    }
    printf("%05d %d -1", head1, Data[head1].val);
    return 0;
}

106

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    vector<int> ans = {2, 0, 1, 9};
    cin >> n;
    for (int i = 4; i < n; i++) {
        ans.push_back(accumulate(ans.end() - 4, ans.end(), 0) % 10);
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i];
    }
    return 0;
}

107

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int champion = 0, group_champion = 0;
    for (int i = 0; i < n; i++) {
        group_champion = 0;
        for (int j = 0; j < m; j++) {
            int tmp;
            cin >> tmp;
            group_champion = max(group_champion, tmp);
        }
        if (i)
            putchar(' ');
        cout << group_champion;
        champion = max(champion, group_champion);
    }
    cout << '\n'
         << champion;
    return 0;
}

108

#include <bits/stdc++.h>
using namespace std;
int main() {
    string str;
    string word = "String";
    cin >> str;
    unordered_map<char, int> ump;
    for (char ch : str) {
        if (word.find(ch) != string::npos)
            ump[ch]++;
    }
    while (!ump.empty()) {
        for (char ch : word) {
            if (ump.count(ch)) {
                putchar(ch);
                if (--ump[ch] == 0)
                    ump.erase(ch);
            }
        }
    }
    return 0;
}

109

#include <bits/stdc++.h>
using namespace std;
vector<string> words[26];                       //存放单词的打印矩阵
void printWord(string word) {                   //打印一个单词
    static int cnt = 0;                         //用于控制格式的计数器
    if (cnt)
        putchar('\n');
    for (int i = 0; i < 7; i++) {               //每个单词输出7行
        string line;
        for (int j = 0; j < word.size(); j++) { //遍历整个单词，填充当前行每个位置的内容
            if (j)
                line += ' ';
            int index = word[j] - 'A';
            line += words[index][i];
        }
        cout << line << endl;                   //每一行都需要换行
    }
    cnt++;
}
int main() {
    for (int i = 0; i < 26; i++) {             //读入单词的打印矩阵
        for (int j = 0; j < 7; j++) {
            string tmp;
            getline(cin, tmp);
            words[i].push_back(tmp);
        }
    }
    char ch;
    string word;
    while ((ch = getchar()) != '\n') {          //遍历所有的单词
        if (ch >= 'A' && ch <= 'Z') {
            word.push_back(ch);
        } else {
            if (word.size()) {                  //如果获取了一个单词那么就打印一个
                printWord(word);                //打印结束后清空单词
                word.clear();
            }
        }
    }
    if (word.size())                            //最后结尾可能还会有一个单词
        printWord(word);
    return 0;
}

110

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef struct node {                               //结点定义
    int id, data, next;
} Node;
Node all[MAXN];
int main() {
    int head, n, k;
    scanf("%d%d%d", &head, &n, &k);                 //读入头指针，结点个数，和k
    vector<Node> v;                                 //存放链表结点的数组
    for (int i = 0; i < n; i++) {                   //读入所有结点
        int id;
        scanf("%d", &id);
        scanf("%d%d", &all[id].data, &all[id].next);
        all[id].id = id;                            //自己的id需要保存下来，方便最后的输出
    }
    for (int i = head; i != -1; i = all[i].next) {  //读取一遍链表，过滤多余结点
        v.push_back(all[i]);
    }
    n = v.size();                                   //更新n为实际的结点个数
    int i;
    for (i = 0; i < n / k; i++)                     //每k个逆置
        reverse(v.begin() + i * k, v.begin() + (i + 1) * k);
    reverse(v.begin() + i * k, v.end());            //尾巴不足k个做特殊处理
    reverse(v.begin(), v.end());                    //将整个表逆置
    for (i = 0; i < n - 1; i++)                     //输出结果，next就是后一个结点的id
        printf("%05d %d %05d\n", v[i].id, v[i].data, v[i + 1].id);
    printf("%05d %d -1", v[i].id, v[i].data);       //最后一个特殊处理，尾指针-1
    return 0;
}