计科余定成

暴力搜索56分
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n;
vector<int>v(1);
void init() {
	for (int i = 1; pow(i, 2) <= n; i++) {
		v.push_back(pow(i, 2));
	}
}
int a[10];
int t = 1;
void dfs(int sum, int k, int pre) {
	if (t == 0) return;
	if (sum > n || k > 4) return;
	if (sum == n && k == 4 && t == 1) {
		t = 0;
		for (int i = 0; i < 4; i++) cout << a[i] << ' ';
		return;
	}
	for (int i = pre; i < v.size(); i++) {
		a[k] = i;
		dfs(sum + v[i], k + 1, i);
	}
}
int main() {
	cin >> n;
	init();
	dfs(0, 0, 0);
	return 0;
}
```
搜索剪枝78分
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n;
vector<int>v(1);
void init() {
	for (int i = 1; pow(i, 2) <= n; i++) {
		v.push_back(pow(i, 2));
	}
}
int a[5];
int find(int s) {
	int l = 0, r = v.size() - 1;
	int mid;
	while (l <= r) {
		mid = l + (r - l) / 2;
		if (s + v[mid] > n) r = mid - 1;
		else l = mid + 1;
	}
	return l - 1;
}
void dfs(int sum, int k, int pre) {
	if (sum > n) return;
	if (k == 4) {
		if (sum == n) {
			for (int i = 0; i < 4; i++) cout << a[i] << ' ';
			exit(0);
		} else return;
	}
	if (k == 3) {
		a[k] = find(sum);
		dfs(sum + v[a[k]], k + 1, 0);
	}
	for (int i = pre; i < v.size(); i++) {
		if (k < 3) {
			a[k] = i;
			dfs(sum + v[i], k + 1, i);
		}
	}
}
int main() {
	cin >> n;
	init();
	dfs(0, 0, 0);
	return 0;
}
```
哈希数组AC
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
int n;
vector<int>v(1);
int c[N], d[N];
void init() {
	memset(c, -1, sizeof(c));
	for (int i = 1; i * i <= 2 * n; i++) {
		v.push_back(i * i);
	}
	for (int i = 0; v[i] <= n; i++) {
		for (int j = i; v[i] + v[j] <= n; j++) {
			int sum = v[i] + v[j];
			if (c[sum] == -1) {
				c[sum] = i;
				d[sum] = j;
			}
		}
	}
}
int main() {
	cin >> n;
	init();
	int res;
	for (int i = 0; v[i] <= n; i++) {
		for (int j = i; v[i] + v[j] <= n; j++) {
			res = n - v[i] - v[j];
			if (c[res] != -1) {
				cout << i << ' ' << j << ' ';
				cout << c[res] << ' ' << d[res];
				return 0;
			}
		}
	}
	return 0;
}
```

0.0分

2 人评分

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

计科余定成

TA的其他文章

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

点我有惊喜！你懂得！

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

蓝桥杯2016年第七届真题-四平方和

评论区

精彩推荐

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

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

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

字符串对比（C语言代码）

printf基础练习2 （C语言代码）

简单的a+b （C语言代码）

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

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

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

Hello, world! （C语言代码）

计科余定成

TA的其他文章

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

点我有惊喜！你懂得！

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

蓝桥杯2016年第七届真题-四平方和

评论区

精彩推荐

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

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

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

字符串对比 （C语言代码）

printf基础练习2 （C语言代码）

简单的a+b （C语言代码）

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

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

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

Hello, world! （C语言代码）

　　评论区

字符串对比（C语言代码）