原题链接
题目描述：给定5个集合，从每个集合中选一个数，使得5个数的和为0.
输入格式：第一行：一个整数t表示数据组数。 接下来t组数据，每组数据第一行一个整数表示集合的大小。 接下来5行，每行n个数表示集合中的i元素。
输出格式：对于每组数据，输出Yes或No表示是否可以使数的和为0.
输入样例： 2 2 1 -1 1 -1 1 -1 1 -1 1 -1 3 1 2 3 -1 -2 -3 4 5 6 -1 3 2 -4 -10 -1
输出样例： No Yes
解析：一看到题目，n^5进行枚举肯定不可取。 那么先n^2预处理前2个集合数的和，经行hash，后n^3枚举后三行，在hash表中查。 似乎可行，于是便开打。 一提交，TLE了。 进行一波卡常，还是TLE了。 那么这么做不可行吗？可行！网上也有许多大佬用这方法A了此题。可能是本蒟蒻太弱，常数太大... 这里介绍用two pointers做的做法。 首先把前两个集合中的数两两相加，再将第3与4个集合中的数两两相加，得到两个数组。 将两个数组都从小到大sort一次。 枚举第5个集合中的数，对于集合中的每个数，创建l，r两个指针，分别指向两个数组其中一个的头与另一个的尾。 若三个数相加>0，则将尾的指针向左移一位。 若<0，则将头的指针向右移一位。 若=0则输出Yes，直接退出。 若不能得出0，则输出No。 一个比较巧妙的做法，无法理解的话可以画个图自行理解理解。 时间复杂度O(n^3)。
代码如下：
#include<cstdio> #include<algorithm> #define ll long long #define rint register int using namespace std; const int maxn = 205; int t, n, tot; ll a[6][maxn], b[maxn * maxn], c[maxn * maxn]; ll read(void) { char c; while (c = getchar(), (c < '0' || c > '9') && c != '-'); ll x = 0, y = 1; if (c == '-') y = -1; else x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x * y; } int main() { t = read(); rint i, j; while (t --) { n = read(); for (i = 1; i <= 5; ++ i) for (j = 1; j <= n; ++ j) a[i][j] = read(); tot = 0; for (i = 1; i <= n; ++ i) //构建第一个数组 for (j = 1; j <= n; ++ j) b[++ tot] = a[1][i] + a[2][j]; tot = 0; for (i = 1; i <= n; ++ i) //构建第二个数组 for (j = 1; j <= n; ++ j) c[++ tot] = a[3][i] + a[4][j]; sort(b + 1, b + 1 + n * n); //排序 sort(c + 1, c + 1 + n * n); int flag = 0; for (i = 1; i <= n; ++ i) { int l = 1, r = n * n; if (flag) break; for (j = 1; j <= n * n * 2; ++ j) { //一共要进行n*n*2次移动 ll val = a[5][i] + b[l] + c[r]; if (val == 0) { flag = 1; break; } else if (val > 0) r --; else l ++; } } if (flag) puts("Yes"); else puts("No"); } return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10372105.html
