现代锦州网站建设,windows建立网站,蒙古文网站建设汇报,网站图片优化的概念一、题目大意
从四个数组A[ ],B[ ],C[ ],D[ ]中分别取一个元素a b c d#xff0c;使得 a b c d 0#xff0c;找出所有a b c d 的解的数量#xff0c;认为下标不同#xff0c;但值相同的元素为不同元素。
二、解题思路
如果暴力枚举#xff0c;一定超时#xff0c;…一、题目大意
从四个数组A[ ],B[ ],C[ ],D[ ]中分别取一个元素a b c d使得 a b c d 0找出所有a b c d 的解的数量认为下标不同但值相同的元素为不同元素。
二、解题思路
如果暴力枚举一定超时所以我们把A[i]B[i]的所有n*n种排列放在ab数组中把C[i]D[i]的所有n*n中排列放在cd数组中然后把cd数组排序二分从cd数组中查找-ab[i]的所有值即可。
二分时可以使用0x3f3f3f3f给cd数组第n*n1个元素赋值便于二分兜底。如果lower_bound查出的值与-ab[i]相等则将upper_bound-lower_bound的值加给result
最后输出result即可题目比较简单在《挑战程序设计》上也可以找到就不再过多的赘述了。
三、代码
#include iostream
#include algorithm
using namespace std;
int a[4007], b[4007], c[4007], d[4007], ab[16000007], cd[16000007], n, inf 0x3f3f3f3f;
void input()
{for (int i 0; i n; i){scanf(%d%d%d%d, a[i], b[i], c[i], d[i]);}
}
void preHandle()
{for (int i 0; i n; i){for (int j 0; j n; j){ab[i * n j] a[i] b[j];cd[i * n j] c[i] d[j];}}sort(cd, cd n * n);cd[n * n] inf;
}
void solve()
{int result 0;for (int i 0; i n * n; i){int abSum ab[i];int cdSum 0 - abSum;int startIdx lower_bound(cd, cd n * n 1, cdSum) - cd;int endIdx upper_bound(cd, cd n * n 1, cdSum) - cd;if (cd[startIdx] ! cdSum){continue;}result (endIdx - startIdx);}printf(%d\n, result);
}
int main()
{while (~scanf(%d, n)){input();preHandle();solve();}return 0;
}
