poj 2785 4 Values whose Sum is 0
Time Limit: 15000MS Memory Limit: 228000K Total Submissions: 21471 Accepted: 6469 Case Time Limit: 5000MS Description The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n . Input The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D . Output For each input file, your program has to write the number quadruplets whose sum is zero. Sample Input 6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45 Sample Output 5 Hint Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
折半枚举, 求四个和为0， 先将两个数组的和枚举保存然后排序（n2+ nlogn), 然后枚举另两个数组判断其和是否在前面的数组里（二分查找 n2log n）.
#include <iostream> #include <cstdio> #include<algorithm> using namespace std; const int N = 4001; int a[4][N]; int cd[N * N]; typedef long long ll; int main(int argc, char *argv[]) { int n; ll cnt = 0; //freopen("in.txt", "r", stdin); scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < 4; j++) { scanf("%d", &a[j][i]); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cd[i * n + j] = a[2][i] + a[3][j]; } } sort(cd, cd + n * n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int temp = -(a[0][i] + a[1][j]); cnt += upper_bound(cd, cd + n * n, temp) - lower_bound(cd, cd + n * n, temp); } } printf("%lld\n", cnt); return 0; }
poj 3061 Subsequence
Subsequence Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 14024 Accepted: 5930 Description A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S. Input The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file. Output For each the case the program has to print the result on separate line of the output file.if no answer, print 0. Sample Input 2 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5 Sample Output 2 3
1 尺取法，枚举序列的左右位置(N2)， 优化方法 若Q(i) = j是满足要求的起点为i的最小j， 则Q(i + 1) >= j, 所以尺取法不断变换终点即可（N).记得特判没有解的情况。
2或者S(i, j) = S(0, j) - S(0, i), 计算0到每个位置的序列和存起来(N)， 对每个起点用二分查找大于S的（NlogN）。
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; int main(int argc, char *argv[]) { int t, n, s; //freopen("in.txt", "r", stdin); scanf("%d", &t); while (t--) { scanf("%d %d", &n, &s); int * a = new int [n + 5]; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } int ans = n + 1; int sum = 0; int left = 0; int right = 0; while (true) { while (sum < s && right < n) { sum += a[right++]; } if (sum < s) { break; } ans = min(ans, right - left); sum -= a[left++]; } printf("%d\n", ans > n ? 0 : ans); } return 0;
原文：http://www.cnblogs.com/hxidkd/p/6671016.html
