礼物「HNOI2017」

题目传送门

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有

但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的自然数

在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $xix_ixi，第二个手环的 iii 号位置装饰物亮度为 yiy_iyi，两个手环之间的差异值为（参见输入输出样例和样例解释）：$

sum_{i = 1}^n (x_i - y_i)^2​i=1​∑​n​​(x​i​​−y​i​​)​2​​

麻烦你帮他计算一下，进行调整（亮度改造和旋转），使得两个手环之间的差异值最小，这个最小值是多少呢？

输入数据的第一行有两个数

输出一个数，表示两个手环能产生的最小差异值。注意在将手环改造之后，装饰物的亮度可以大于

样例输入

5 6
1 2 3 4 5
6 3 3 4 5

样例输出

样例解释

需要将第一个手环的亮度增加

此时两个手环的亮度差异值为

对于 $30%30\%30% 的数据，n≤500,m≤10nle 500, mle 10n≤500,m≤10；对于 70%70\%70% 的数据，n≤5000nle 5000n≤5000；对于 100%100\%100% 的数据，1≤n≤50000,1≤m≤100,1≤ai≤m1le nle 50000, 1le mle 100, 1le a_ile m1≤n≤50000,1≤m≤100,1≤ai≤m。$

　　比较好想的就是先枚举断点，然后枚举要加上的数，最后求最小值，复杂度O（m*n^2），预计得分30.

　　稍微思考一下可以发现在断点相同时，差异值与加上的数呈二次函数关系，所以可以三分。复杂度降为O（n^2 * logm），预计得分70.

70分代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define LL long long
 7 #define RI register int
 8 using namespace std;
 9 const int INF = 0x7ffffff ;
10 const int N = 5000 + 10 ;
11 
12 inline int read() {
13     int k = 0 , f = 1 ; char c = getchar() ;
14     for( ; !isdigit(c) ; c = getchar())
15       if(c == '-') f = -1 ;
16     for( ; isdigit(c) ; c = getchar())
17       k = k*10 + c-'0' ;
18     return k*f ;
19 }
20 int n, m, ans = INF ; int a1[N], a2[N], xx[N], s2[N] ;
21 
22 inline int sqr(int x) { return x*x ; }
23 inline void solve1(int s) {
24     for(int i=1;i<=n;i++) a2[i] = i+s > n ? a1[i+s-n] : a1[i+s] ;
25     for(int i=1;i<=n;i++) xx[i] = a2[i]-s2[i] ;
26     int L = -m, R = m ;
27     while(L < R-2) {
28         int mid = (L+R)>>1, m1 = mid, m2 = mid+1 ;
29         int f1 = 0, f2 = 0 ;
30         for(int i=1;i<=n;i++) f1 += sqr(xx[i]+m1), f2 += sqr(xx[i]+m2) ;
31         if(f1 == f2) L = m1, R = m2 ;
32         else if(f1 < f2) R = m2 ;
33         else L = m1 ;
34     }
35     int mid = (L+R)>>1, m1 = mid, m2 = mid+1 ;
36     int f1 = 0, f2 = 0, f3 = 0, f4 = 0 ;
37     for(int i=1;i<=n;i++) {
38         f1 += sqr(xx[i]+m1), f2 += sqr(xx[i]+m2), f3 += sqr(xx[i]+L), f4 += sqr(xx[i]+R) ;
39     }
40     int minn = min(min(f1,f2),min(f3,f4)) ;
41     ans = min(minn,ans) ;
42 }
43 
44 int main() {
45     n = read(), m = read() ;
46     for(int i=1;i<=n;i++) a1[i] = read() ;
47     for(int i=1;i<=n;i++) s2[i] = read() ;
48     for(int i=1;i<=n;i++) solve1(i) ;
49     printf("%d
",ans) ;
50     return 0 ;
51 }

　　至于正解...

　　好像要用FFT，日后有机会学的话再更新吧。

礼物「HNOI2017」

题目传送门

题目描述

输入格式

输出格式

样例

样例输入

样例输出

样例解释

数据范围与提示

70分代码：