【BZOJ 4827】[HNOI2017] 礼物

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4827
神犇题解:https://blog.sengxian.com/solutions/hnoi-2017-day1

解题报告

这题怎么讲呢?如果你不知道循环卷积,那么你只有$70$分
比如说:我 _(:з」∠)_

百度百科上循环卷积这个词条的例题就是这题
所以知道循环卷积的定义,然后写一个$FFT$就可以了

Code

#include<bits/stdc++.h>
#define LL long long
#define CPL complex<double>
using namespace std;

const int N = 200000;
const int INF = 2e9;
const double EPS = 0.5;
const double PI = acos(-1);

int n,m,B,C,mx,len,tt,f[N],pos[N];
CPL a[N],b[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
} 

inline void FFT(CPL *arr, int ty) {
	for (int i=0;i<len;i++) {
		if (pos[i] < i) {
			swap(arr[pos[i]], arr[i]);
		}
	}
	for (int ll=1;ll<len;ll<<=1) {
		CPL wn(cos(PI/ll), sin(PI/ll)*ty);
		for (int i=0;i<len;i+=ll*2) {
			CPL w(1,0);
			for (int j=0;j<ll;j++,w=w*wn) {
				CPL tmp = arr[i+j+ll] * w;
				arr[i+j+ll] = arr[i+j] - tmp;
				arr[i+j] = arr[i+j] + tmp;
			}
		}
	}
	if (ty == -1) {
		for (int i=0;i<len;i++) {
			arr[i] /= len;
		}
	}
}

int main() {
	n = read(); m = read();
	for (int i=0,tmp;i<n;i++) {
		B += (tmp = read()) << 1;
		C += tmp * tmp;
		a[i] = CPL{tmp, 0};
	}
	for (int i=0,tmp;i<n;i++) {
		B -= (tmp = read()) << 1;
		C += tmp * tmp;
		b[n-i] = CPL{tmp, 0};
	}
	
	for (len=1,tt=-1;len<n*2;len<<=1,++tt);
	for (int i=1;i<len;i++) {
		pos[i] = pos[i>>1]>>1;
		if (i&1) {
			pos[i] |= 1 << tt;
		}
	}
	FFT(a, 1);
	FFT(b, 1);
	for (int i=0;i<len;i++) {
		a[i] = a[i] * b[i];
	}
	FFT(a, -1);
	for (int i=n;i<len;i++) {
		a[i%n] += a[i];
	}
	for (int i=0;i<n;i++) {
		f[i] = a[i].real() + EPS;
		mx = max(f[i], mx);
	}
	C = C - 2 * mx;
	int p1 = -1.0 * B / 2 / n + EPS;
	int p2 = -1.0 * B / 2 / n - EPS;
	printf("%d\n",min(p1*p1*n+B*p1, p2*p2*n+B*p2) + C);
	return 0;
}

28 thoughts to “【BZOJ 4827】[HNOI2017] 礼物”

  1. Hmm is anyone else experiencing problems with
    the images on this blog loading? I’m trying to determine if its a problem on my end
    or if it’s the blog. Any feed-back would be greatly appreciated.

  2. I don’t even know how I ended up here, but I thought this post was great.
    I don’t know who you are but definitely you’re going to a famous
    blogger if you are not already 😉 Cheers!

  3. It’s amazing to pay a quick visit this site and reading the views of all mates about this paragraph, while I am also eager of getting knowledge.

  4. Its like you read my mind! You seem to know so much about this,
    like you wrote the book in it or something. I think that you could do with a few
    pics to drive the message home a little bit, but instead of that, this is wonderful blog.
    A fantastic read. I will certainly be back.

  5. I like what you guys are usually up too. Such
    clever work and reporting! Keep up the terrific works guys I’ve included
    you guys to my own blogroll.

  6. Do you mind if I quote a few of your articles as long as I provide credit and sources back to your weblog? My blog is in the very same niche as yours and my users would genuinely benefit from a lot of the information you present here. Please let me know if this alright with you. Thank you!

  7. I was suggested this website by my cousin. I’m not sure whether this post is written by him as nobody else know such detailed
    about my difficulty. You are amazing! Thanks!

  8. Fantastic beat ! I would like to apprentice while you amend your
    web site, how can i subscribe for a blog website? The account aided
    me a acceptable deal. I had been a little bit acquainted of this your broadcast provided bright clear concept

  9. I am really enjoying the theme/design of your blog.
    Do you ever run into any internet browser compatibility problems?
    A small number of my blog readers have complained about my site not
    working correctly in Explorer but looks great in Opera.
    Do you have any advice to help fix this problem?

  10. Heya i’m for the primary time here. I found this board and I
    in finding It truly useful & it helped me out much. I hope to provide something again and aid others like you aided me.

  11. I seriously love your site.. Excellent colors & theme.
    Did you develop this site yourself? Please reply back as I’m wanting to create my own website and want to find out where you got this from or exactly what the theme is
    named. Appreciate it!

  12. I’m working on a new list. I’m hopeful that this one will be much bigger. I made some announcements about my future site plans.one will be much bigger. I made some announcements about my future site plans.I’m going to be adding some new stuff soon. You’ll definitely want to stay tuned for that.

  13. Hello just wanted to give you a quick heads up and let you know a few of the images aren’t loading properly. I’m not sure why but I think its a linking issue. I’ve tried it in two different browsers and both show the same results.

发表评论

电子邮件地址不会被公开。 必填项已用*标注