当前位置:网站首页>[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 .
边栏推荐
- Cost accounting [20]
- Cost accounting [13]
- Cost accounting [23]
- STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
- 【练习-1】(Uva 673) Parentheses Balance/平衡的括号 (栈stack)
- Accounting regulations and professional ethics [2]
- 基于web的照片数码冲印网站
- China earth moving machinery market trend report, technical dynamic innovation and market forecast
- Alice and Bob (2021牛客暑期多校训练营1)
- 渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
猜你喜欢
Ball Dropping
动态规划前路径问题优化方式
力扣刷题记录
Gartner:关于零信任网络访问最佳实践的五个建议
Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
洛谷P1102 A-B数对(二分,map,双指针)
信息安全-威胁检测引擎-常见规则引擎底座性能比较
X-Forwarded-For详解、如何获取到客户端IP
Information security - Analysis of security orchestration automation and response (soar) technology
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
随机推荐
Borg Maze (BFS+最小生成树)(解题报告)
HDU-6025-Coprime Sequence(女生赛)
力扣刷题记录--完全背包问题(一)
VS2019初步使用
Cost accounting [20]
0 - 1 problème de sac à dos (1)
渗透测试 ( 1 ) --- 必备 工具、导航
F - Birthday Cake(山东省赛)
Accounting regulations and professional ethics [5]
[exercise-7] crossover answers
【高老师UML软件建模基础】20级云班课习题答案合集
程序员的你,有哪些炫技的代码写法?
[analysis of teacher Gao's software needs] collection of exercises and answers for level 20 cloud class
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
Perform general operations on iptables
洛谷P1102 A-B数对(二分,map,双指针)
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
【练习-6】(PTA)分而治之
Cost accounting [14]
Cost accounting [15]