PAT – BASIC – 20POINTS[updating]

持续更新中

1002 大整数的字符串存储

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

int main()
{
    char n[100];
    vector<string> v;
    string num[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
    while (~scanf("%s", &n)) {

        int sum = 0;
        for (int i = 0; i < strlen(n); i++)
            sum += n[i] - '0';

        while (sum != 0) {
            v.push_back(num[sum % 10].c_str());
            sum /= 10;
        }

        for (int i = v.size() - 1; i >= 0 ; i--) {
            printf("%s", v[i].c_str());
            if(i == 0) printf("\n");
            else printf(" ");
        }
    }

    return 0;
}

1004 字符数组预留、结构体赋值

#include <iostream>
using namespace std;

struct Stu
{
    char name[11];
    char snum[11];
    int grade;
} maxStu, minStu, tmpStu;

int main()
{
    maxStu.grade = -1;
    minStu.grade = 101;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%s%s%d", tmpStu.name, tmpStu.snum, &tmpStu.grade);
        if (tmpStu.grade > maxStu.grade) maxStu = tmpStu;
        if (tmpStu.grade < minStu.grade) minStu = tmpStu;
    }
    printf("%s %s\n", maxStu.name, maxStu.snum);
    printf("%s %s\n", minStu.name, minStu.snum);
    return 0;
}

1007 线性素数筛注意是否取上界

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

const int maxn = 100000;
bool isPrime[maxn];
int a[maxn];

int main() {
    int n, j = 1, compsite;
    memset(isPrime, true, sizeof(isPrime));
    scanf("%d", &n);

    for(int N = 2; N <= n; N++) {
        if(isPrime[N]) a[j++] = N;
        for(int i = 1; i < j; i++) {
            if((compsite = a[i] * N) > n) break;
            isPrime[compsite] = false;
            if(N % a[i] == 0) break;
        }
    }

    int cnt = 0;
    for(int i = 2; i < j; i++)
        if(a[i] - a[i - 1] == 2)
            cnt++;
    printf("%d", cnt);

    return 0;
}

1008 循环移动数组的三种方法、最小公倍数

直接从 $\scriptsize a[N – M ]$ 开始循环输出，或使用辅助数组

# include <iostream>
using namespace std;

int main() {
    int N, M, T, j;
    scanf("%d%d", &N, &M);
    int a[N];
    M = M % N;
    for(int i = 0; i < N; i++)         scanf("%d", &a[i]);
    for(int i = N - M; i < N; i++)     printf("%d ", a[i]);
    for(int i = 0; i < N - M - 1; i++) printf("%d ", a[i]);
    printf("%d", a[N - M - 1]);
    return 0;
}

三次翻转法

环形替换法

1009 循环读入、逆序输出

注意自增在循环条件中时会多计算一次

#include <iostream>
using namespace std;

int main() {
    char s[80][80];
    int i = 0;
    while(~scanf("%s", s[i])) i++;

    for(int j = i - 1; j > 0; j--)
        printf("%s ", s[j]);
    printf("%s\n", s[0]);

    return 0;
}

1012 注意交错为0，不同类型运算转换

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

int main() {
    int A[6];
    memset(A, 0, sizeof(A));
    int n, a, b = 0;
    float num = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a);
        switch(a % 5) {
            case 0: A[1] += a % 2 ? 0: a;            break;
            case 1: b = (b==1 ? -1: 1); A[2] += a*b; break;
            case 2: A[3] ++;                         break;
            case 3: A[4] += a; num++;                break;
            case 4: A[5] = A[5] > a ? A[5] : a;      break;
        }
    }
    if(A[1]) printf("%d ", A[1]);               else printf("N ");
    if(b)    printf("%d ", A[2]);               else printf("N ");
    if(A[3]) printf("%d ", A[3]);               else printf("N ");
    if(A[4]) printf("%.1f ", A[4] / num);       else printf("N ");
    if(A[5]) printf("%d",  A[5]);               else printf("N");
    return 0;
}

1013 线性素数筛、注意数组是否够容纳上界

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

const int maxn = 110000;
bool isPrime[maxn];
int a[10001];

int main()
{
    int m, n, composite, count = 1, cnt = 1;
    scanf("%d%d", &m, &n);
    memset(isPrime, true, sizeof(isPrime));

    for (int i = 2; cnt <= n; i++) {
        if (isPrime[i]) a[cnt++] = i;
        for (int j = 1; j < cnt; j++) {
            if ((composite = a[j] * i) >= maxn) break;
            isPrime[composite] = false;
            if (i % a[j] == 0) break;
        }
    }

    for (int i = m; i <= n; i++) {
        if (count++ % 10 == 0 || i == n) printf("%d\n", a[i]);
        else printf("%d ", a[i]);
    }

    return 0;
}

1014 指针遍历法、分段模拟、隐含输入限定

避免过多数组下标操作计算，防止计算繁复和频繁读写

复杂模拟尽量分段实现，避免耦合和代码难理解

注意隐含输入限制，星期范围、数字和字母、以及字母大小写

#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    char day[7][4] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
    char s0[61], s1[61], s2[61], s3[61];
    int d = 0, h, m = 0;
    scanf("%s%s%s%s", s0, s1, s2, s3);

    while (s0[d] && s1[d]) {
        if (s0[d] == s1[d] && s0[d] >= 'A' && s0[d] <= 'G')
            break;
        d++;
    }

    h = d + 1;
    while (s0[h] && s1[h]) {
        if (s0[h] == s1[h]) {
            if (s0[h] >= 'A' && s0[h] <= 'N') {
                h = s0[h] - 'A' + 10;
                break;
            }
            else if (s0[h] >= '0' && s0[h] <= '9') {
                h = s0[h] - '0';
                break;
            }
        }
        h++;
    }

    while (s2[m] && s3[m]) {
        if (s2[m] == s3[m])
            if (s2[m] >= 'a' && s2[m] <= 'z' || s2[m] >= 'A' && s2[m] <= 'Z')
                break;
        m++;
    }

    printf("%s %02d:%02d", day[s0[d] - 'A'], h, m);

    return 0;
}

1017 竖式除法模拟、注意0处理

#include <iostream>
using namespace std;

int main()
{
    char s[1001], *p = s;
    int n, d = 0;
    scanf("%s%d", s, &n);
    for (int i = 0; s[i]; i++)
    {
        d = d * 10 + s[i] - '0';
        s[i] = d / n + '0';
        d %= n;
    }
    if(p[0] == '0' && p[1]) p++;
    printf("%s %d", p, d);
    return 0;
}

1019 sort用法

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

int main() {
    int s[4], t[4];
    int sNum, tNum;
    scanf("%d", &tNum);
    sNum = tNum;

    while(true)
    {
        s[0] = sNum / 1000;
        s[1] = sNum % 1000 / 100;
        s[2] = sNum % 100 / 10;
        s[3] = sNum % 10;

        sort(s, s + 4);
        for(int i = 0; i < 4; i++)
            t[i] = s[3 - i];

        tNum = t[3] + 10 * t[2] + 100 * t[1] + 1000 * t[0];
        sNum = s[3] + 10 * s[2] + 100 * s[1] + 1000 * s[0];
        printf("%04d - %04d = ", tNum, sNum);
        if(tNum == sNum) { printf("%04d\n", 0); break; }
        printf("%04d\n", tNum -= sNum);
        if(tNum == 6174) break;
        sNum = tNum;
    }
    return 0;
}

1022 进制转换除k取余法

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

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

    while(a != 0) {
        v.push_back(a % d);
        a /= d;
    }

    if(v.size())
        for(int i = v.size() - 1; i >= 0; i--)
            printf("%d", v[i]);
    else printf("0");

    return 0;
}

1023 边遍历边处理

更简洁的解法来自于 @OliverLew ，预先取0，并在之后的输入中检测一次性输出0，一边读入一边输出，O(1)内存有被惊艳到

#include <iostream>
using namespace std;

int main() {
    int num[10], start = 10;
    for (int i = 0; i < 10; i++) {
        scanf("%d", &num[i]);
        if(i < start && i && num[i])
            start = i;
    }

    if(start == 10) printf("%d", 0);
    else {
        printf("%d", start);
        num[start]--;

        for(int i = 0; i < 10; i++)
            while(num[i]--)
                printf("%d", i);
    }

    return 0;
}

1027 输入格式、统一规律

下解给出倒三角和正三角分别输出情况

#include <iostream>
using namespace std;

int main() {
    int n, i = 3, j = 1;
    char c;
    scanf("%d %c", &n, &c);

    while(j + 2 * i <= n) {
        j += 2 * i;
        i += 2;
    }
    i -= 2;

    int b = 0;
    for(int k = i; k >= 1; k -= 2) {
        int l = k, t = b++;
        while(t--) putchar(' ');
        while(l--) putchar(c);
        putchar('\n');
    }

    b = i / 2 - 1;
    for(int k = 3; k <= i; k += 2) {
        int l = k, t = b--;
        while(t--) putchar(' ');
        while(l--) putchar(c);
        putchar('\n');
    }

    printf("%d", n - j);
    return 0;
}

更简便的办法是统一输出规律

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    int n; char c;
    scanf("%d %c", &n, &c);
    int medium = (int) sqrt((n + 1) / 2);

    for(int row = 1; row <= 2 * medium - 1; row++) {
        for(int i = 1; i <= medium - abs(row - medium) - 1; i++) putchar(' ');
        for(int i = 1; i <= 2 * abs(row - medium) + 1; i++) putchar(c);
        putchar('\n');
    }

    printf("%d", n - 2 * medium * medium + 1);
    return 0;
}

1028 双重排序规则、读入特殊格式、简化思维

#include <iostream>
using namespace std;

struct Person {
    char name[6];
    int yy, mm, dd;
} maxP, minP, tmp, down, up;

// 转为时间戳比较或读入字符串strcmp更易
bool isAbove(Person &high, Person &low) {
    if(high.yy != low.yy) return high.yy < low.yy;
    if(high.mm != low.mm) return high.mm < low.mm;
    return high.dd <= low.dd;
}

int main() {
    int cnt, num = 0;
    down.yy = 1814; down.mm = 9; down.dd = 6;
    up.yy = 2014; up.mm = 9; up.dd = 6;
    minP = down; maxP = up;

    scanf("%d", &cnt);

    for(int i = 0; i < cnt; i++) {

        scanf("%s%d/%d/%d", tmp.name, &tmp.yy, &tmp.mm, &tmp.dd);

        if(isAbove(down, tmp) && isAbove(tmp, up)) {

            if(isAbove(tmp, maxP)) maxP = tmp;

            if(isAbove(minP, tmp)) minP = tmp;

            num++;
        }
    }

    if(num) printf("%d %s %s", num, maxP.name, minP.name);
    else printf("0");

    return 0;
}

1029 散列思想、统一形式、大小写转换

#include <iostream>
using namespace std;

int main()
{
    char s0[10000], s1[10000], *p = s1, c;
    bool map[256] = {0};
    scanf("%s%s", s0, s1);

    while (c = *p) {
        if(*p >= 'a' && *p <= 'z')
            c = *p - 32;
        map[c] = true;
        p++;
    }

    p = s0;
    while (c = *p) {
        if(*p >= 'a' && *p <= 'z')
            c = *p - 32;
        if (!map[c]) {
            putchar(c);
            map[c] = true;
        }
        p++;
    }

    return 0;
}

1032 结果保存和最值

#include <iostream>
using namespace std;

int main() {
    int n, t, maxN, maxP = -1;
    scanf("%d\n", &n);
    int p[n + 1] = {0};

    while(~scanf("%d %d", &n, &t)) {
        p[n] += t;
        if(p[n] > maxP) {
            maxP = p[n];
            maxN = n;
        }
    }

    printf("%d %d", maxN, maxP);

    return 0;
}

1033 散列思想、统一形式

#include <iostream>
using namespace std;

int main(){
    int map[256] = {0};
    char c, t;
    while((c = getchar()) != '\n') {
        if(c >= 'a' && c <= 'z')
            c -= 32;
        map[c]++;
    }

    while((c = getchar()) != '\n') {
        if(map['+'] && c >= 'A' && c <= 'Z')
            continue;
        t = c;
        if(c >= 'a' && c <= 'z')
            t = c - 32;
        if(!map[t]) putchar(c);
    }
    return 0;
}

1037 类进制计算、负数模运算为负结果、注意0

#include <iostream>
using namespace std;

int main()
{
    int g0, s0, k0;
    int g1, s1, k1;
    scanf("%d.%d.%d", &g0, &s0, &k0);
    scanf("%d.%d.%d", &g1, &s1, &k1);
    long t0 = k0 + s0 * 29 + g0 * 493;
    long t1 = k1 + s1 * 29 + g1 * 493;
    if(t1 >= t0) printf("%d.%d.%d", (t1 - t0) / 493, (t1 - t0) % 493 / 29, (t1 - t0) % 29);
    else printf("-%d.%d.%d", (t0 - t1) / 493, (t0 - t1) % 493 / 29, (t0 - t1) % 29);
    return 0;
}

1038 注意数组初始化

#include <iostream>
using namespace std;

int main()
{
    int N, K, p;
    scanf("%d", &N);
    int a[101] = {0};

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

    scanf("%d", &K);
    while (--K) {
        scanf("%d", &p);
        printf("%d ", a[p]);
    }
    scanf("%d", &p);
    printf("%d", a[p]);
    return 0;
}

1039 类桶排思想、输出带符号格式

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

int main()
{
    int pearl[256], less = 0, more = 0;
    char c;
    memset(pearl, 0, sizeof(pearl));
    while ((c = getchar()) != '\n')
        pearl[c]++;
    while ((c = getchar()) != '\n')
        pearl[c]--;
    for (int i = 0; i < 256; i++) {
        if (pearl[i] < 0)        less -= pearl[i];
        else if (pearl[i] > 0)   more += pearl[i];
    }
    if (less) printf("No %d", less);
    else printf("Yes %d", more);
    return 0;
}

1042 最值、双重排序规则

#include <iostream>
using namespace std;

int main()
{
    char c;
    int max = 25;
    int num[26] = {0};
    while ((c = getchar()) != '\n')
    {
        if (c >= 'a' && c <= 'z')
            num[c - 'a']++;
        else if (c >= 'A' && c <= 'Z')
            num[c - 'A']++;
    }

    for (int i = 24; i >= 0; i--)
        if (num[i] >= num[max])
            max = i;

    printf("%c %d", max + 'a', num[max]);
    return 0;
}

1048 双指针、char运算转int、统一0

#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    char a[101], b[101];
    scanf("%s%s", a, b);
    int i, j, cnt = 1;
    i = strlen(a) - 1;
    j = strlen(b) - 1;
    cnt = max(i, j);
    a[cnt + 1] = '\0';
    int A, B, tmp, flag = 1;

    while (cnt >= 0) {
        // 或用平移方法，通过下标映射来对齐运算
        A = i < 0 ? 0 : a[i] - '0';
        B = j < 0 ? 0 : b[j] - '0';

        if (flag) {
            tmp = (A + B) % 13;
            if (tmp == 10) a[cnt] = 'J';
            else if (tmp == 11) a[cnt] = 'Q';
            else if (tmp == 12) a[cnt] = 'K';
            else a[cnt] = tmp + '0';
        }
        else {
            tmp = B - A;
            if (tmp < 0) a[cnt] = tmp + 10 + '0';
            else a[cnt] = tmp + '0';
        }

        cnt--;
        flag = !flag;
        if (i != -1) i--;
        if (j != -1) j--;
    }
    printf("%s\n", a);
    return 0;
}

1049 int溢出、double不精确、数字规律

枚举会超时，故寻找数字规律

循环体核心语句num必须置前且为较大的类型，否则先算i * (N – i + 1)可能会导致int溢出

IEEE754的double只是近似值，为达到可用精度，先挪动小数点计算后再恢复小数点

注意强制转型是就近结合的，double转long long时整体运算转型需要加括号以防止精度丢失

参考 @zhengrh

#include <iostream>
using namespace std;

int main()
{
    int N;
    double num;
    long long sum = 0;

    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%lf", &num);
        sum += (long long) (num * 1000) * i * (N - i + 1);
    }
    printf("%.2f", sum / 1000.0);

    return 0;
}

1052 特殊字符读取、转义、正则读取

这道题有够坑的，if条件之多也是目前之最了，此处参考 @OliverLew 源码

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

int main() {
    char c, symbol[3][10][5];
    memset(symbol, '\0', sizeof(symbol));

    for(int i = 0; i < 3; i++)
        for(int j = 0; (c = getchar()) != '\n'; j)
            if(c == '[') scanf("%[^]]", symbol[i][j++]);

    int n, index[5];
    scanf("%d", &n);
    while(n--)
    {
        for(int i = 0; i < 5; i++)
            scanf("%d", &index[i]);

        if (index[0] > 0 && index[0] <= 10 && *symbol[0][--index[0]]
            && index[1] > 0 && index[1] <= 10 && *symbol[1][--index[1]]
            && index[2] > 0 && index[2] <= 10 && *symbol[2][--index[2]]
            && index[3] > 0 && index[3] <= 10 && *symbol[1][--index[3]]
            && index[4] > 0 && index[4] <= 10 && *symbol[0][--index[4]])
            printf("%s(%s%s%s)%s\n",symbol[0][index[0]],symbol[1][index[1]],symbol[2][index[2]],symbol[1][index[3]],symbol[0][index[4]]);
        else printf("Are you kidding me? @\\/@\n");
    }

    return 0;
}

1082 思维转换取值大的反而小

#include <iostream>
using namespace std;
int main() {
    while(getchar() != '\n');
    int mx = -1, mn = 10001, mxN, mnN, x, y, pos, t;
    while(~scanf("%d%d%d", &t, &x, &y)) {
        pos =  x * x + y * y;
        if(pos > mx) { mxN = t; mx = pos; }
        if(pos < mn) { mnN = t; mn = pos; }
    }

    printf("%04d %04d", mnN, mxN);

    return 0;
}

1088 注意变量可能为double型

#include <iostream>
using namespace std;

int main() {
    int M, X, Y, a, b;
    double c;
    scanf("%d%d%d", &M, &X, &Y);
    for(int a = 99; a >= 10; a--) {
        b = a % 10 * 10 + a / 10;
        if(a > b)       c = (a - b) * 1.0 / X;
        else            c = (b - a) * 1.0 / X;

        if(b == Y * c) {
            printf("%d", a);
            printf(M > a ? " Gai": (M < a ? " Cong": " Ping"));
            printf(M > b ? " Gai": (M < b ? " Cong": " Ping"));
            printf(M > c ? " Gai": (M < c ? " Cong": " Ping"));
            return 0;
        } 
    }
    printf("No Solution");
    return 0;
}

1089 暴力枚举

知道是暴力枚举有什么用，还不是被打败了没模拟出来…下次再来

1092 结构体数组初始化和排序、循环边界

可以不排序，一次遍历记录最大值序号，一次遍历输出所有最大值序号

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

struct B{
    int type;
    int sell;
};

bool cmp (B b1, B b2) {
    if(b1.sell != b2.sell) return b1.sell > b2.sell;
    return b1.type < b2.type;
}

int main() {
    int N, M, T;
    scanf("%d%d", &N, &M);
    B Ins[N] = {0};

    while(M--) {
        for(int i = 0; i < N; i++) {
            scanf("%d", &T);
            Ins[i].type = i + 1;
            Ins[i].sell += T;
        }
    }

    sort(Ins, Ins + N, cmp);
    T = Ins[0].sell;
    printf("%d\n", T);
    printf("%d", Ins[0].type);
    for(int i = 0; i < N - 1 && Ins[i + 1].sell == T; i++)
        printf(" %d", Ins[i + 1].type);
    return 0;
}

1093 getchar != EOF读入换行也会停止

#include <iostream>
using namespace std;

int main() {
    bool isExist[128] = {0};
    char c;
    int i = 2;
    while(i) {
        while((c = getchar()) != '\n') {
            if(!isExist[c]) {
                isExist[c] = true;
                putchar(c);
            }
        }
        i--;
    }

    return 0;
}

1094 注意已给定长度，字符串转整数

字符串转整数库函数

#include <stdlib.h>
#include <stdio.h>
int atoi(const char *nptr);

复制指定地址开始指定个数字符到字符数组库函数

#include <stdio.h>
char *strncpy(char *dest, const char *src, int n)

#include <iostream>
using namespace std;

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

long long toNum(char *p, int i) {
    long long e = 1;
    long long sum = 0;
    for(; i >= 0; i--) {
        sum += (*(p + i) - '0') * e;
        e *= 10;
    }
    return sum;
}

int main() {
    int n, k;
    char s[1000], *p = s;
    scanf("%d %d", &n, &k);
    scanf("%s", s);
    k--;
    while(*p) {
        long long num = toNum(p, k);
        if(isPrime(num)) {
            for(int i = 0; i <= k; i++)
                printf("%c", *(p + i));
            return 0;
        }
        p++;
    }
    printf("404");
    return 0;
}