[BZOJ4827][Hnoi2017]礼物(FFT)
4827: [Hnoi2017]礼物
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1315 Solved: 915
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1 2 3 4 5
6 3 3 4 5
Sample Output
【样例解释】
需要将第一个手环的亮度增加1,第一个手环的亮度变为: 2 3 4 5 6 旋转一下第二个手环。对于该样例,是将第
二个手环的亮度6 3 3 4 5向左循环移动 2017-04-15 第 6 页,共 6 页 一个位置,使得第二手环的最终的亮度为
:3 3 4 5 6。 此时两个手环的亮度差异值为1。
HINT
Source
Solution
由于是多项式第一题所以抄的yyb的题解(说的像我后面就能自己做一样。。。)
为了方便,我们从0开始编号,然后答案就是下面这个式子
\[{\mathop{ \sum }\limits_{{i=0}}^{{n-1}}{\mathop{{{ \left( {\mathop{{x}}\nolimits_{{i}}\mathop{{-y}}\nolimits_{{i+k}}+c} \right) }}}\nolimits^{{2}}}}\]
其中${c}$的取值范围为${ \left[ {-m,m} \right] }$,因为一旦超过这个范围,$c+{\mathop{{y}}\nolimits_{{i}}}$的绝对值一定大于${\mathop{{x}}\nolimits_{{i}}}$的绝对值,这样把$c$+1或-1一定能使答案更小。
把答案式子拆开:
\[{{ \sum {\mathop{{\mathop{{x}}\nolimits_{{i}}}}\nolimits^{{2}}}}+{ \sum {\mathop{{\mathop{{y}}\nolimits_{{i}}}}\nolimits^{{2}}}-{2 \sum {\mathop{{x}}\nolimits_{{i\text{ }}}\mathop{{y}}\nolimits_{{i+k}}}+n\mathop{{c}}\nolimits^{{2}}+}}2c \left( { \sum {\mathop{{x}}\nolimits_{{i}}}-{ \sum {\mathop{{y}}\nolimits_{{i}}}}} \right) }\]
c可以枚举,所以除了${ \sum {\mathop{{x}}\nolimits_{{i\text{ }}}\mathop{{y}}\nolimits_{{i+k}}}}$都算常数项了,接下来考虑如何最大化${ \sum {\mathop{{x}}\nolimits_{{i\text{ }}}\mathop{{y}}\nolimits_{{i+k}}}}$
显然不能n^2暴力乘。我们把$x$看成一个多项式,把$y$ reverse一下,也看成一个多项式,然后做卷积,发现卷积后第n-1项的系数恰好就是${ \sum {\mathop{{x}}\nolimits_{{i\text{ }}}\mathop{{y}}\nolimits_{{i}}}}$。
解法呼之欲出:把$y$(reverse后的)复制一遍接在后面,然后跟$x$做卷积,那么卷积后第n-1+k项的系数就是${ \sum {\mathop{{x}}\nolimits_{{i\text{ }}}\mathop{{y}}\nolimits_{{i+k}}}}$。
//公式编辑得好累……
Code
#include<bits/stdc++.h>
using namespace std;
const int N=<<;
const double pi=acos(-1.0);
inline int read(){
int x=,w=;char ch=;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=getchar();
return w?-x:x;
}
struct cp{
double x,y;
cp(double xx=,double yy=):x(xx),y(yy){};
cp operator + (const cp &tmp)const{return cp(x+tmp.x,y+tmp.y);}
cp operator - (const cp &tmp)const{return cp(x-tmp.x,y-tmp.y);}
cp operator * (const cp &tmp)const{return cp(x*tmp.x-y*tmp.y,x*tmp.y+y*tmp.x);}
};
int n,m,ans,ss,sa[N],sb[N],rev[N],res[N];
cp a[N],b[N];
void fft(int n,cp a[],int fg){
for(int i=;i<n;++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int m=,len=m<<;m<n;m<<=,len<<=){
cp I=cp(cos(pi/m),fg*sin(pi/m));
for(int i=;i<n;i+=len){
cp w=cp(,),t;
for(int j=;j<m;++j,w=w*I)
t=a[i+j+m]*w,
a[i+j+m]=a[i+j]-t,
a[i+j]=a[i+j]+t;
}
}
}
void pre(){
for(int i=;i<n;++i) a[i].x=sa[i+],b[i].x=b[i+n].x=sb[n-i];
int lim=,l=;
while(lim<=(n*-)) lim<<=,++l;
for(int i=;i<lim;++i) rev[i]=(rev[i>>]>>)|((i&)<<(l-));
fft(lim,a,),fft(lim,b,);
for(int i=;i<lim;++i) a[i]=a[i]*b[i];
fft(lim,a,-);
for(int i=;i<lim;++i)
res[i]=(int)(a[i].x/lim+0.5);
}
int main(){
n=read(),m=read();
for(int i=;i<=n;++i){
sa[i]=read();
ans+=sa[i]*sa[i];
ss+=sa[i];
}
for(int i=;i<=n;++i){
sb[i]=read();
ans+=sb[i]*sb[i];
ss-=sb[i];
}
pre();
int tmp=;
for(int k=;k<n;++k) tmp=max(tmp,res[n-+k]);
ans-=(tmp<<);tmp=0x3f3f3f3f;
for(int c=-m;c<=m;++c) tmp=min(tmp,n*c*c+*c*ss);
cout<<ans+tmp<<endl;
return ;
}
BZOJ4827
最新文章
- 使用Spring和SpringMVC管理bean时要注意的一个小细节
- kendoTreeView,需要注意的地方
- mongkeyrunner实现循环随机输入值的方法
- 5----table类型
- Mybatis resultMap空值映射问题解决
- Apache日志不记录图片文件设置方法和来源日志的配置
- Truncating HTML attribute value in SharePoint DataFormWebPart
- Linux 之 rsyslog 系统日志转发(转载)
- perl 异步超时 打印错误
- freemarker自己定义标签(二)
- JavaEE——Intellij Idea 创建JavaWeb项目
- Android Matrix类以及ColorMatri
- QTP自动化测试培训:描述编程之WebElement
- Centos7 安装 scrapy
- SpringBoot项目打war包部署Tomcat教程
- python之第三方模块安装
- MySQL优化之like关键字
- Centos安装Oracle及问题处理
- Android超精准计步器开发-Dylan计步(申明:来源于网路)
- 洛谷P4198 楼房重建