手机版网站建设费用清单,怎样做企业网站备案,常见o2o电商平台有哪些,电子商务网站有哪些类型题目描述 我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了#xff0c;他决定买一对情侣手环#xff0c;一个留给自己#xff0c;一个送给她。每个手环上各有 n 个装饰物#xff0c;并且每个装饰物都有一定的亮度。 但是在她生日的前一天#xff0c;我的室友突… 题目描述 我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了他决定买一对情侣手环一个留给自己一个送给她。每个手环上各有 n 个装饰物并且每个装饰物都有一定的亮度。 但是在她生日的前一天我的室友突然发现他好像拿错了一个手环而且已经没时间去更换它了他只能使用一种特殊的方法将其中一个手环中所有装饰物的亮度增加一个相同的自然数 c即非负整数。并且由于这个手环是一个圆可以以任意的角度旋转它但是由于上面装饰物的方向是固定的所以手环不能翻转。需要在经过亮度改造和旋转之后使得两个手环的差异值最小。 在将两个手环旋转且装饰物对齐了之后从对齐的某个位置开始逆时针方向对装饰物编号1,2,…,n其中 n 为每个手环的装饰物个数 第 1 个手环的 i 号位置装饰物亮度为 xi第 2 个手环的 i 号位置装饰物亮度为 yi两个手环之间的差异值为(参见输入输出样例和样例解释) \sum_{i1}^{n} (x_i-y_i)^2∑i1n(xi−yi)2 麻烦你帮他计算一下进行调整亮度改造和旋转使得两个手环之间的差异值最小这个最小值是多少呢 输入输出格式 输入格式 输入数据的第一行有两个数n, m代表每条手环的装饰物的数量为n每个装饰物的初始亮度小于等于m。 接下来两行每行各有n个数分别代表第一条手环和第二条手环上从某个位置开始逆时针方向上各装饰物的亮度。 输出格式 输出一个数表示两个手环能产生的最小差异值。注意在将手环改造之后装饰物的亮度 可以大于 m。 输入输出样例 输入样例#15 6
1 2 3 4 5
6 3 3 4 5 输出样例#11 说明 【样例解释】 需要将第一个手环的亮度增加1第一个手环的亮度变为 2 3 4 5 6 旋转一下第二个手环。对于该样例是将第二个手环的亮度6 3 3 4 5向左循环移动一个位置使得第二手环的最终的亮度为 3 3 4 5 6。 此时两个手环的亮度差异值为1 【数据范围】 30%的数据满足n≤500, m≤10 70%的数据满足n≤5000 100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。 题目可以转化为求Σ(xi-yid)^2的最小值.yi可以转n下. 把这个式子展开,Σxi^2Σyi^2n*d^2-Σ2xi*yiΣxi*dΣyi*d.可以发现,x,y的二次项为常量,和d有关的项为一个二次函数,剩下的就是Σxi*yi. 这个东西有n个不同的值,分别就是第二个数组转n下.可以把第二个数组翻转,然后就构造出了卷积,FFT后提取系数即可. 用complex时取real()然后取整要加0.5. 1 #includeset2 #includemap3 #includequeue4 #includestack5 #includectime6 #includecmath7 #includestring8 #includevector9 #includecstdio
10 #includecstdlib
11 #includecstring
12 #includeiostream
13 #includealgorithm
14 #includecomplex
15 #define LL long long
16 #define maxn 50000*4
17 using namespace std;
18 const double piacos(-1);
19 typedef complexdouble C;
20 C A[maxn],B[maxn];
21 int R[maxn],L0,n,nn,m;
22 LL sumx0,sumy0,pfx0,pfy0;
23 void FFT(C *k,int f){
24 for(int i0;in;i) if(iR[i]) swap(k[i],k[R[i]]);
25 for(int i1;in;i1){
26 C wn(cos(pi/i),f*sin(pi/i));
27 for(int j0;jn;j(i1)){
28 C w(1,0);
29 for(int p0;pi;p,w*wn){
30 C xk[jp],yw*k[jpi];
31 k[jp]xy;k[jpi]x-y;
32 }
33 }
34 }
35 if(f-1) for(int i0;in;i) k[i]/n;
36 }
37 LL jis(LL x){return nn*x*x2*(sumx-sumy)*x;}
38 void solve(){
39 LL x1(sumy-sumx)/nn;
40 LL x2x11,x3x1-1;
41 LL zxmin(jis(x1),min(jis(x2),jis(x3)));
42 LL zd-999999;
43 for(int i0;inn-1;i)
44 zdmax(zd,(LL)(A[i].real()0.5A[inn].real()));
45 zdmax(zd,(LL)(A[nn-1].real()));
46 printf(%lld,pfxpfyzx-2*zd);
47 }
48 int main()
49 {
50 int x;
51 scanf(%d%d,n,m),nnn;
52 n--;m2*n;
53 for(int i0;in;i) scanf(%d,x),A[i]x,sumxx,pfxx*x;
54 for(int in;i0;i--) scanf(%d,x),B[i]x,sumyx,pfyx*x;
55 for(n1;nm;n1) L;
56 for(int i0;in;i) R[i](R[i1]1)|((i1)(L-1));
57 FFT(A,1);FFT(B,1);
58 for(int i0;in;i) A[i]*B[i];
59 FFT(A,-1);
60 solve();
61 return 0;
62 } 转载于:https://www.cnblogs.com/pantakill/p/7282221.html
