#1388 : Periodic Signal
描述
Profess X is an expert in signal processing. He has a device which can send a particular 1 second signal repeatedly. The signal is A0 ... An-1 under n Hz sampling.
One day, the device fell on the ground accidentally. Profess X wanted to check whether the device can still work properly. So he ran another n Hz sampling to the fallen device and got B0 ... Bn-1.
To compare two periodic signals, Profess X define the DIFFERENCE of signal A and B as follow:
You may assume that two signals are the same if their DIFFERENCE is small enough.
Profess X is too busy to calculate this value. So the calculation is on you.
输入
The first line contains a single integer T, indicating the number of test cases.
In each test case, the first line contains an integer n. The second line contains n integers, A0 ... An-1. The third line contains n integers, B0 ... Bn-1.
T≤40 including several small test cases and no more than 4 large test cases.
For small test cases, 0<n≤6⋅103.
For large test cases, 0<n≤6⋅104.
For all test cases, 0≤Ai,Bi<220.
输出
For each test case, print the answer in a single line.
- 样例输入
-
2
9
3 0 1 4 1 5 9 2 6
5 3 5 8 9 7 9 3 2
5
1 2 3 4 5
2 3 4 5 1 - 样例输出
-
80
0
这题啊，我觉得暴力可做，刚开始超时了，又做了一点优化还是不行啊。
然后我觉得这个k的取值，和排完序的前m项有很大的关系，然后取m在不超时和wa的范围之间。。。这个看运气，竟然AC了
我的思路是排序a， b数组，按住其中一个数组不动，在前m个数内，用a1的下标减去b的下标，取一个得到k的最大值就好
正规做法竟然是fft。。不会啊
我的方法是歪门邪道。。看看就好，不要采纳#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define RE(i, n) FOR(i, 1, n)
#define FORP(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i <(n); ++i)
#define SZ(x) ((int)(x).size )
#define ALL(x) (x).begin(), (x.end())
#define MSET(a, x) memset(a, x, sizeof(a))
using namespace std; typedef long long int ll;
typedef pair<int, int> P;
ll read() {
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'') {
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='') {
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
const double pi=.14159265358979323846264338327950288L;
const double eps=1e-;
const int mod = 1e9 + ;
const int INF = 0x3f3f3f3f;
const int MAXN = ;
const int xi[] = {, , , -};
const int yi[] = {, -, , }; int N, T;
ll a[], b[];
ll c[], d[];
struct asort {
int num;
ll date;
} sa[], sb[];
bool cmp(asort a, asort b) {
return a.date > b.date;
}
int main() {
//freopen("in.txt", "r", stdin);
int t, n, k;
scanf("%d", &t); while(t--) {
ll sum = ;
scanf("%d", &n); for(int i = ; i < n; i++) a[i] = read();
for(int i = ; i < n; i++) b[i] = read();
for(int i = n; i < *n ; i++) {
a[i] = a[i-n];
b[i] = b[i-n];
}
for(int i = ; i < n; i++) {
sum += a[i]*a[i];
sum += b[i]*b[i];
sa[i].num = i, sa[i].date = a[i];
sb[i].num = i, sb[i].date = b[i];
}
sort(sa, sa+n, cmp);
sort(sb, sb+n, cmp);
int m = min(n, );
ll res = ;
for(int ai = ; ai < m; ai++) {
ll ans = ;
int i = (sb[].num - sa[ai].num + n)%n;
for(int j = i; j < n+i; j++) {
ans += (a[j-i]*b[j]) <<;
}
if(ans > res) {
res = ans;
k = i;
}
}
printf("%lld\n", sum - res);
// printf("%d\n", k);
}
return ;
}