题解：P8690 [蓝桥杯 2019 国 B] 填空问题

· · 题解

前言：

搭配 CSDN 可以更好的食用哦！

试题 A:

从 2019 开始枚举，如果成功就退出。记得开 long long。

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    long long sum=1<<30;
    for(long long x=2020;x<=10000;x++)
    for(long long y=x+1;y<=10000;y++)
    if(y*y-x*x==x*x-2019*2019&&x+y<sum)sum=y+x;
    printf("%d\n",sum);
}

答案：7020。

试题 B:

可以先算出所有的素数，再用 0/1 背包求解即可。

#include<bits/stdc++.h> 
using namespace std;
bool vis[10005];//是否为素数 
long long tot,c[10005];//存素数
long long f[10005];//dp 
void ss(){
    for(int i=2;i<=2019;i++){
        if(vis[i])continue;
        c[++tot]=i;
        for(int j=2;j*i<=2019;j++)
        vis[j*i]=1;
    }
} 
int main(){
    ss();
    f[0]=1;
    for(int i=1;i<=tot;i++)
    for(int j=2019;j>=c[i];j--)
    f[j]+=f[j-c[i]];
    printf("%lld\n",f[2019]);
}

答案：55965365465060。

试题 C:

深度爆搜 DFS，记得每次 vis 数组要清。

#include<bits/stdc++.h> 
using namespace std;
//const int flag[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool vis[105][105],k;
int ans;
bool check(int x,int y){
    return x<1||x>8||y<1||y>8||y<=x;
}
void DFS(int x,int y){
    if(x==1||y==8){ans++;return;}//判断边界
    if((check(x,y)||vis[x][y])&&k)return;
    k=1;
    vis[x][y]=1;
//  for(int i=0;i<4;i++){
//      int now_x=x+flag[i][0],now_y=flag[i][1];
//      DFS(now_x,now_y);
//  }
    DFS(x+1,y);
    DFS(x-1,y);
    DFS(x,y+1);
    DFS(x,y-1);
    vis[x][y]=0;
}
int main(){
    for(int i=1;i<=8;i++){
        for(int j=1;j<=10;j++)vis[i][j]=0;//清数组
        k=0;
        DFS(i,i);
    }
    printf("%d\n",ans);
}

答案：2444。

试题 D:

暴力枚举 YYDS！

#include<bits/stdc++.h> 
using namespace std;
int main(){
    for(int i=4;i;i++){
        int cnt=0;
        for(int j=1;j<=i;j++)
        if(i%j==0)cnt++;
        if(cnt==100){
            printf("%d\n",i);
            return 0;
        }
    } 
}

答案是 45360。

试题 E:

还是暴力搜索，先判断边界，然后再递归。

#include<bits/stdc++.h> 
using namespace std;
const int flag[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int ans=0;
bool vis[6][6];
bool check(int x,int y){
    return x<0||x>5||y<0||y>5;
}
void DFS(int x,int y,int sum){
    if(sum>12)return;
    if(sum>=4&&x==0&&y==0){ans++;return;}
    for(int i=0;i<4;i++){
        int now_x=x+flag[i][0],now_y=y+flag[i][1];
        if(check(now_x,now_y)||vis[now_x][now_y])continue;
        vis[now_x][now_y]=1;
        DFS(now_x,now_y,sum+1);
        vis[now_x][now_y]=0;
    }

}
int main(){
    DFS(0,0,0);
    printf("%d\n",ans);
}

答案是 206。

AC CODE：

知道你们最喜欢啦！

#include<bits/stdc++.h>
using namespace std;
char T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string ans [] = {
        "7020",
        "55965365465060", 
        "2444", 
        "45360", 
        "206",
    };
    cin>>T;
    cout<<ans[T-'A']<<'\n';
    return 0;
}

求管理员通过！