Day1 蓝桥杯省赛冲刺精炼刷题 —— 位运算与循环

发布于：2025-03-26 ⋅ 阅读:(15) ⋅ 点赞:(0)

一、0握手问题 - 蓝桥云课（条件枚举）

直接算代码：

#include <iostream>
using namespace std;
int main()
{
    int sum=0;
    for(int i=49;i>=7;i--)
        sum+=i;
    cout<<sum<<endl;
    return 0;
}

验证代码：

int ans = 0;
for (int i = 1; i <= 50; ++i) {
  for (int j = i + 1; j <= 50; ++j) {
    if (i <= 7 && j <= 7) continue;
    else ans ++;
  }
}

 模拟逻辑：前7个人不会相互握手，其他人相互握手，每次握手一次，次数加一。

二、 0门牌制作 - 蓝桥云课（十进制整数拆解）

直接算代码： 

#include <iostream>
using namespace std;
int main()
{
    int ans=0;
    for(int i=1;i<=2020;i++)
    {
        int ans=i;
        if(i%10==2) ans++;
        if(i/10%10==2) ans++;
        if(i/100%10==2) ans++;
        if(i/1000==2) ans++;
        //    while (x > 0) 
        //    {
        //        if (x % 10 == 2) ans ++;
        //        x /= 10;
        //    }
    }
    cout<<ans;
    return 0;
}

知识点：

        考察十进制整数拆解，即将一个十进制整数 xx 按照十进制拆除每一位，如 903903，拆成 {9,0,3}、{9,0,3}。拆解十进制整数的代码模版：

int a[count], len = 0;//数组中存储整数 xx 的每一位。len 代表 xx 的长度
do {
  a[++len] = x % 10;
  x /= 10;
} while (x > 0);

三、0九进制转十进制 - 蓝桥云课 （进制转换）

直接算代码： 

#include <iostream>
using namespace std;
int main()
{
    cout<<2*9*9*9+2*9+2;
    return 0;
}

1、模拟进制转换过程，得到 n 进制转换为十进制的代码：

/**
 * n 代表整数的进制
 * a 存储n进制数每一位的数组
 * len a数组长度，即该n进制整数的长度
 */
int n_to_10(int n, int a[], int len) {
    int res = 0;
    int p = 1;
    for (int i = len - 1; i >= 0; --i) {
        res += a[i] * p;
        p *= n;
    }
    return res;
}

优化：

/**
 * n 代表整数的进制
 * a 存储n进制数每一位的数组
 * len a数组长度，即该n进制整数的长度
 */
int n_to_10(int n, int a[], int len) {
    int res = 0;
    for (int i = 0; i < len; ++i) {
        res = res * n + a[i];//将当前的 res 左移一位（相当于乘以 n），然后加上当前位的值
    }
    return res;
}

2、模拟十进制数转换为 n 进制

/**
 * 十进制转换为n进制
 * x为十进制整数 
 * a为转换后的存储空间，逆序存储
 * 该函数返回一个len，代表转换后的长度
 */
int _10_to_n(int x, int n, int a[]) {
    int len = 0;
    do {
        a[len ++] = x % n;
        x /= n;
    } while (x > 0);
    return len;
}

四、0平方差 - 蓝桥云课（高精度计算）

算法代码（模拟）：

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

char s1[105], s2[105]; // 存放输入的两个大整数字符串
int a1[105] = {0}, a2[105] = {0}; // 存放将字符串转换为整数后的数组
int result1[105], result2[105], result[210] = {0}; // 存放加法、减法和乘法的结果

int main()
{
    scanf("%s %s", s1, s2); // 读取两个大整数字符串

    int i1 = strlen(s1); // 获取第一个字符串的长度
    int i2 = strlen(s2); // 获取第二个字符串的长度
    int l1 = i1, l2 = i2, begin1 = 0, begin2 = 0; // l1为|A|的长度, l2为|B|的长度

    // 处理负号
    if (s1[0] == '-') {
        l1--; // 如果第一个数是负数，长度减1
        begin1 = 1; // 从第二个字符开始处理
    }
    if (s2[0] == '-') {
        l2--; // 如果第二个数是负数，长度减1
        begin2 = 1; // 从第二个字符开始处理
    }

    // 将字符串转换为整数数组，个位存放在数组首地址处
    for (int i = begin1; i < i1; i++) {
        a1[i1 - 1 - i] = s1[i] - '0';
    }
    for (int i = begin2; i < i2; i++) {
        a2[i2 - 1 - i] = s2[i] - '0';
    }

    int maxl = l1; // 找出两个数的最大长度
    if (l2 > l1)
        maxl = l2;

    // 加法部分
    int r1 = maxl; // 加法的结果长度
    for (int i = 0; i < maxl; i++) { // 先直接加
        result1[i] = a1[i] + a2[i];
    }
    for (int i = 0; i < maxl; i++) { // 后进位
        if (result1[i] >= 10) {
            result1[i] %= 10;
            result1[i + 1] += 1;
            if (i == maxl - 1)
                r1++;
        }
    }

    // 减法部分
    int r2 = maxl; // 减法的结果长度
    int flag1 = 0; // 标记结果是否为负数
    for (int i = 0; i < r2; i++) { // 先直接减
        result2[i] = a1[i] - a2[i];
    }
    while (result2[r2 - 1] == 0) // 将值为0的高位从长度中去除
        r2--;
    if (result2[r2 - 1] < 0) { // 若最高位为负，则结果是一个负值
        flag1 = 1;
        for (int i = 0; i < r2; i++) {
            result2[i] *= (-1); // 将各个位取相反数
        }
    }
    for (int i = 0; i < r2; i++) { // 进位
        if (result2[i] < 0) {
            result2[i] = 10 + result2[i];
            result2[i + 1] -= 1;
        }
    }
    while (result2[r2 - 1] == 0) // 去除前导零
        r2--;

    // 乘法部分
    int r = r1 + r2; // 乘法的结果长度
    for (int i = 0; i < r1; i++) { // 乘法定律
        for (int j = 0; j < r2; j++) {
            result[i + j] += result1[i] * result2[j];
        }
    }
    for (int i = 0; i < r; i++) { // 进位
        if (result[i] >= 10) {
            result[i + 1] += result[i] / 10;
            result[i] %= 10;
        }
    }

    // 打印结果
    while (result[r - 1] == 0) { // 计算结果的真正长度
        r--;
    }
    if (flag1 == 1) // 如果结果是负数，打印负号
        printf("-");
    for (int i = r - 1; i >= 0; i--) { // 从高位到低位打印结果
        printf("%d", result[i]);
    }
    return 0;
}

 

大佬代码（复杂了点）：

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

const int N = 300; // 定义常量N，表示数组的最大长度

char A[N], B[N]; // 用于存储输入的两个字符串形式的整数
int a[N], lena, f_a; // a存储A的绝对值，lena是A的长度，f_a是A的符号（1表示负数）
int b[N], lenb, f_b; // b存储B的绝对值，lenb是B的长度，f_b是B的符号（1表示负数）
int aa[N], lenaa; // aa存储a的平方
int bb[N], lenbb; // bb存储b的平方
int c[N], lenc; // c存储最终结果

/**
 * 判断a是否大于等于b，如果成立，返回1，否则返回0
 * a 存储a整数的数组
 * lena a整数的长度
 */
int comp(int a[], int lena, int b[], int lenb) {
    if (lena != lenb) return lena > lenb; // 如果长度不同，直接比较长度
    for (int i = lena - 1; i >= 0; --i) { // 从最高位开始比较
        if (a[i] > b[i]) return 1;
        else if (a[i] < b[i]) return 0;
    }
    return 1; // 如果所有位都相等，返回1
}

/**
 * 计算出 a - b，并且放在c中，保证 a >= b
 * 返回c的长度
 */
int sub(int a[], int lena, int b[], int lenb, int c[]) {
    int lenc = lena; // 初始化结果的长度为a的长度
    for (int i = 0; i < lenc; ++i) {
        c[i] = a[i] - b[i]; // 逐位相减
    }
    for (int i = 0; i < lenc; ++i) {
        if (c[i] < 0) c[i] += 10, c[i + 1] --; // 处理借位
    }
    while (lenc > 0 && c[lenc - 1] == 0) lenc --; // 去掉前导零
    if (lenc == 0) lenc = 1; // 如果结果为0，保留一位
    return lenc;
}

/**
 * 计算出 a * b，并且放在c中
 * 返回c的长度
 */
int multi(int a[], int lena, int b[], int lenb, int c[]) {
    int lenc = lena + lenb - 1; // 初始化结果的长度
    for (int i = 0; i < lena; ++i) {
        for (int j = 0; j < lenb; ++j) {
            c[i + j] += a[i] * b[j]; // 逐位相乘并累加
        }
    }
    for (int i = 0; i < lenc; ++i) {
        if (c[i] > 9) { // 处理进位
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }
    if (c[lenc] > 0) { // 处理最高位的进位
        c[lenc + 1] += c[lenc] / 10;
        c[lenc] %= 10;
        lenc ++;
    }
    return lenc;
}

/**
 * 将字符串转换为整数存储，并且返回整数长度
 */
int get_num(char *s, int *a) {
    int n = strlen(s); // 获取字符串长度
    for (int i = n - 1; i >= 0; --i) a[n - 1 - i] = s[i] - '0'; // 将字符转换为数字并逆序存储
    return n;
}

void sol() {
    scanf("%s", A); // 读取第一个数
    scanf("%s", B); // 读取第二个数
    if (A[0] == '-') lena = get_num(A + 1, a), f_a = 1; // 如果A是负数，处理符号并获取绝对值
    else lena = get_num(A, a); // 如果A是正数，直接获取绝对值
    if (B[0] == '-') lenb = get_num(B + 1, b), f_b = 1; // 如果B是负数，处理符号并获取绝对值
    else lenb = get_num(B, b); // 如果B是正数，直接获取绝对值

    lenaa = multi(a, lena, a, lena, aa); // 计算a的平方
    lenbb = multi(b, lenb, b, lenb, bb); // 计算b的平方
    if (comp(a, lena, b, lenb)) { // 如果a的绝对值大于等于b
        lenc = sub(aa, lenaa, bb, lenbb, c); // 计算a² - b²
    } else { // 否则结果是一个负数
        lenc = sub(bb, lenbb, aa, lenaa, c); // 计算b² - a²
        printf("-"); // 输出负号
    }
    for (int i = lenc - 1; i >= 0; --i) {
        printf("%d", c[i]); // 输出结果
    }
    printf("\n");
}

int main() {
    sol(); // 调用sol函数
}

知识点：

        在C/C++中，由于没有大整数类，最大的整数只能表示 2^64−1，所以在一些情况下，需要模拟大整数运算，常用的其实就是乘法和加减法。

由于本身就是模拟运算，所以按照手算的竖式运算即可。

对于大整数运算通常有以下几点注意：

  1. 由于输入的时候无法使用正常方式输入，所以我们采用字符串输入，然后逆序过来，方便运算。

  2. 加法的话直接对应位置相加，然后从低位到高位处理进位问题。

  3. 减法的话，需要先判断大小，然后用绝对值大的整数减去小的，最后处理借位和符号问题。

  4. 乘法的话，按照竖式的方式进行计算，然后处理进位问题。

五、2.跑步 - 蓝桥云课（日期问题）

算法代码：

#include <stdio.h>

// 每个月的日期数,ds[i]代表i月份的天数
int ds[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
    int sy = 2022; // 起始年份
    int ey = 2022; // 结束年份
    int week = 6; // 定义 0-6 ,0为星期日，1为星期一，2为星期二...
    int ans = 0;
    for (int y = sy; y <= ey; ++y) { // 第一层循环，枚举年份
        for (int m = 1; m <= 12; ++m) { // 第二层循环，枚举月份
            int dd = ds[m];
            if (y % 4 == 0 && y % 100 != 0 && m == 2) // 判断是不是闰月
                dd = 29;
            else if (y % 400 == 0 && m == 2) // 判断是不是闰月
                dd = 29;
            for (int d = 1; d <= dd; ++d) { // 枚举天
                if (week == 0 || week == 6 || d % 10 == 1) { // 如果满足某一个条件，就记录答案
                        ans ++;
                    }
                week = (week + 1) % 7; // 向后推移星期几
            }
            
        }
    }
    printf("%d\n", ans);
    return 0;
}

思路：（通用框架）

  1. 使用列表存储月份的天数，使得判断天数的时候能够直接查表，查表法非常好用，后续算法中也可能会用到。

  2. 星期的推演，由于星期是7天为一个轮回，所以使用取模的技巧，将周日设置为0，巧妙的将周六后是周日、周日后一天是周一联系的起来。

  3. 观察到每个日期是以1结尾，所以，利用取模的技巧将最后一个数取出进行判断，舍去了需要判断是1、11、21、31的麻烦。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布