[NOIP2021]方差 题解
2022/7/29 23:23:04
本文主要是介绍[NOIP2021]方差 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门QAQ
Preface
现在看来当时的我还是太菜了啊QAQ(虽然现在也很菜
Analysis
显然,原序列中每个数都减去同一个数后,方差也不会有任何改变。
为了方便,这里我们先让原式中每个 \(a_i\) 减去 \(a_1\)。
考虑将题中要求的这个式子化简(很简单,过程省去):
\[n\times \sum_{i=1}^n a_i^2-(\sum_{i=1}^na_i)^2 \]此时仍然找不到什么思路,因为题中这个操作非常迷惑。
不过观察到,\(a_i \gets a_{i-1}+a_{i+1}-a_i\) 后,\(a_{i-1},a_i,a_{i+1}\) 三项就有了公共项。
考虑差分一下寻找规律。令 \(d_i=a_i - a_{i-1}\)。
发现一次操作后 \(d_i=a_{i+1}-a_i,d_{i+1}=a_i-a_{i-1}\)。
可以发现,一次操作就是交换了 \((d_i,d_{i+1})\) 。那么我们可以通过不断交换随意重排这个序列。
但是这也是有条件的,我们重排是为了让序列的方差最小,这就需要一些处理手段了。
Lemma:满足题意的差分数组必然呈单谷状。
形式化的说,存在一点 \(k(1\le k\le n)\),满足 \(\forall i \in [1,k),d_i \ge d_{i+1}\) 且 \(\forall i \in [k,n),d_i \le d_{i+1}\)。
感性理解一下,这样构造就是使得 \(a\) 数组中的数值较为集中在平均值附近。
引用一下 这篇题解 的图:
这样构造出来的差分数组长这个样子,那么用前缀和求出原来的 \(a\) 数组就是:
根据初中数学的知识,方差越小,代表着一个序列的「波动」越小,也就是离平均值更近。
显然这样构造是很优秀的,但怎么说明这样就是最优的呢?
证明:
(注:以下均是我从另一篇博客找来的极不严谨较容易理解的方法,严谨的数学证明请看其它博客)
考虑邻项交换。只考虑 \(\ge k\) 的部分,\(\lt k\) 的部分也是同理。
考虑交换 \((d_x,d_{x+1})(x \ge k)\),显然这只会让原序列中的 \(a_x\) 变大。
但这会导致我们的 \(\bar{a}\) 一起变大,还是不太好判断。
不如回到方差的定义,「波动」越大,方差越大,\(a_x\) 处于较大的一部分,它变大显然会让整个序列的「波动」变大,那么方差也会变大。
(这个解释好牵强QAQ,考场上还是推一推样例找性质,然后打个暴力对拍吧qwq)
有了这个性质,开始设计算法:
将 \(d\) 数组从小到大排序,依次插入新的差分序列的头或尾,显然这样是满足单谷的要求的。
现在要做的是判断是插入序列头还是序列尾部。
状态很多,又是最优化,考虑 DP。
设 \(f(i,j)\) 表示将前 \(d_1\sim d_i\) 插入序列,\(\sum a_i=j\) 时最小的 \(\sum a_i^2\)。
分情况讨论:
-
插入序列头:\(f(i,j) = f(i-1,j - i\times d_i)+ i\times d_i^2+2\times (j-i\times d_i)\times d_i\)。
-
插入序列尾:\(f(i,j)=f(i-1,j-\sum\limits_{k=1}^i d_k)+ j\times j\)。
此时还有一个问题:这个 DP 时空复杂度均为 \(O(N^2\times \max\{a_i\})\),被数据范围卡住了。
空间可以用滚动数组优化,那时间呢?
观察最后一组数据,\(N\) 非常大,但 \(a_i\) 非常小,说明我们的 \(d\) 数组中存在相当多的 \(0\)。
那么我们遇到 \(0\) 直接跳过就好了。计入时间复杂度的循环就只有 \(O(\max\{a_i\})\) 轮。
此时时间复杂度降到 \(O(N\times \max\{a_i\}^2)\),可以通过本题。
Code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e4 + 5; const int maxm = 605; const ll INF = 1e16; int n,a[maxn],d[maxn],sum[maxn]; ll f[2][maxn * maxm]; int main() { freopen("variance.in","r",stdin); freopen("variance.out","w",stdout); scanf("%d",&n); int m = n - 1; for(int i = 1;i <= n;++ i)scanf("%d",&a[i]); for(int i = 1;i <= m;++ i)d[i] = a[i + 1] - a[i]; sort(d + 1 , d + m + 1); for(int i = 1;i <= m;++ i)sum[i] = sum[i - 1] + d[i]; for(int i = 0;i <= m * sum[m];++ i)f[0][i] = INF; f[0][0] = 0; bool u = false; for(int i = 1;i <= m;++ i) { if(!d[i])continue ; u ^= true; for(int j = 0;j <= sum[m] * m;++ j) { f[u][j] = INF; if(j >= d[i] * i)f[u][j] = min(f[u][j] , f[u ^ 1][j - i * d[i]] + 1ll * i * d[i] * d[i] + 2ll * (j - i * d[i]) * d[i]); if(j >= sum[i])f[u][j] = min(f[u][j] , f[u ^ 1][j - sum[i]] + 1ll * sum[i] * sum[i]); } } ll ans = INF; for(int j = 0;j <= m * sum[m];++ j)ans = min(ans , 1ll * n * f[u][j] - 1ll * j * j); printf("%lld\n",ans); return 0; }
完结撒花✿✿ヽ(°▽°)ノ✿
这篇关于[NOIP2021]方差 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?