~~压力~~雅礼考试总结

· · 个人记录

做题做了几百道，一夜之间全忘掉。

11.3 星期六，又迎来了每周一次的压力考试，我的心情十分的复杂。不止是本校的人，还有全省的人一同来考试。一开始考试，就出现了一种紧张的心理。刹那间，感觉什么知识全都清空，题目的算法完全没有看出来，竟一时出现了此题无高效算法的感觉。

都说第一题容易，但是单是这一题我就肝了一个多小时（要知道，第一题是水题！）。思路我开始偏向数学方法，想去解不等式。结果活活的一小时过去，我还没有码代码，等同于发呆了一小时，十分的可笑。

后来等到考试结束，仔细回味那题，或许并没有那么难？ 还真没有！ 化简到那一步时已经可以开始贪心了，而我就在这时走偏了。

第二题，给定一个序列，求子序列元素的平均值为x的方案数。

求方案数，要么公式题，要么就是DP题。果然，在一波随便乱搞后，发现DP方程：

设f(i,j,k)为对于前i个数，已经选了j个数，和为k的方案数

f(i,j,k) += f(i-1,j-1,k-a[i]) (k - a[i] >= 0)

发现方程的第一维完全可以滚掉，所以

    for(int i = 1; i <= n; i++) {
    for(int j = i; j >= 1; j--)
        for(int k = sum; k >= a[i]; k--)
        f[j][k] = (f[j][k] + f[j-1][k - a[i]]) % mo;
}

没错，O(n^{4})，但是数据水还是过了。（sum最多有为n^{2}）

其实可以优化到O(n^{3})，把j滚掉就行了。（提示：把元素减去平均值）