SP1296 SUMFOUR - 4 values whose sum is 0
传送门
考虑把A+B+C+D=0转换成−A−B=C+D,于是预处理出C+D的数组,sort一遍以后二分查找即可。
时间复杂度O(n2log(n2))(反正不会爆就是了)
我以前写的代码,码风可能有点清奇。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| #include <algorithm> #include <cstdio> #include <iostream> using namespace std; int A[4005], B[4005], C[4005], D[4005]; int SumCD[4005 * 4005]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { SumCD[i + j * n] = C[i] + D[j]; } } sort(SumCD, SumCD + n * n); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int find = A[i] + B[j]; ans += upper_bound(SumCD, SumCD + n * n, -find) - lower_bound(SumCD, SumCD + n * n, -find); } } printf("%d\n", ans); }
|
P1325 雷达安装
传送门
考虑只有一个点,一个雷达的时候,雷达在哪个区间才可以覆盖住这个点,
设dis=d2−y2dis=\sqrt{d^2-y^2}dis=d2−y2,发现只有在区间[x−dis,x+dis...
P2572 BZOJ1858 [SCOI2010]序列操作
洛谷
BZOJ
线段树维护,每个节点上面记录666个值l0,l1,r0,r1,m0,m1l0,l1,r0,r1,m0,m1l0,l1,r0,r1,m0,m1(套路),代表从左开始最长000的序列...