方差
\(wait\) \(to\) \(finish\)
关luogu多少不人道了,我在哪儿刷题啊
题面
[NOIP2021] 方差
题目描述
给定长度为 \(n\) 的非严格递增正整数数列 \(1 \le a_1 \le a_2 \le \cdots \le a_n\)。每次可以进行的操作是:任意选择一个正整数 \(1 < i < n\),将 \(a_i\) 变为 \(a_{i – 1} + a_{i + 1} – a_i\)。求在若干次操作之后,该数列的方差最小值是多少。请输出最小值乘以 \(n^2\) 的结果。
其中方差的定义为:数列中每个数与平均值的差的平方的平均值。更形式化地说,方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i – \bar a)}^2\),其中 \(\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i\)。
输入格式
输入的第一行包含一个正整数 \(n\),保证 \(n \le {10}^4\)。
输入的第二行有 \(n\) 个正整数,其中第 \(i\) 个数字表示 \(a_i\) 的值。数据保证 \(1 \le a_1 \le a_2 \le \cdots \le a_n\)。
输出格式
输出仅一行,包含一个非负整数,表示你所求的方差的最小值的 \(n^2\) 倍。
样例 #1
样例输入 #1
4
1 2 4 6
样例输出 #1
52
样例 #2
样例输入 #2
见附件中的 variance/variance2.in
样例输出 #2
见附件中的 variance/variance2.ans
样例 #3
样例输入 #3
见附件中的 variance/variance3.in
样例输出 #3
见附件中的 variance/variance3.ans
样例 #4
样例输入 #4
见附件中的 variance/variance4.in
样例输出 #4
见附件中的 variance/variance4.ans
提示
【样例解释 #1】
对于 \((a_1, a_2, a_3, a_4) = (1, 2, 4, 6)\),第一次操作得到的数列有 \((1, 3, 4, 6)\),第二次操作得到的新的数列有 \((1, 3, 5, 6)\)。之后无法得到新的数列。
对于 \((a_1, a_2, a_3, a_4) = (1, 2, 4, 6)\),平均值为 \(\frac{13}{4}\),方差为 \(\frac{1}{4}({(1 – \frac{13}{4})}^2 + {(2 – \frac{13}{4})}^2 + {(4 – \frac{13}{4})}^2 + {(6 – \frac{13}{4})}^2) = \frac{59}{16}\)。
对于 \((a_1, a_2, a_3, a_4) = (1, 3, 4, 6)\),平均值为 \(\frac{7}{2}\),方差为 \(\frac{1}{4} ({(1 – \frac{7}{2})}^2 + {(3 – \frac{7}{2})}^2 + {(4 – \frac{7}{2})}^2 + {(6 – \frac{7}{2})}^2) = \frac{13}{4}\)。
对于 \((a_1, a_2, a_3, a_4) = (1, 3, 5, 6)\),平均值为 \(\frac{15}{4}\),方差为 \(\frac{1}{4} ({(1 – \frac{15}{4})}^2 + {(3 – \frac{15}{4})}^2 + {(5 – \frac{15}{4})}^2 + {(6 – \frac{15}{4})}^2) = \frac{59}{16}\)。
【数据范围】
测试点编号 | \(n \le\) | \(a_i \le\) |
---|---|---|
\(1 \sim 3\) | \(4\) | \(10\) |
\(4 \sim 5\) | \(10\) | \(40\) |
\(6 \sim 8\) | \(15\) | \(20\) |
\(9 \sim 12\) | \(20\) | \(300\) |
\(13 \sim 15\) | \(50\) | \(70\) |
\(16 \sim 18\) | \(100\) | \(40\) |
\(19 \sim 22\) | \(400\) | \(600\) |
\(23 \sim 25\) | \({10}^4\) | \(50\) |
对于所有的数据,保证 \(1 \le n \le {10}^4\),\(1 \le a_i \le 600\)。
GT考试
数列
是\(2^{a_i}\)的加和,会有进位,进位是从低位向高位的,加和的顺序对S是没有任何影响的,所以考虑从低位向高位dp,依次放置\(a_i\),最后再乘上组合数
设\(f_{i,j,k,p}\)表示现在dp到了S的第i位(从0开始),a中已经确定了j个元素,前i位中有k个1,要向i+1为进位p个1的方案数
转移:\(f_{i+1,j+t,k+(p+t)\%2,\lfloor \frac{p+t}{2}\rfloor}\space +=\space f_{i,j,k,p}\times v_i^t \times C_{n-j}^{t}\)
如果可以忽略顺序那就不要考虑顺序,怎么容易怎么来
如果当前设的状态转移时不能考虑到所有的限制,那就再加一维
多模几组,找找规律,或者就是按照自己模拟的流程进行dp
数据传输
树上倍增dp,我只能说很女少,至于下次再碰见能不能做出来得另说 😕
直接到达的点之间的距离不能超过K,转化为不能有连续的K个点都没有被计入答案
二维\(dijkstra\) \(O(Qn\log n)\)
\((x,y)\)表示到达点x时有连续y个点(包括x)没有被计入答案
\((x,y)\to (x,0)\) 把\(val_x\)计入答案
\((x,y)\to (to,y+1)\)
树上倍增优化这个过程
\(dis_{u,i,x,y}\)表示到达u点时有连续x个点没有被计入答案,到达\(fa_{x,i}\)时有连续y个点没有被计入答案,\((u,fa_{u,i}]\)路径上的最小代价
考虑\(dis_{u,0,x,y}\)的初始化:
1.\(\space\)u点计入答案,fa计入答案 代价\(val_{fa}\)
2. u点计入答案,fa不计入答案 没有代价
(u,fa]路径上不必考虑走到儿子节点再回来的情况,因为fa此时不被计入答案,走儿子节点就是增加代价或者连续点数,都是不优的
- u和fa都不计入答案(只存在于K=3)
\(dis_{u,0,2,2}\)需要走到相邻节点再回来,因为u和fa两个点连续未选的点已经达到了上限
代价就是u节点及相邻节点的最小val
可以先猜一个复杂度然后想优化/kk
在树上去统计某个信息,不修改可以考虑倍增
大胆猜结论,然后尝试证明或推翻
原文地址:http://www.cnblogs.com/Facrt/p/16907306.html