自动搬运

查看原文

来自洛谷，原作者为

	adminh 今年必拿√！else不改签|学术关私信开|暂退|红掉绿别Σ(っ °Д °;)っ

搬运于2025-08-24 22:41:30，当前版本为作者最后更新于2024-09-17 10:48:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：

搭配 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;
}

求管理员通过！