P8758 [蓝桥杯 2021 国 A]

· · 题解

试题 A：纯质数

因为是提交答案题，根本不用考虑什么时间空间，只要能算出正确答案就行。不管用什么筛法，筛出来就行。这里放一份拆位的代码。

int a[10],len;
while(n){
    a[++len]=n%10;
    n/=10;
}

answer：1903。

试题 B：完全日期

直接暴力枚举即可。把每个月的天数存在一个数组里，如若大于原本的天数，则月份加一，日变为一（如果变回零，则循环内要先自增）。月份同理。不要忘记判断闰年。answer：977。

试题 C：最小权值

题目中已给出公式，直接套用。核心代码：

for(int i=2;i<=2021;i++){
    for(int j=0;j<=i-1;j++){
        long long k=1+2*W[j]+3*W[i-j-1]+j*j*(i-j-1);
        W[i]=min(W[i],k);
    } 
}

answer：2653631372。

试题 D：覆盖

这是一道状态压缩动态规划，用 {\large f_{i,j}} 表示第 i 行覆盖状态为 j 的方案数，而现在这个状态是由上一行推导出来的。为方便计算，我们将是否合法标记为 0 或 1，将横向放置或纵向放置也标记为 0 或 1，统计合理的方案数即可。

answer：12988816。

Code

#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "1903",
        "977",
        "2653631372", 
        "12988816",
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'];
    return 0;
}