AcWing 1221. 四平方和(带注释)
原题链接
简单
作者:
格子格子
,
2021-03-18 12:20:18
,
所有人可见
,
阅读 4589
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5 * 1e6;
struct Sum {
int s, c, d;
bool operator< (const Sum &t) const {
if (s != t.s) return s < t.s;
if (c != t.c) return c < t.c;
return d < t.d;
}
}S[N];
int n, m;
int main() {
cin >> n;
for (int c = 0; c * c <= n; ++c) {
for (int d = c; c * c + d * d <= n; ++d)
S[m++] = {c * c + d * d, c, d};
}
sort(S, S + m);
for (int a = 0; a * a <= n; ++a) {
for (int b = a; a * a + b * b <= n; ++b) {
int t = n - a * a - b * b;
int l = 0, r = m - 1;
while (l < r) {
int mid = l + r >> 1;
if (S[mid].s >= t) r = mid;
else l = mid + 1;
}
if (S[l].s == t) {
cout << a << " " << b << " " << S[l].c << " " << S[l].d << endl;
return 0;
}
}
}
return 0;
}
我感觉不用对d进行排序啊,综合相同,c还相同,那d不相同吗,相同为什么还排序呢
调试过了,是可以过的hh
if (S[mid].s >= t) r = mid;可以写成 <=吗?
应该是可以的,S[mid].s >= t 意思就是 t <= S[mid].s
不是,他的意思是if(S[mid].s<=t) l=mid;
else r=mid-1;
这个是不行的,可能有两个符合要求的,要输出靠左边的那一个,所以二分条件只能用(S[mid].s>=t)
这注释太棒啦!
大佬tal,爱了
tql
这个是怎么来保证a <= b <= c <= d 的呢?实在想不通
本来就从小到大进行枚举,所以找到符合的解就是字典序最小
l=mid+1二分是找同一个值的下界(最左侧元素),由于结构体已经按照c<d顺序排序了,找到了就是c<d的
大佬 是怎么确定cd和ab的字典序的呀
首先a和b的字典序可以确定的,a从0开始,b从a开始枚举,然后枚举c,d,当你找到cc+dd=n-aa-bb时,a和b一定是最小的那个组合,因为你想a和b都是从最小的开始枚举的,它们的顺序已经确定了,c和d就比较简单了,你已经对平方和相等的解进行了排序,然后对c和d分别进行排序即可
那为啥b <= c啊?
因为先遍历的c和d,都存在集合S中了,然后sort后,再寻找可行的方案中满足条件的最小的a和b,因此一定满足b <= c,反过来想,如果不满足的话说明b应该出现在cd的位置上,而不是满足条件的较小值a和b上。
这个是怎么来保证a <= b <= c <= d 的呢?
从大到小枚举的即可保证
t=n-aa-bb可以推出aa + bb + t = n ,然后 t = cc + dd
我现在重看一遍才发现(:
tql
牛皮