当前位置:网站首页>【练习-11】4 Values whose Sum is 0(和为0的4个值)
【练习-11】4 Values whose Sum is 0(和为0的4个值)
2022-07-06 09:26:00 【火焰车】
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×B×C×D are such that a+b+c+d=0. In the following, we assume that all lists have the same size n.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
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 test case, your program has to write the number quadruplets whose sum is zero.
The outputs of two consecutive cases will be separated by a blank line.
Samples
Input
1
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
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).
题意:
每行输入一个a,b,c,d,问输入的这些a[n],b[n],c[n],d[n]有多少种组合可以使a+b+c+d=0成立。
题意很简单。
首先我们肯定能想到的暴力枚举,四层for循环,但是很显然会超时(4000^4)。
这时间,可以想到分治(把大问题化成若干个小问题)。我可以先把a+b记录下来,然后看是否有-c-d(a+b+c+d=0 ==> a+b = -c-d)。
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define CLEAR(a) memset(a,0,sizeof a)
#define Clear(a) memset(a,-1,sizeof a)
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
ll a[4005],b[4005],c[4005],d[4005];
ll tmp[16000005];
int main()
{
int n,t;
ll res;
cin>>t;
while(t--)
{
while (~scanf("%d",&n))
{
res = 0;
for (int i = 0; i < n; i++)
scanf ("%lld%lld%lld%lld", &a[i], &b[i], &c[i], &d[i]);
int cnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
tmp[cnt++] = c[i] + d[j];
sort(tmp, tmp + cnt);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
ll sum =-a[i]-b[j];
res += upper_bound(tmp,tmp+cnt,sum) - lower_bound(tmp,tmp+cnt,sum);
}
printf ("%lld\n\n",res);
}
}
return 0;
}
用scanf是为了防止超时。。
这里最重要的是理解:
res += upper_bound(tmp,tmp+cnt,sum) - lower_bound(tmp,tmp+cnt,sum);
upper_bound是返回大于,lower_bound是返回大于等于。这时间如果没有等于的话,那么返回的一定是0,(lower = upper = 第一个大于sum的数)。但是如果有等于sum的数就会返回它的个数。
可以用这个来求某个数的个数。
边栏推荐
- 信息安全-威胁检测-flink广播流BroadcastState双流合并应用在过滤安全日志
- Flex --- detailed explanation of flex layout attributes
- mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
- 信息安全-威胁检测引擎-常见规则引擎底座性能比较
- Eslint--- error: newline required at end of file but not found (EOL last) solution
- VS2019初步使用
- LeetCode#412. Fizz Buzz
- 动态规划前路径问题
- 学习记录:TIM—基本定时器
- LeetCode#2062. Count vowel substrings in strings
猜你喜欢
Matlab comprehensive exercise: application in signal and system
学习记录:TIM—基本定时器
Learning record: how to perform PWM output
学习记录:使用STM32F1看门狗
程序员的你,有哪些炫技的代码写法?
Nodejs+vue网上鲜花店销售信息系统express+mysql
LeetCode#62. Different paths
Borg Maze (BFS+最小生成树)(解题报告)
Flex --- detailed explanation of flex layout attributes
B - 代码派对(女生赛)
随机推荐
力扣刷题记录--完全背包问题(一)
JS --- detailed explanation of JS DOM (IV)
LeetCode#2062. Count vowel substrings in strings
C语言数组的概念
Hospital privacy screen Industry Research Report - market status analysis and development prospect forecast
STM32 how to use stlink download program: light LED running light (Library version)
Research Report on market supply and demand and strategy of China's earth drilling industry
信息安全-威胁检测引擎-常见规则引擎底座性能比较
学习记录:USART—串口通讯
ucorelab3
LeetCode#204. Count prime
Cost accounting [13]
Indonesian medical sensor Industry Research Report - market status analysis and development prospect forecast
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
Interesting drink
0-1背包問題(一)
Cost accounting [22]
LeetCode#36. Effective Sudoku
ucore lab 6
LeetCode#268. Missing numbers