HNOI2017 礼物

题目传送门

显然,我参加了这次HNOI。

然而并没有什么用,只拿了纯良心的70pts暴力。

30%的数据满足n≤500, m≤10;

70%的数据满足n≤5000;

100%的数据满足1≤n≤50000, 1≤m≤100, 1≤ai≤m。

并不知道在$30pts$ $m\le 10$的基础上,为什么$100 pts$ $m\le 100$,包括$70 pts$ $m\le 100$,然而后面两个部分分真的m可以开到很大。

题解

显然手环2亮度减c和手环1亮度+c是等价的,所以修改相当于在手环2亮度+c$(|c| \le m)$(显然)

假设下标从0开始到n-1(原题为从1到n)

30pts:枚举移动的位数,和c($O(n^2m)$)。

70pts:枚举移动的位数,移动过去后变成了一个求$\sum_{i=0}^{n-1}(s_i-c)^2$的最小值,其中$s_i=x_i-y_i$。

然后展开得$nc^2+\sum s_ic+\sum s_i^2$

然后就是求二次方程最小值,时间复杂度$O(1)$,总时间复杂度$O(n^2)$

当然还有C2016红太阳 huhao的$O(nm^2)$神奇算法

100pts:

显然$\sum_{i=0}^{n-1}s_i$是一个定值,$\sum_{i=0}^{n-1}s_i^2=\sum_{i=0}^{n-1}(x_i-y_i)^2=\sum_{i=0}^{n-1}(x_i^2+y_i^2-2x_iy_i)$,显然$\sum_{i=0}^{n-1}(x_i^2+y_i^2)$也是定值,为了结果尽量小,显然要$\sum_{i=0}^{n-1}2x_iy_i$尽量大 ,所以就是要求$\sum_{i=0}^{n-1}x_iy_i$的最大值。

设经过旋转,$x_0$转到了原来$x_k$的位置。

那么就变为$\sum_{i=0}^{n-k-1}x_{i+k}y_i+\sum_{i=0}^{k-1}x_iy_{n-k+i}$

设$x’$为x翻转后的序列,$y’$为y翻转后的序列。

则$\sum_{i=0}^{n-k-1}x_{i+k}y_i+\sum_{i=0}^{k-1}x_iy_{n-k+i}=\sum_{i=0}^{n-k-1}x’_{(n-k-1)-i}y_i+\sum_{i=0}^{k-1}x_iy’_{(k-1)-i}$

设$s=x’\times y$,$s’=x\times y’$则$\sum_{i=0}^{n-k-1}x_{i+k}y_i+\sum_{i=0}^{k-1}x_iy_{n-k+i}=s_{n-k-1}+s’_{k-1}$,就是FFT卷积取最小值。。

然后得到最小值后直接解方程就好,时间复杂度$O(n \log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
Author: CNYALI_LK
LANG: C++
PROG: 3723.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
template<class T>T read(){
T s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
// printf("%d\n",a);
int cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;a=-a;}
do{WriteIntBuffer[++cnt]=(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
putchar(end);
}
struct fs{
double x,y;
fs(double a=0.0,double b=0.0){x=a;y=b;}
fs operator +(fs b){return fs(x+b.x,y+b.y);}
fs operator -(fs b){return fs(x-b.x,y-b.y);}
fs operator *(fs b){return fs(x*b.x-y*b.y,x*b.y+y*b.x);}
fs operator /(double b){return fs(x/b,y/b);}
};
fs x[1<<17],y[1<<17],xr[1<<17],yr[1<<17],s1[1<<17],s2[1<<17];
int rev[1<<17];
int f(int x,int a,int b,int c){return x*(x*a+b)+c;}
void FFT(fs *a,int siz,int flg){
for(int i=0;i<siz;++i)if(i>rev[i])swap(a[i],a[rev[i]]);
for(int s=2;s<=siz;s<<=1){
int g=s>>1;
fs ww(cos(pi/g),flg*sin(pi/g));
for(int l=0;l<siz;l+=s){
fs w(1,0);
for(int i=0;i<g;++i){
fs u=a[l+i],v=a[l+i+g]*w;
a[l+i]=u+v;
a[l+i+g]=u-v;
w=w*ww;
}
}
}
if(flg<0)for(int i=0;i<siz;++i)a[i]=a[i]/siz;
}
int main(){
#ifdef cnyali_lk
freopen("3723.in","r",stdin);
freopen("3723.out","w",stdout);
#endif
int n,cnt=0,ccnt=0,ax,ay,M;
n=read<int>();M=read<int>();
for(int i=0;i<n;++i){
ax=read<int>();
x[i]=fs(ax);
xr[n-i-1]=x[i];;
cnt-=ax;
ccnt+=ax*ax;
}
for(int i=0;i<n;++i){
ay=read<int>();
y[i]=fs(ay);
yr[n-i-1]=y[i];;
cnt+=ay;
ccnt+=ay*ay;
}
cnt<<=1;
int m=n+n,s=1,t=0;
while(s<=m){s<<=1;++t;}
for(int i=0;i<s;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(t-1));

FFT(x,s,1);
FFT(y,s,1);
FFT(xr,s,1);
FFT(yr,s,1);
for(int i=0;i<s;++i)s1[i]=x[i]*yr[i];
for(int i=0;i<s;++i)s2[i]=y[i]*xr[i];
FFT(s1,s,-1);
FFT(s2,s,-1);
int ans=(int)(s2[n-1].x+0.5),Ans=0x3f3f3f3f;
for(int k=1;k<n;++k)chkmax(ans,(int)(s2[n-k-1].x+s1[k-1].x+0.5));
ccnt-=ans+ans;
// printf("%d_%d,%d,%d\n",ans,n,cnt,ccnt);
double x=-(cnt/2)*1./n;
/// write(f(-1,n,cnt,ccnt),'\n');
// printf("%lf\n",x);
write(min(f(floor(x),n,cnt,ccnt),f(ceil(x),n,cnt,ccnt)),'\n');

return 0;
}
# FFT

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×