朝阳网站建设 慈云寺,移动端芯片综合性能排行榜,手机营销网站模板免费下载,看设计比较好的网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
首先可以知道#xff0c;我们对某个数组加上一个正数数的操作可以转换成对一个数组加上一个任意数#xff0c;所以我们设变化量为xxx。 对于∑i1n(ai−bi)2\sum_{i1}^n(a_i-b_i)^2i1∑n…传送门
文章目录题意思路题意 思路
首先可以知道我们对某个数组加上一个正数数的操作可以转换成对一个数组加上一个任意数所以我们设变化量为xxx。 对于∑i1n(ai−bi)2\sum_{i1}^n(a_i-b_i)^2i1∑n(ai−bi)2我们将变化量加入变成∑i1n(ai−bi−x)2\sum_{i1}^n(a_i-b_i-x)^2i1∑n(ai−bi−x)2考虑大力展开这个式子变成∑i1n(ai2bi2)nx22x∑i1n(bi−ai)−2∑i1naibi\sum_{i1}^n(a_i^2b_i^2)nx^22x\sum_{i1}^n(b_i-a_i)-2\sum_{i1}^na_ib_ii1∑n(ai2bi2)nx22xi1∑n(bi−ai)−2i1∑naibi 可以发现对于前部分就是一个关于xxx的二次函数比较容易处理最值的问题问题就转换成了∑i1naibi\sum_{i1}^na_ib_i∑i1naibi什么时候最大了。 对于这个问题考虑其很像卷积的形式所以套路的将aaa翻转变成∑i1nan−i1bi\sum_{i1}^na_{n-i1}b_i∑i1nan−i1bi由于我们旋转任意一个数组都是等价的这里选择旋转bbb数组我们破环成链将bbb扩展为[1,2n][1,2n][1,2n]此时设fn1k∑i1nan−i1bkif_{n1k}\sum_{i1}^na_{n-i1}b_{ki}fn1k∑i1nan−i1bki所以我们直接卷起来让后取[n1,2n][n1,2n][n1,2n]的最大值即可最后加上前部分的最小值就是答案啦。
// Problem: P3723 [AH2017/HNOI2017]礼物
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3723
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N],b[N];struct FFT {double PIacos(-1);int rev[N];int bit,limit;struct Complex {double x,y;void init() { xy0; }Complex operator (const Complex t) const { return {xt.x,yt.y}; }Complex operator - (const Complex t) const { return {x-t.x,y-t.y}; }Complex operator * (const Complex t) const { return {x*t.x-y*t.y,x*t.yy*t.x}; } }a[N];void init(int n,int m) {int xmax(n,m)*2; bit0;while((1bit)x) bit;limit1bit;for(int i0;ilimit;i) rev[i](rev[i1]1)|((i1)(bit-1));}void fft(Complex a[],int inv) {for(int i0;ilimit;i) if(irev[i]) swap(a[i],a[rev[i]]);for(int mid1;midlimit;mid1) {Complex w1Complex({cos(PI/mid),inv*sin(PI/mid)});for(int i0;ilimit;imid*2) {Complex wkComplex({1,0});for(int j0;jmid;j,wkwk*w1) {Complex xa[ij],ywk*a[ijmid];a[ij]xy; a[ijmid]x-y;}}}if(inv-1) {for(int i0;ilimit;i) {a[i].x/limit;a[i].y/limit;}}}int solve(int *ans,int *x,int n,int *y,int m) {for(int i0;in;i) a[i].xx[i];for(int i0;im;i) a[i].yy[i];init(n,m); fft(a,1); for(int i0;ilimit;i) a[i]a[i]*a[i];fft(a,-1);for(int i0;inm;i) ans[i](int)(a[i].y/20.5);for(int i0;ilimit;i) a[i].init();return nm;}}FT;int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);int sum10,sum20;for(int i1;in;i) scanf(%d,a[i]),sum1a[i]*a[i],sum2-a[i];for(int i1;in;i) scanf(%d,b[i]),b[in]b[i],sum1b[i]*b[i],sum2b[i];reverse(a1,a1n);int lenFT.solve(a,a,n,b,2*n);int mx0;for(int in1;in*21;i) mxmax(mx,a[i]);int ansINF;for(int i-m*2;im*2;i) ansmin(ans,sum1n*i*i2*i*sum2-2*mx);coutansendl;return 0;
}
/**/
