http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1250
Super Fast Fourier Transform
Bobo has two sequences of integers
{
a
1
,
a
2
,
…
,
a
n
}
and
{
b
1
,
b
2
,
…
,
b
m
}
. He would like to find
∑
i
=
1
n
∑
j
=
1
m
⌊
|
a
i
−
b
j
|−−−−−−−√
⌋
.
Note that
⌊
x
⌋
denotes the maximum integer does not exceed
x
, and
|
x
|
denotes the absolute value of
x
.
Input
The input contains at most
30
sets. For each set:
The first line contains
2
integers
n
,
m
(
1
≤
n
,
m
≤
10
5
).
The second line contains
n
integers
a
1
,
a
2
,
…
,
a
n
.
The thrid line contains
m
integers
b
1
,
b
2
,
…
,
b
m
.
(
a
i
,
b
i
≥
0
,
a
1
+
a
2
+
⋯
+
a
n
,
b
1
+
b
2
+
…
,
b
m
≤
10
6
)
Output
For each set, an integer denotes the sum.
Sample Input
1 2 1 2 3 2 3 1 2 3 4 5
Sample Output
2 7
不得不说自己笨，这么简单，当时就是不会
题意：n个a,m个b的相乘的累积和
思路：把重复的a和b找出了，会减少很大的复杂度
1 #include <stdio.h> 2 #include <math.h> 3 #include <string.h> 4 #include <stdlib.h> 5 6 int a[100005],b[100005],suma[1000005],sumb[1000005]; 7 long long ans; 8 9 int main() 10 { 11 int m,n,acut,bcut,tmp; 12 while(~scanf("%d%d",&m,&n)) 13 { 14 acut = 0,bcut = 0; 15 memset(suma,0,sizeof(suma)); 16 memset(sumb,0,sizeof(sumb)); 17 for(int i = 1;i<=m;i++) 18 { 19 scanf("%d",&tmp); 20 if(suma[tmp]==0) 21 a[acut++] = tmp; 22 suma[tmp]++; 23 } 24 for(int i = 1;i<=n;i++) 25 { 26 scanf("%d",&tmp); 27 if(sumb[tmp]==0) 28 b[bcut++] = tmp; 29 sumb[tmp]++; 30 } 31 ans = 0; 32 for(int i = 0;i<acut;i++) 33 for(int j = 0;j<bcut;j++) 34 { 35 ans+=(long long ) suma[a[i]]*sumb[b[j]]*(long long )(sqrt(abs(a[i]-b[j]))); 36 } 37 printf("%lld\n",ans); 38 } 39 return 0; 40 }
转载于:https://www.cnblogs.com/Tree-dream/p/6540096.html