北京道路建设在什么网站查询,网站建设有发展吗,零基础学编程,aso优化重要吗Description
我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了#xff0c;他决定买一对情侣手 环#xff0c;一个留给自己#xff0c;一个送给她。每个手环上各有 n 个装饰物#xff0c;并且每个装饰物都有一定的亮度。但是在她生日的前一天#xff0c;我的室…Description
我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了他决定买一对情侣手 环一个留给自己一个送给她。每个手环上各有 n 个装饰物并且每个装饰物都有一定的亮度。但是在她生日的前一天我的室友突然发现他好像拿错了一个手环而且已经没时间去更换它了他只能使用一种特殊的方法将其中一个手环中所有装饰物的亮度增加一个相同的自然数 c即非负整数。并且由于这个手环是一个圆可以以任意的角度旋转它但是由于上面 装饰物的方向是固定的所以手环不能翻转。需要在经过亮度改造和旋转之后使得两个手环的差异值最小。在将两个手环旋转且装饰物对齐了之后从对齐的某个位置开始逆时针方向对装饰物编号 1,2,…,n其中 n 为每个手环的装饰物个数第 1 个手环的 i 号位置装饰物亮度为 xi第 2 个手 环的 i 号位置装饰物亮度为 yi两个手环之间的差异值为(参见输入输出样例和样例解释) ∑i1n(xi−yi)2\sum_{i1}^{n}(x_i-y_i)^2∑i1n(xi−yi)2麻烦你帮他计算一下进行调整亮度改造和旋转使得两个手环之间的差异值最小 这个最小值是多少呢
Input 输入数据的第一行有两个数n, m代表每条手环的装饰物的数量为n每个装饰物的初始 亮度小于等于m。 接下来两行每行各有n个数分别代表第一条手环和第二条手环上从某个位置开始逆时 针方向上各装饰物的亮度。 1≤n≤50000, 1≤m≤100, 1≤ai≤m
Output 输出一个数表示两个手环能产生的最小差异值。 注意在将手环改造之后装饰物的亮度 可以大于 m。
Sample Input 5 6 1 2 3 4 5 6 3 3 4 5 Sample Output 1
【样例解释】 需要将第一个手环的亮度增加1第一个手环的亮度变为 2 3 4 5 6 旋转一下第二个手环。对于该样例是将第二个手环的亮度6 3 3 4 5向左循环移动 2017-04-15 第 6 页共 6 页 一个位置使得第二手环的最终的亮度为3 3 4 5 6。 此时两个手环的亮度差异值为1
solution
虽然题目说只能增加自然数ccc亮度 但是既可以是给第一个环加也可以是给第二个环加 所以转化为给固定一个环增加ccc亮度ccc可以是负数
假设枚举AAA环增加的亮度为xxx考虑最后的结果 ∑i1n(aix−bi)2∑i1n(ai2x2bi22aix−2aibi−2bix)\sum_{i1}^n(a_ix-b_i)^2\sum_{i1}^n(a_i^2x^2b_i^22a_ix-2a_ib_i-2b_ix)i1∑n(aix−bi)2i1∑n(ai2x2bi22aix−2aibi−2bix)∑i1nai2∑i1nbi2nx22x∑i1nai−2x∑i1nbi−2∑i1naibi\sum_{i1}^na_i^2\sum_{i1}^nb_i^2nx^22x\sum_{i1}^na_i-2x\sum_{i1}^nb_i-2\sum_{i1}^na_ib_ii1∑nai2i1∑nbi2nx22xi1∑nai−2xi1∑nbi−2i1∑naibi 发现只有最后一项2∑i1naibi2\sum_{i1}^na_ib_i2∑i1naibi可以改变 因为环可以旋转那么对应位的亮度乘积求和可能会不同 所以最大化该项就可以保证差异值最小
h(i)∑j0if(i)∗g(i−j)h(i)\sum_{j0}^if(i)*g(i-j)h(i)j0∑if(i)∗g(i−j) 将AAA环扩倍反转BBB环 使用FFTFFTFFT卷积这样AAA环的(n,2n](n,2n](n,2n]就是所有可能旋转的情况
code
#include cmath
#include cstdio
#include iostream
using namespace std;
#define maxn 300005
#define ll long long
struct complex {double x, i;complex(){}complex( double X, double I ) {x X, i I;}
}A[maxn], B[maxn], rB[maxn];double pi acos( -1.0 );complex operator ( complex a, complex b ) {return complex( a.x b.x, a.i b.i );
}complex operator - ( complex a, complex b ) {return complex( a.x - b.x, a.i - b.i );
}complex operator * ( complex a, complex b ) {return complex( a.x * b.x - a.i * b.i, a.x * b.i a.i * b.x );
}int len 1;
int r[maxn];void FFT( complex *c, int f ) {for( int i 0;i len;i )if( i r[i] ) swap( c[i], c[r[i]] );for( int i 1;i len;i 1 ) {complex omega( cos( pi / i ), f * sin( pi / i ) );for( int j 0;j len;j ( i 1 ) ) {complex w( 1, 0 );for( int k 0;k i;k , w w * omega ) {complex x c[j k], y w * c[j k i];c[j k] x y;c[j k i] x - y;}}}
}ll suma1, suma2, sumb1, sumb2;
int n, m;int main() {scanf( %d %d, n, m );for( int i 1;i n;i ) {scanf( %lf, A[i].x );A[i n].x A[i].x;suma1 A[i].x;suma2 A[i].x * A[i].x;}for( int i 1;i n;i ) {scanf( %lf, B[i].x );sumb1 B[i].x;sumb2 B[i].x * B[i].x;}for( int i 1;i n;i )rB[i].x B[n - i 1].x; int l 0;while( len n * 3 ) {len 1;l ;}for( int i 0;i len;i )r[i] ( r[i 1] 1 ) | ( ( i 1 ) ( l - 1 ) );FFT( A, 1 );FFT( rB, 1 );for( int i 0;i len;i )A[i] A[i] * rB[i];FFT( A, -1 );for( int i 0;i len;i )A[i].x ( ll ) ( A[i].x / len 0.5 );ll ans 1ll 60;for( int i 1;i n;i )for( int j -m;j m;j ) //初始的亮度都不超过m 那么就没必要把差x弄得太过火ans min( ans, suma2 sumb2 n * j * j 2ll * j * ( suma1 - sumb1 ) - 2ll * ( ll ) A[i n].x );printf( %lld, ans );return 0;
}
/*
Σ(aix-bi)^2Σai^2Σbi^2n*x*x2*x*(Σai-Σbi)-2*Σai*bi
因为旋转所以最后一项是不固定的
在枚举x后最大化后面一项
最后的相差就是最小的
考虑卷积
*/
