蓝桥杯刷题(持续更新...)

本文最后更新于:几秒前

lanqiao

本栏目记录在 蓝桥杯 刷题中的一些思考和反思,持续更新…

如果觉得我代码太烂,欢迎留言拍砖。🎉

本文创建于: 2020.03.24 || 更新log: 2020.03.312020.03.302020.03.24

Tip

  • 建议PC端查看此文,因为有目录可以参考。
  • 此文只列举(浪费时间多的)部分题,更多题在 我的github 中。

BASIC-10 十进制转十六进制

资源限制
时间限制:1.0s   内存限制:512.0MB
问题描述
  给定n个十六进制正整数,输出它们对应的八进制数。
输入格式
  输入的第一行为一个正整数n (1<=n<=10)。
  接下来n行,每行一个由0~9、大写字母A~F组成的字符串,表示要转换的十六进制正整数,每个十六进制数长度不超过100000。
输出格式
  输出n行,每行为输入对应的八进制正整数。
【注意】
  输入的十六进制数不会有前导0,比如012A。输出的八进制数也不能有前导0。
样例输入
  2
  39
  123ABC
样例输出
  71
  4435274
【提示】
  先将十六进制数转换成某进制数,再由某进制数转换成八进制。

一、思路

  • 用自带的进制输出,真是太方便啦!📎 C++好用的进制转换
  • 但是这数据规模忒🐔大了,每个十六进制数长度不超过 100000 * 4/3 = 长度足足有 133333 位
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        long long s;
        cin >> hex >> s;
        cout << oct << s << endl;
    }
    return 0;
}

二、改进

1.用什么存

  • 用字符串读入,输出。(便于挨个字符转换 + 便于字符拼接)

2.如何转换

  • 十六进制数 挨个转换为 二进制数,并拼接。【利用数组 s2 += a[s16[j] - 'A' + 10];
  • 二进制数,每三位,转换成八进制。【利用键值对 s8 += m[tmp];
#include <iostream>
#include <map>
using namespace std;
int main() {
    string a[16] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", 
        "1010", "1011", "1100", "1101", "1110", "1111"};
    map<string, string> m;
    m["000"] = "0";
    m["001"] = "1";
    m["010"] = "2";
    m["011"] = "3";
    m["100"] = "4";
    m["101"] = "5";
    m["110"] = "6";
    m["111"] = "7";
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s16 = "", s2 = "", s8 = "";
        cin >> s16;
        for (int j = 0; j < s16.size(); j++) {
            if (s16[j] > '9') {
                s2 += a[s16[j] - 'A' + 10];
            } else {
                s2 += a[s16[j] - '0'];
            }
        }
        if (s2.size() % 3 == 1) {
            s2 = "00" + s2;
        } else if (s2.size() % 3 == 2) {
            s2 = "0" + s2;
        }
        int flag = 0;
        for (int j = 0; j < s2.size(); j += 3) {
            string tmp = s2.substr(j, 3);
            s8 += m[tmp];    
            if (j == 0 && m[tmp] == "0") {
                flag = 1;
            }
        }
        if (flag) {
            s8 = s8.substr(1);
        }
        cout << s8;
        cout << endl;
    }
    return 0;
}

/*
易错:
1. 第5行,初始化数组,逗号别少写。
2. 第22行,s16[j] > '9',9的单引号,别少写
3. 第29行,不能写成 s2 += “00”,因为 “00” 应该在前面
4. 第45行,注意换行,保持题目输出的格式一致
*/

BASIC-30 阶乘计算

资源限制
时间限制:1.0s   内存限制:512.0MB
问题描述
  输入一个正整数n,输出n!的值。
  其中n!=1*2*3*…*n。
算法描述
  n!可能很大,而计算机能表示的整数范围有限,需要使用高精度计算的方法。使用一个数组A来表示一个大整数a,A[0]表示a的个位,A[1]表示a的十位,依次类推。将a乘以一个整数k变为将数组A的每一个元素都乘以k,请注意处理相应的进位。首先将a设为1,然后乘2,乘3,当乘到n时,即得到了n!的值。
输入格式
  输入包含一个正整数n,n<=1000。
输出格式
  输出n!的准确值。
样例输入
10
样例输出
3628800

一、思路:

1.用什么存:

  • ans 来存结果,因为不知道数组多长,使用 vector ,并倒序储存结果,个位在 a[0]。
  • flag 来存进位值,同 vector

2.如何进位

  • flag 长度保持比 ans 长度多一位,当 flag 长度 = ans 长度时,flag 长度增加,存 ans 的进位值 或 0。

  • 一轮结束,当 falg 最后一位,不为零时,ans 长度增加,存 falg 最后一位值。

3.缺点

  • vector 长度增加时 的判断过于麻烦。(判断是否处于最后一位 & 判断增加长度处的值为进位值 or 0)
  • 边乘边进位的逻辑过于繁琐,可以分两次,先乘再加,(见优化)
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> ans, flag;
    ans.push_back(1);
    flag.push_back(0);
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < ans.size(); j++) {
            ans[j] = i * ans[j] + flag[j];
            flag[j] = 0;
            if (ans[j] >= 10) {
                if (flag.size() - 1 == j) {
                    flag.push_back(ans[j] / 10);
                } else {
                    flag[j + 1] = ans[j] / 10;
                }
                ans[j] %= 10;
            } else {
                if (flag.size() - 1 == j) {
                    flag.push_back(0);
                } else {
                    flag[j + 1] = 0;
                }
            }
        }
        while (flag[flag.size() - 1]) {
            ans.push_back(flag[flag.size() - 1]);
            if (ans[ans.size() - 1] >= 10) {
                flag.push_back(ans[ans.size() - 1] / 10);
                ans[ans.size() - 1] %= 10;
            } else {
                flag.push_back(0);
            }
        }
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i];
    }
    return 0;
}
/*
易错:
29-36行,对ans的最高位进位的操作必不可少,否则下一轮,最高位的乘法的结果会爆
i-- 别写成 i++
*/

二、优化

  • 初始化一个大数组 a[10000],可省去 push_back() 步骤。

  • 多次循环,将 乘法 和 进位(加法) 用两个循环分开处理。

  • 多次循环,将 去除前置0 和 打印 分开处理。

#include <iostream>
using namespace std;
int main() {
    int a[10000] = {1};
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10000; j++) {
            a[j] *= i;
        }
        for (int j = 0; j < 10000; j++) {
            if (a[j] >= 10) {
                a[j + 1] += (a[j] / 10);
                a[j] %= 10; 
            }
        }
    }
    int flag = 0;
    for (int i = 9999; i >= 0; i--) {
        if (a[i] == 0) {
            continue;
        }
        flag = i;
        break;
    }
    for(int i = flag; i >= 0; i--) {
        cout << a[i];
    }
    return 0;
}
/*
易错:a[10000] 的数组长度,1000不够大,需要10000。
*/

三、启示

  • 有大大大大数乘法,可以用数组存。

本博客所有文章均个人原创,除特别声明外均采用 CC BY-SA 4.0协议,转载请注明出处!

 目录

致敬李文亮及各路英雄好汉!