22软工孟姿好

用户名：dotcpp0669285

访问量：740

签　名：

莫道桑榆晚，为霞尚满天

等　　级
排　　名	878
经　　验	3562
参赛次数	13
文章发表	47
年　　龄	20
在职情况	学生
学　　校	bilibili大学
专　　业	软件工程

　　自我简介：

自强不息

TA的其他文章

旧物有情 # 枚举法求素数
浏览：22

旧物有情 # 枚举法求水仙花数
浏览：14

旧物有情 # 遍历求二维数组转置
浏览：9

你可能喜欢

哈希法 # 2270: 蓝桥杯2016年第七届真题-四平方和(C++)

　　作者: 22软工孟姿好　　　　发表时间：2024-11-22 08:29:49 浏览：7　|　评论：0　

原题链接：蓝桥杯2016年第七届真题-四平方和

这道题显而易见的暴力思路就是三重for循环枚举所有情况

这里有一个全新的思路 => 哈希法

对于四个数字 a b c d (升序排序)

我们定义数组 C[S],D[S], 表示 能凑出平方和为S的 c 和 d 是多少
例如 C[18]=3，D[9]=3

由于一定有解,且一定满足 升序排序的关系

那么我们在枚举的时候优先枚举c 和 d(从小到大开始枚举),
这样搜索可以保持答案优先考虑较小的数据

```c++
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define MAX 0x3f3f3f3f
#define MIN -0x3f3f3f3f
using namespace std;
typedef long long ll;

const int N = 5e6 + 10;

int C[N], D[N];

int main() {
	int n;
	cin >> n;
	//由于搜索顺序从小到大,可能出现同一个s被多个c和d满足
	//这里我们只要更小的数据,即第一次满足的数据
	memset(C, -1, sizeof C);
	for (int c = 0; c * c <= n; c++) {
		for (int d = c; d * d + c * c <= n; d++) {
			int s = c * c + d * d;
			if (C[s] == -1) {
				C[s] = c, D[s] = d;
			}
		}
	}

for (int a = 0; a * a <= n; a++) {
		for (int b = a; a * a + b * b <= n; b++) {
			int s = n - a * a - b * b;
			if (C[s] != -1) {
				printf("%d %d %d %d", a, b, C[s], D[s]);
				return 0;
			}
		}
	}

return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

22软工孟姿好

TA的其他文章

你可能喜欢

弟弟的作业（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

哈希法 # 2270: 蓝桥杯2016年第七届真题-四平方和(C++)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

程序员的表白（C语言代码）

【回文数(二)】（C语言代码）

ASCII帮了大忙

计算质因子（C++代码）

三角形（C++代码）记忆化搜索

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

矩阵乘方（C语言代码）

输入输出格式练习（C语言代码）

22软工孟姿好

TA的其他文章

你可能喜欢

弟弟的作业 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

哈希法 # 2270: 蓝桥杯2016年第七届真题-四平方和(C++)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

程序员的表白 （C语言代码）

【回文数(二)】 （C语言代码）

ASCII帮了大忙

计算质因子 （C++代码）

三角形 （C++代码）记忆化搜索

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

矩阵乘方 （C语言代码）

输入输出格式练习 （C语言代码）

弟弟的作业（C语言代码）

　　评论区

程序员的表白（C语言代码）

【回文数(二)】（C语言代码）

计算质因子（C++代码）

三角形（C++代码）记忆化搜索

矩阵乘方（C语言代码）

输入输出格式练习（C语言代码）