dw建设网站步骤,睿思设计,免费发布招工的平台,wordpress默认主题怎么用四平方和 暴力做法
Y总暴力做法#xff0c;蓝桥云里能通过所有数据 总结#xff1a;暴力也分好坏#xff0c;下面这份代码就是写的好的暴力 如何写好暴力:1. 按组合枚举 2. 写好循环结束条件#xff0c;没必要循环那么多次 #includeiostream
#includecmath蓝桥云里能通过所有数据 总结暴力也分好坏下面这份代码就是写的好的暴力 如何写好暴力:1. 按组合枚举 2. 写好循环结束条件没必要循环那么多次 #includeiostream
#includecmathusing namespace std;int n;int main(){std::ios::sync_with_stdio(false);cin.tie(0);cinn;for(int a0;a*an;a)for(int ba;a*ab*bn;b)for(int cb;a*ab*bc*cn;c){int t(n-a*a-b*b-c*c);int dsqrt(t);if(d*dt){couta b c d ;return 0;}}return 0;
}我自己写的暴力做法只能过87.5% o(╥﹏╥)o
#includeiostream
#includecmathusing namespace std;int n;int main(){std::ios::sync_with_stdio(false);cin.tie(0);cinn;for(int a0;a*an;a)for(int b0;b*bn;b)for(int c0;c*cn;c)for(int d0;d*dn;d){if(a*ab*bc*cd*dn){couta b c d;return 0;}}return 0;
}分析
参考题解
这道题目最重要的思路是空间换时间这是算法竞赛里一个非常重要的思想 本来我们需要枚举 a b c d 四个数字因为第四个数字可以计算出来所以至少需要三重循环即 O(n3)但是这肯定是要超时的所以就想办法优化循环的次数
重点来了: 一个比较好的思路是把三重循环拆成两次二重循环。在第一次二重循环中计算一下c^2d^2,然后记录下来在第二次对a和b的循环中可以直接使用而不需要再次计算。如此一来时间复杂度就被大大的简化了。
至于如何记录 c^2d^2 则可以考虑使用哈希表或者数组二分的做法。不得不说实在是太巧妙了 二分做法
//四平方和
//二分
#includebits/stdc.husing namespace std;const int N 5e6 10;struct Sum{int s, c, d;// 下面这个重载用来解决按字典序输出的问题// 首先根据 c*cd*d排序为什么按c*cd*d排序呢// 因为我们的c是从小到大枚举d从c开始枚举也就是说我们的c和d是按字典序枚举的// 所以c*cd*d中的c和d一定是符合字典序的// 如果c*cd*d相同那么就比较c如果c*cd*d和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;}
}record[N * 2];int n;int main()
{cin n;int k 0;// 用来记录结构体数组里的元素个数(也就是说record里有多少个元素)// 预处理(其实就是打表)for(int c 0; c * c n; c){for(int d c; c * c d * d n; d ){record[k] {c * c d * d, c, d};}}// 排序sort(record, record k);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;// k表示record里的元素个数int l 0, r k - 1;while(l r){int mid l r 1;if(record[mid].s t) r mid;else l mid 1;}if(record[l].s t){printf(%d %d %d %d\n, a, b, record[l].c, record[l].d);return 0;}}}return 0;
} 哈希做法
使用C自带的unordered_map过不了不过模拟哈希表却可以过。
#includeiostream
#includecstring
#includealgorithmusing namespace std;// 开放地址法的N一般为原先的两倍在本题应该为2*5e6
// 但这里我怕爆内存只好跟原来一样了
// 注意N得为质数,5e6的质数为5e611
/* 求质数的代码for(int i5e6;;i){bool flagtrue;for(int j2;j*ji;j){if(i%j0){flagfalse;break;}if(flag){coutiendl;break;}}}*/
const int N5e611,null0x3f3f3f3f;int h[N];typedef pairint,int PII;PII s[N];int n;int find(int x){int k(x%NN)%N;while(h[k]!nullh[k]!x){k;}return k;}int main(){cinn;memset(h,null,sizeof h);// 打表for(int c0;c*cn;c)for(int dc;c*cd*dn;d){int kfind(c*cd*d);if(h[k]null) {h[k]c*cd*d;s[k].firstc,s[k].secondd;}}for(int a0;a*an;a)for(int ba;a*ab*bn;b){int tn-a*a-b*b;int kfind(t);if(h[k]!null){couta b s[k].first s[k].second;return 0;}}return 0;
}
