题目描述

“蓝桥杯”练习系统 (lanqiao.cn)

题目分析

首先想到的方法为dfs去寻找每一个数，但发现会有超时

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, cnt, a[N];
void dfs(int dep, int sum, int start)
{if(dep == 4){if(sum == 0 && cnt == 0){for(int i = 0; i < 4; i ++){cout << a[i] << ' ';}cnt ++;}return;}for(int i = start; i <= sqrt(sum); i ++){a[dep] = i;dfs(dep + 1, sum - (i * i), i);} 
}
int main()
{cin >> n;dfs(0, n, 0);return 0;
}

使用二分

先将后两个数确定，将其后两个数的平方和以及分别对应的数字存入结构体中，再一一枚举前两个数，二分出可以匹配的后两个数，确定出答案

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
int n, num;
struct node
{int ss, c, d;
}sum[N * 2];
bool cmp(node x, node y)
{if(x.ss != y.ss){return x.ss < y.ss;	} else{if(x.c != y.c){return x.c < y.c;}else{return x.d < y.d;}}
}
int main()
{cin >> n;for(int c = 0; c * c <= n; c ++){for(int d = c; c * c + d * d <= n; d ++){sum[num ++] = {c * c + d * d, c, d};}}sort(sum, sum + num, cmp);for(int a = 0; a * a <= n; a ++){for(int b = 0; a * a + b * b <= n; b ++){int t = n - a * a - b * b;int l = 0, r = num - 1;while(l < r){int mid = l + r >> 1;if(sum[mid].ss >= t)r = mid;else l = mid + 1;}if(sum[l].ss == t){cout << a << ' ' << b << ' ' << sum[l].c << ' ' << sum[l]. d;return 0;}} }return 0;
}