PAT – ADVANCED – 20POINTS (UPDATING)

进制转换类

常用 除余法

A1001 取进制各位

思路1 %10得末位数，/10前移一位，由此得到逆序各位数
思路2 分段输出左对齐补0，$\scriptsize [10^6]=n/1000000,[10^3,10^6]=n/1000 \mod 1000,[0,10^3]=n \mod 1000$

int main()
{
    vector<char> v;
    int a, b;
    scanf("%d %d", &a, &b);

    a += b;
    if(a < 0) { putchar('-'); a = -a; }
    if(a == 0) v.push_back('0');

    for(int i = 1; a; i++) {
        v.push_back('0' + a % 10);
        a /= 10;
        if(a && i % 3 == 0) v.push_back(',');
    }

    for(int i = v.size() - 1; i >= 0; i--)
        putchar(v[i]);
    putchar('n');
    return 0;
}

A1005 取进制各位、大整数字符串存储

注意0特殊情况输出的是”zero”

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string chn[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    vector<int> v;
    int sum = 0, i;
    char s[101];

    scanf("%s", s);
    for (int i = 0; s[i]; i++)
        sum += s[i] - '0';

    while (sum) {
        v.push_back(sum % 10);
        sum /= 10;
    }

    for (i = v.size() - 1; i > 0; i--)
        printf("%s ", chn[v[i]].c_str());

    if(i == -1) printf("zeron");
    else printf("%sn", chn[v[0]].c_str());

    return 0;
}

A1008 记录循环旧值

每次循环记录旧值pre，可迭代入新一轮计算cur

#include <iostream>
using namespace std;

int main() {
    int N, pre = 0, cur;
    long long sum = 0;
    scanf("%d", &N);

    while (N--) {
        scanf("%d", &cur);
        if (cur >= pre) sum += 6 * (cur - pre) + 5;
        else sum += 4 * (pre - cur) + 5;
        pre = cur;
    }

    printf("%lldn", sum);

    return 0;
}

A1011 求取最大值

无需开O(n)数组记录，仅需一个变量迭乘

#include <iostream>
using namespace std;

int main() {
    double m, num, r = 1.0;
    char n[] = {'W', 'T', 'L'};
    int id;

    for(int i = 0; i < 3; i++) {
        m = __DBL_MIN__;
        for(int j = 0; j < 3; j++) {
            scanf("%lf", &num);
            if(m < num) {
                id = j;
                m = num;
            }
        }
        r *= m;
        printf("%c ", n[id]);
    }

    printf("%.2fn", (0.65 * r - 1) * 2);

    return 0;
}

A1015 素数判断、进制转换

大端k进制数取得：先余k后除k即可得到
判断质数：问题规模 $\scriptsize \lt 10^5$，逐项除余即可
输入格式：先满足第一个数合法，再读入另一个数计算

#include <iostream>
using namespace std;

int toReverseDecimal(int n, int r) {
    int num = 0;
    while (n) {
        num = num * r + n % r;
        n /= r;
    }
    return num;
}

bool isPrime(int N) {
    if(N < 2) return false;
    for (int i = 2; i * i <= N; i++)
        if (N % i == 0) return false;
    return true;
}

int main() {
    int N, D;
    while (~scanf("%d", &N)) {
        if (N < 0) break;
        scanf("%d", &D);
        if (isPrime(N)) {
            N = toReverseDecimal(N, D);
            if (isPrime(N)) printf("Yesn");
            else printf("Non");
        }
        else printf("Non");
    }
    return 0;
}

A1019 进制转换、双指针

注意细节：指针累加记录至末尾时多一，访问末尾索引需减一

#include <iostream>
using namespace std;

int main() {
    int num[31];
    bool isP = true;
    int t = 0, h = 0, t1;
    long long N, b;
    scanf("%lld%lld", &N, &b);

    while (N) {
        num[t++] = N % b;
        N /= b;
    }

    t -= 1;
    t1 = t;
    while (h < t)
        if (num[h++] != num[t--])
            isP = false;

    if (isP)        printf("Yesn");
    else            printf("Non");
    while (t1 > 0)  printf("%d ", num[t1--]);
    printf("%dn", num[0]);

    return 0;
}

A1027 进制转换

本题仅有两位，先除后余，无需倒序处理

#include <iostream>
using namespace std;

char R[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C'};

int main() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    putchar('#');
    printf("%c%c", R[a / 13], R[a % 13]);
    printf("%c%c", R[b / 13], R[b % 13]);
    printf("%c%c", R[c / 13], R[c % 13]);
    return 0;
}

A1058 变进制数

此题注意自身叠加运算导致某数改变，后续重用该数时已不是原值，应使用中间变量保存结果

#include<iostream>
using namespace std;

int main() {
    int ga, sa, ka;
    int gb, sb, kb;
    int of;
    scanf("%d.%d.%d %d.%d.%d", &ga, &sa, &ka, &gb, &sb, &kb);
    of = (ka + kb) / 29;
    ka = (ka + kb) % 29;

    kb = sa + sb + of;
    sa = kb % 17;
    of = kb / 17;

    ga = ga + gb + of;

    printf("%d.%d.%d", ga, sa, ka);
    return 0;
}

大整数运算

采用 字符串读入，逐位运算
常见 竖式计算模拟，记录借位进位即可

A1023 乘法模拟

乘法模拟：从低位到高位逐位乘并累加进位
进位处理：注意最高位进位会导致长度增加
正确性验证：原始各位数字计数num与结果各位数字num[r[i]]计数比对

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char s[21];
    scanf("%s", s);
    int num[10] = {0}, r[21] = {0};
    int i, j = 0, len = strlen(s);

    for(i = len - 1; i >= 0; i--) {
        int id = s[i] - '0';
        int db = id << 1;

        r[j] += db;
        if(r[j] >= 10) r[j] -= 10;
        r[j + 1] = (db >= 10);

        num[id]++;
        num[r[j]]--;
        j++;
    }

    if(r[j])  num[r[j]]--;
    else      j--;
    i = j;

    for(; j >= 0; j--)
        if(num[r[j]]) {
            printf("Non");
            break;
        }
    if(j == -1)     printf("Yesn");
    while(i >= 0)   printf("%d", r[i--]);
}

图形输出

图形输出题主要是寻找序号与输出之间的规律

A1031 找规律、双指针

枚举发现规律：图形高度h = (l + 2) / 3，中央空格数m = l – 2 * h;
对称输出：输出{s[i]，s[n-i-1]}，或用双指针法{s[i++],s[j–]}

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int h, m, l, i, j;
    char s[81];
    scanf("%s", s);

    l = strlen(s);
    h = (l + 2) / 3;
    m = l - 2 * h;

    for (i = 0, j = l - 1; i <= j; i++, j--) {
        if (h > 1) {
            putchar(s[i]);
            for (int k = 0; k < m; k++)
                putchar(' ');
            h--;
            putchar(s[j]);
            putchar('n');
        }
        else while(i <= j) putchar(s[i++]);
    }
    return 0;
}

哈希散列

主要是stl::unordered_map的使用

A1035 哈希表存取

判断并修改：遍历字符串使用哈希表查找替换
修改个数计数：初始num=0，每一字符串判断发生修改++num即为修改个数
输出结果集：若修改下次读入pswd[++num]，若未修改下次覆盖读入pswd[num]，结果集范围[0,num-1]

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    char user[1000][11], pswd[1000][11], cur;
    unordered_map<char, char> map;
    int total, i, add, num = 0;
    map['0'] = '%';
    map['O'] = 'o';
    map['1'] = '@';
    map['l'] = 'L';

    scanf("%d", &total);

    while (~scanf("%s %s", user[num], pswd[num])) {
        i = 0; add = 0;
        while (pswd[num][i]) {
            cur = pswd[num][i];
            if (map.find(cur) != map.end()) {
                pswd[num][i] = map[cur];
                add = 1;
            }
            i++;
        }
        num += add;
    }

    if (num > 0) {
        printf("%dn", num);
        for (int j = 0; j < num; j++)   printf("%s %sn", user[j], pswd[j]);
    }
    else if (total == 1)    printf("There is 1 account and no account is modifiedn");
    else                    printf("There are %d accounts and no account is modifiedn", total);

    return 0;
}

A1041 散列计数

题意理解：筛出的是只出现一次，且按输入序首次出现的数字
保存输入序：按输入序检索需按序保存数字个数N，最大1e5+1
哈希表大小：数字范围[1,1e4]，需开1e4+1

#include <iostream>
using namespace std;

int main() {
    int map[10001] = {0}, num[100001] = {0};
    int N, i;
    scanf("%d", &N);

    for (i = 0; i < N; i++) {
        scanf("%d", &num[i]);
        map[num[i]]++;
    }

    for (i = 0; i < N; i++) {
        if (map[num[i]] == 1) {
            printf("%dn", num[i]);
            return 0;
        }
    }
    printf("Nonen");

    return 0;
}

A1050 散列去重

#include <iostream>
using namespace std;
int main() {
    int i = -1, s2[128] = {0};
    char s1[10001], c;

    while ((c = getchar()) != 'n') s1[++i] = c;
    s1[++i] = '';

    while ((c = getchar()) != 'n') s2[c]++;
    i = -1;

    while (s1[++i]) if (!s2[s1[i]]) putchar(s1[i]);
    putchar('n');
    return 0;
}

字符串处理

scanf读入整行时可能以空格为分隔符，改为cstio::gets()或逐字符读取
逐字符读取时要在读取末尾手动添加”标明字符串结束，以防未初始化数组随机值影响

循环结构

A1061 循环细节

①不满足条件而继续循环，条件应置于循环内部，否则将直接退出循环
②区分break在条件分支内和分支后
③此题较坑的部分是隐含范围”MON-SUN”对应的范围为”A-G”

#include <iostream>
using namespace std;

int main() {
    char s1[61], s2[61], s3[61], s4[61];
    char *day[7] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
    int i;
    scanf("%s%s%s%s", s1, s2, s3, s4);

    for (i = 0; s1[i] && s2[i]; i++)
        if (s1[i] == s2[i] && s1[i] >= 'A' && s1[i] <= 'G')
            break;
    printf("%s ", day[s1[i] - 'A']);

    for (++i; s1[i] && s2[i]; i++)
        if (s1[i] == s2[i]) {
            if (s1[i] >= 'A' && s1[i] <= 'N')      printf("%02d:", s1[i] - 'A' + 10);
            else if (s1[i] >= '0' && s1[i] <= '9') printf("%02d:", s1[i] - '0');
            else continue;
            break;
        }

    for (i = 0; s3[i] && s4[i]; i++)
        if (s3[i] == s4[i] && ((s3[i] >= 'a' && s3[i] <= 'z') || (s3[i] >= 'A' && s3[i] <= 'Z')))
            break;#include <iostream>
using namespace std;

    int main() {
        int t = 1;
        bool isAbove = false;
        long long a, b, c, r;
        while (getchar() != 'n') ;
        while (~scanf("%lld%lld%lld", &a, &b, &c)) {
            r = a + b;
            if (a > 0 && b > 0 && r < 0) isAbove = true;
            else if (a < 0 && b < 0 && r >= 0) isAbove = false;
            else if (r > c) isAbove = true;
            else isAbove = false;

            if (isAbove) printf("Case #%d: truen", t);
            else printf("Case #%d: falsen", t);
            t++;
        }

        return 0;
    }
    printf("%02dn", i);

    return 0;
}

类型边界

A1065 超限处理

①特殊处理超范围情况，其余正常判断
long long 类型表示范围 $\scriptsize [-2^{63},2^{63}-1]$
上限溢出时 $\scriptsize a+b \in [2^{63},2^{64}-2]$，计算结果 $\scriptsize \% 64 = [-2^{63},-2]$
下限溢出时 $\scriptsize a+b \in [-2^{64},-2^{63}-1]$，计算结果 $\scriptsize \% 64 = [-2^{63}-1,0]$
②用字符串模拟竖式加减法，并比较结果

#include <iostream>
using namespace std;

int main() {
    int t = 1;
    bool isAbove = false;
    long long a, b, c, r;
    while (getchar() != 'n') ;
    while (~scanf("%lld%lld%lld", &a, &b, &c)) {
        r = a + b;
        if (a > 0 && b > 0 && r < 0) isAbove = true;
        else if (a < 0 && b < 0 && r >= 0) isAbove = false;
        else if (r > c) isAbove = true;
        else isAbove = false;

        if (isAbove) printf("Case #%d: truen", t);
        else printf("Case #%d: falsen", t);
        t++;
    }

    return 0;
}