博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷P3723 [AH2017/HNOI2017]礼物(FFT)
阅读量:5849 次
发布时间:2019-06-19

本文共 1893 字,大约阅读时间需要 6 分钟。

 

首先,两个数同时增加自然数值相当于只有其中一个数增加(此增加量可以小于0)

我们令$x$为当前的增加量,${a},{b}$分别为旋转后的两个数列,那么$$ans=\sum_{i=1}^n(a_i+x-b_i)^2$$

然后把第$i$项提出来并展开,可得$$(a_i+x-b_i)^2=a_i^2+b_i^2+x^2+2xa_i-2xb_i-2a_ib_i$$

那么答案就是$$ans=\sum_{i=1}^na_i^2+\sum_{i=1}^nb_i^2+nx^2+2x(\sum_{i=1}^na_i+\sum_{i=1}^nb_i)-2\sum_{i=1}^na_ib_i$$

然后发现,答案里面只有最后一项与$a,b$的顺序有关(也就是旋转成了什么样子),前面的项都是常数(对同一个$x$来说),那么我们只要令$\sum_{i=1}^na_ib_i$最大就能让答案最小了

我们考虑一下,如果把数列$b$给反过来,那么最后一项就变成了$\sum_{i=1}^na_ib_{n-i+1}$,这是一个卷积的形式,可以直接用FFT计算1$项的系数)

那么我们把数列$b$反过来,然后把数列$a$倍长,那么两式卷积之后第$n+1$到第$2n$项里面最大值就是最大的$\sum_{i=1}^na_ib_i$

于是只要枚举一下$x$和旋转(多项式的第几项)就好了

1 //minamoto 2 #include
3 #include
4 #include
5 #define ll long long 6 #define inf 0x3f3f3f3f3f3f3f3f 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf;10 template
inline bool cmin(T&a,const T&b){
return a>b?a=b,1:0;}11 inline int read(){12 #define num ch-'0'13 char ch;bool flag=0;int res;14 while(!isdigit(ch=getc()))15 (ch=='-')&&(flag=true);16 for(res=num;isdigit(ch=getc());res=res*10+num);17 (flag)&&(res=-res);18 #undef num19 return res;20 }21 const int N=400005;const double Pi=acos(-1.0);22 struct complex{23 double x,y;24 complex(double xx=0,double yy=0){x=xx,y=yy;}25 inline complex operator +(complex b){
return complex(x+b.x,y+b.y);}26 inline complex operator -(complex b){
return complex(x-b.x,y-b.y);}27 inline complex operator *(complex b){
return complex(x*b.x-y*b.y,x*b.y+y*b.x);}28 }A[N],B[N];29 int n,m,l,r[N],limit=1,a[N],b[N];ll a1,a2,b1,b2,ans=inf;30 void FFT(complex *A,int type){31 for(int i=0;i
>1]>>1)|((i&1)<<(l-1));56 FFT(A,1),FFT(B,1);57 for(int i=0;i

 

转载于:https://www.cnblogs.com/bztMinamoto/p/9745089.html

你可能感兴趣的文章
Facebook广告平台遭遇8小时服务中断,或对黑色星期五购物节造成影响
查看>>
Uber开源基于web的自主可视化系统,可共享数据
查看>>
KubeEdge:开源的Kubernetes原生边缘计算框架
查看>>
IBM在2016年将拓展其云数据分析服务业务
查看>>
为解决跨越式增长障碍,“增长王者”都做对了些啥?
查看>>
比拼三大移动端深度学习框架,小米MACE有哪些优势?
查看>>
腾讯副总裁曾宇:谈谈腾讯的技术价值观与技术人才修炼
查看>>
机器学习研究的七个迷思
查看>>
时序数据库DolphinDB和TimescaleDB 性能对比测试报告
查看>>
Dependabot:自动创建GitHub PR修复潜在漏洞
查看>>
专访李峰:行进中的平安金融云
查看>>
苏宁 11.11:仓库内多 AGV 协作的全局路径规划算法研究
查看>>
浅析MySQL JDBC连接配置上的两个误区
查看>>
数据库管理工作如何适应DevOps实践
查看>>
git笔记
查看>>
黑盒测试用例设计中划分等价法详解
查看>>
关于weex
查看>>
Vue的缓存算法—LRU算法
查看>>
七牛云存储常见问题整理
查看>>
Handler 系列一:如何使用
查看>>