当前位置:网站首页>[exercise -11] 4 values why sum is 0 (and 4 values of 0)
[exercise -11] 4 values why sum is 0 (and 4 values of 0)
2022-07-06 15:57:00 【Flame car】
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).
The question :
Enter one per line a,b,c,d, Ask the input a[n],b[n],c[n],d[n] How many combinations can make a+b+c+d=0 establish .
The question is very simple .
First of all, we can definitely think of the enumeration of violence , four layers for loop , But it will obviously time out (4000^4).
This time , You can think of divide and conquer ( Turn the big problem into several small problems ). I can put a+b recorded , Then see if there is -c-d(a+b+c+d=0 ==> a+b = -c-d).
AC Code :
#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;
}
use scanf To prevent timeout ..
The most important thing here is to understand :
res += upper_bound(tmp,tmp+cnt,sum) - lower_bound(tmp,tmp+cnt,sum);
upper_bound Yes, return greater than ,lower_bound Is to return greater than or equal to . If this time is not equal to , Then it must be 0,(lower = upper = The first one is greater than sum Number of numbers ). But if there is equal to sum The number of will return its number .
You can use this to find The number of a certain number .
边栏推荐
- 【练习-2】(Uva 712) S-Trees (S树)
- China's peripheral catheter market trend report, technological innovation and market forecast
- Penetration test (3) -- Metasploit framework (MSF)
- Opencv learning log 19 skin grinding
- Cost accounting [13]
- 【练习-5】(Uva 839)Not so Mobile(天平)
- Record of force deduction and question brushing
- 渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
- The most complete programming language online API document
- Determine the Photo Position
猜你喜欢
Information security - threat detection - detailed design of NAT log access threat detection platform
Nodejs+vue网上鲜花店销售信息系统express+mysql
Nodejs+vue online fresh flower shop sales information system express+mysql
C语言必背代码大全
C语言数组的概念
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
STM32 how to use stlink download program: light LED running light (Library version)
STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
X-forwarded-for details, how to get the client IP
随机推荐
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
Find 3-friendly Integers
Opencv learning log 18 Canny operator
Cost accounting [22]
Learning record: STM32F103 clock system overview working principle
Research Report on market supply and demand and strategy of China's earth drilling industry
洛谷P1102 A-B数对(二分,map,双指针)
0-1背包问题(一)
Ball Dropping
Nodejs+vue online fresh flower shop sales information system express+mysql
[exercise-1] (UVA 673) parentheses balance/ balanced brackets (stack)
渗透测试 ( 4 ) --- Meterpreter 命令详解
MATLAB综合练习:信号与系统中的应用
Cost accounting [20]
C语言学习笔记
【练习-2】(Uva 712) S-Trees (S树)
Opencv learning log 32 edge extraction
HDU - 6024 Building Shops(女生赛)
数据在内存中的存储&载入内存,让程序运行起来
Opencv learning log 19 skin grinding