小奇挖矿2

对于20%的数据，n=1。只需判断这个星球位置是否能拆分成4和7的和。

可以简单递推，枚举求得。

打表的话可以发现，只有1 2 3 5 6 9 10 13 17不能拆。

对于40%的数据，n很小。可以2^n枚举去哪些星球，然后用上面的方法判定一个星球能否到下一个星球。

对于60%的数据，m比较小。设x[i]为i号星球的原矿数，f[i]为到i号星球能获得的最大原矿数，则f[i]=max{f[i-4],f[i-7]}+x[i]。

对于100%的数据，m很大。

1.将所有矿物排序，f[i]为到第i个矿体能获得的最大原矿数，那么f[i]=max{f[j]}+x[i]，其中，i-j满足能拆分成4和7。

这样dp需要n^2的复杂度，但是我们发现，相距超过17的一定可达，那么不超过17的范围内暴力，超过17的取个最大值即可，复杂度O(n)

2.可以把相邻的星球距离超过17的压缩成18，按照60%的做法dp

小奇的矩阵

对于30%的数据，把所有的路径深搜出来取最优，复杂度是T*C(2n,n)*n

这道题乍一看像是dp，但是问题在于因为求的是方差与平均数有关，每一步的代价似乎不能直接得出

对于另外40%的数据，我们发现路径Ai和SN不超过120，考虑枚举SN，平均值为av=SN/N（N=n+m-1），那我们就能得到每一步的代价，但是要保证求的路径符合Ai和为SN，设计f(s,i,j)表示到（i,j），和为s的最小代价

f(s,i,j)=min{f(s-a[i][j],i,j-1),f(s-a[i][j],i-1,j)}+(av-a[i][j])^2

复杂度是T*SN^2*n^2

事实上，路径Ai和不等于SN也无所谓，因为对于一条路径，只有我们枚举的SN等于路径Ai和时，这条路径的方差才最小

设我们枚举的SN比真实的Ai和小E，E是任意实数

很容易证明∑(Ai-Aavg)^2<∑(Ai-av+E)^2

所以直接去掉dp的第一维，复杂度是T*SN*n^2,可以通过100%的数据

还有另外一种思路，把求方差的式子展开

得到N*∑(Ai^2)-SN^2，设计f(s,i,j)表示到（i,j），和为s的最小的N*∑(Ai^2)，最后枚举s取f(s,i,j)-s^2的最小值，复杂度也是T*SN*n^2

小奇的仓库

来自原出题人18357：

算法1：

不会写函数的小伙伴们，我们只需要写个floyd，就有10分啦！

算法2：

在算法1的基础上，我们对每条边处理一下xor，就有20分啦！

算法3：

简单的树形DP，或者你会nlogn的dij，处理完每个点到其它点的最短路后再加上xor，那么这样就有30分啦！

算法4：

第4、5个点无需xor，那么我们树形DP扫一个节点与其它所有节点的路径长度之和，可以合并信息，最终均摊O(1)，50分到手。

算法5：

第6个点xor 1，那么我们树形DP到一个点时记录有多少个0，多少个1，然后每当一条路径到2，那部分就再记录一个值，60分到手。

算法6：

如果你第6个点都过了，却没有满分，笨死啦！

一样的嘛，就是原来的“0”、“1”、大于等于2变成了0~16么~~