# P8759 [蓝桥杯 2021 国 B] 填空问题

· · 题解

P8759 [蓝桥杯 2021 国 B] 填空问题

看问题A：

思路：

做这道题的时候，我们要知道一个知识 1MB = 8Mbps，所以 200Mbps = 25MB。

code 很简单：

int main(){
    cout << 200 / 8;
}

得到答案25。

问题B

思路：

思路很简单，就是枚举 1 到 20210605 中所有的数，判断其是否为质数，再进行数位分离。

code:

首先质数判定的函数：

bool isprime(int n){
    if(n < 2) return 0;//小于2的都不是质数
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return 0;//能整除n，所以n不是质数
    }
    return 1;
}

主函数代码：

int main(){
    int ans = 0;
    for(int i = 2; i <= 20210605; i++){//1不是质数
        if(isprime(i)){//i必须是质数
            int j = i;
            bool t = 1;//初始默认i是纯质数
            while(j){//进行数位分离
                if(!isprime(j % 10)){//判断j（i）的每一位是不是质数
                    t = 0;//修改t
                    break;
                }
                j /= 10;
            }
            if(t) ans++;//如果t为真，i就是纯质数
        }
    }
    cout << ans;
}

得到答案 1903。

问题C

思路：

直接枚举 2001-01-01 到 2021-12-31 ，每次进行数位分离，并判断数位分离后的和是否为完全平方数（这里有一个偷懒的方法，由于数位分离后的和最小是 5 ，具体日期为 2001 年 1 月 1 日，最大是 32，具体日期是 2019 年 9 月 29 日，5到32之间的完全平方数只有 9、16、25 ，所以只需要判定这么多）。

code:

int check_month(int year, int month){//用于检查月份天数 
    //判断大月 
    if(month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12){
        return 31;
    }
    //判断小月 
    if(month == 4 || month == 6 || month == 9 || month == 11){
        return 30;
    }
    //剩下的就是2月份 ，判断年份是否为闰年 
    if(year % 400 == 0){//能被400整除年份是世纪闰年 
        return 29;
    }
    if(year % 100 != 0 && year % 4 == 0){//除世纪闰年外，剩下的闰年都不能被100整除，但可以被4整除 
        return 29;
    } 
    return 28;//剩下的就都是平年且为2月了 
}
int digital_separation(int year, int month, int day){//对日期进行数位分离的函数 
    int sum = 0;
    while(year){//对年份进行分离 
        sum += year % 10;
        year /= 10; 
    }
    while(month){//对月份进行分离 
        sum += month % 10;
        month /= 10; 
    }
    while(day){//对天数进行分离 
        sum += day % 10;
        day /= 10; 
    }
    return sum;
}
int main(){
    int cnt = 0;//统计完全日期 
    for(int year = 2001; year <= 2021; year++){//年份 
        for(int month = 1; month <= 12; month++){//月份 
            int day = check_month(year, month);//月份有的天数 
            for(int i = 1; i <= day; i++){//日期 
                int result = digital_separation(year, month, i);//获得数位分离后的结果 
                if(result == 9 || result == 16 || result == 25){//判断是否为完全平方数 
                    cnt++;
                }
            } 
        } 
    }
    cout << cnt;
}

得到答案 977。

问题D

思路：

虽然题目说的是二叉树，但是方法不是二叉树（我一开始还傻乎乎的写了棵树，后来才想起来 dp）……

由于题目已经给了一个公式： W(v)=1+2W(L)+3W(R)+(C(L))^2 C(R)，那么只需要根据这个公式推导就行了，由于题目说要树的权值最小，所以每一次都要判定是否最小（数组还得初始化为最大，我为此又调了半天时间）……

code:

#define ll long long
ll tree[10010];
int main(){
    memset(tree, 0x3f, sizeof(tree));//假设二叉树里的值都是最大的（后面有比较哪个更小） 
    tree[0] = 0;//一开始二叉树是空的 ，所以第一项为0 
    for(int i = 1;i <= 2021;i++){//二叉树有2021个节点 
        for(int j = 0;j < i;j++){
            ll a = 1 + 2 * tree[j] + 3 * tree[i - j - 1] + j * j * (i - j - 1);//根据W(v)=1+2W(L)+3W(R)+(C(L))(c(L))C(R)所得来
            if(a < tree[i]) tree[i] = a; //判断哪个更小 
        }
    }
    cout << tree[2021];
}

得到答案 2653631372。

最后判断的code：

#include <bits/stdc++.h>
using namespace std;
int main(){
    char c;
    cin >> c;
    if(c == 'A') cout << 25;//问题A
    if(c == 'B') cout << 1903;//问题B
    if(c == 'C') cout << 977;//问题C
    if(c == 'D') cout << 2653631372;//问题D
}