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

试题 \(\mathrm{A}\) : 平方序列

枚举 \(x\)，通过 \(x^2-2019^2\) 求出它们的公差 \(c\)，再计算 \(x^2+c\) 是否为完全平方数即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	for(int i=2020;1==1;i++){
	int c=i*i-2019*2019;
	int k=i*i+c;
	if(sqrt(k)*sqrt(k)==k){
		cout<<sqrt(k)+i;
		return 0;
	    }
	}
}

答案为 \(7020\)。

试题 \(\mathrm{B}\) : 质数拆分

埃筛筛出所有 $ 2 \sim 2019 $ 范围内的所有质数，再用背包求出答案即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool k[2020];
int h=1;
int p[1000],dp[2020];
void pd(){
	memset(k,0,sizeof(k));
	k[1]=k[0]=0;
	for(int i=2;i<=2019;i++){
		if(k[i]==1) continue;
		p[h]=i;
		h++;
		for(int j=i;j<=2019;j+=i){
			k[j]=1;
		}
	}
}
signed main(){
	pd();
	dp[0]=1;
	for(int i=1;i<h;i++){
		for(int j=2019;j>=p[i];j--){
			dp[j]+=dp[j-p[i]];
		}
	}
	cout<<dp[2019];
	return 0;
}

答案为 \(55965365465060\)。

试题 \(\mathrm{C}\) : 拼接

暴搜对角线上的所有点，计算所有可能，并统计其方案数。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int ans=0;
bool vis[8][8];
void dfs(int x,int y){
	if(x==0||y==7){
		ans++;
		return;
	}
	for(int i=0;i<4;i++){
		int nx=dx[i]+x,ny=dy[i]+y;
		if(nx<0||nx>7||ny<=nx||ny>7||vis[nx][ny]==1) continue;
		vis[nx][ny]=1;
		dfs(nx,ny);
		vis[nx][ny]=0;
	}
}
signed main(){
	for(int i=0;i<=7;i++){
		memset(vis,0,sizeof(vis));
		dfs(i,i);
	}
	cout<<ans;
}

答案为 \(2444\)。

试题 \(\mathrm{D}\) : 求值

从 \(101\) 一直枚举到第一次出现 \(100\) 个因数的数字。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	for(int i=101;1==1;i++){
		int ans=0;
		for(int j=1;j*j<=i;j++){
			if(i%j==0){
				if(i/j!=j) ans+=2;
				else ans++;
			}
		}
		if(ans==100){
			cout<<i;
			return 0;
		}
	}
}

答案为 \(45360\)。

试题 \(\mathrm{E}\) : 路径计数

从 \((0,0)\) 暴搜正方形，和 \(\mathrm{C}\) 题相似。

• 注意，不自交最少要走 \(4\) 步，判断步数时应为 \(k\ge4\)。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int ans=0;
bool vis[7][7]; 
void dfs(int x,int y,int k){
	if(k>12) return;
	if(k>=4&&x==0&&y==0){
		ans++;
		return;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<0||ny<0||nx>5||ny>5||vis[nx][ny]) continue;
		vis[nx][ny]=1;
		dfs(nx,ny,k+1);
		vis[nx][ny]=0;
	}
}
signed main(){
	dfs(0,0,0);
	cout<<ans;
	return 0;
}

答案为 \(206\)。

本题的 AC code

#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "7020", 
        "55965365465060", 
        "2444",
        "45360",
        "206",
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}