代数好玩
发现不等式这个内容还是稍微有一点用的，于是看日报稍微学习了一下儿。这篇日报里讲了一些不等式并给出了一些习题，但是没有题解，于是我来写一些，尽量写得友好一点儿吧。
这里我把所有题都整理到 vjudge 上的这个比赛里了。
当然除了日报中介绍的不等式还有很多可能用到的不等式：四边形不等式，琴生不等式，切比雪夫不等式...
下面是习题题解（开了代码共享计划的应该能看到代码）。
Journey with Pigs
设猪的排序是 (a_i)，则最后得到的价值是 (sumlimits_{i=1}^n(p_i-d_it) imes w_{a_i})。现在我们要最大化这个 (sum)，看到这种形如 (sumlimits ab) 的可以往排序或柯西不等式上去想。这道题柯西取不了等，所以只好排序做。
排序不等式即为 (sumlimits_{i=1}^na_ib_igesumlimits_{i=1}^{n}a_ib_{p_i}gesumlimits_{i=1}^na_ib_{n-i+1})。证明用调整法也很好证。
现在我们 (p_i-d_it) 确定了，我们发现只要最小的 (p_i-d_it) 对应最小的 (w_i) 就可以得到最大的价值了。时间复杂度为 (O(nlog{n}))。
CF1401D Maximum Distributed Tree
可以说这题我在做时把 product 理解成了和然后一直在想怎么用柯西做。。。
不过OI中柯西的题不怎么多因为不好取等。
看到 (sum_{i=1}^{n-1}sum_{j=i+1}^{n}f(i,j)) 不妨看成每条边对答案的贡献 (sum_{i=1}^{n-1}g(i)w(i))，(g(i)) 是经过该边的路径条数，(w(i)) 是这条边的边权。(g(i)) 是很好统计的。让答案最大即为让越大的 (g(i)) 配越大的 (w(i))（排序不等式）。
发现这个 (k) 一定是 (m) 个质数的乘积，如果 (m = n-1) 那么每个质数排序越大的质数配越大的 (g(i)) 即为答案；如果 (m > n-1) 那么把最大的几个全部丢到最大的 (g(i)) 上就是最优的，稍微调整就可以证（上面两种情况不能全部丢最大的上面因为要求 (1) 的边尽量少）；如果 (m<n-1)，那么就只能最小的几条边是 (1) 了。
P2647 最大收益
考虑我们已经确定了取哪些数然后要确定顺序，发现如果答案排列是 (p_1,p_2...p_k)，那么答案为 (sum_{i=1}^n(w_{p_i}-(k-i)r_{p_{i}}))。
发现前面的和顺序无关，最后即要最小化 (sum_{i=1}^{n}(k-i)r_{p_{i}})，(k-i) 递减，那么 (r) 递增即为最小（排序不等式）。所以我们在一开始按 (r) 排序就和顺序无关，按从前往后的顺序取就好了。
然后就可以考虑 dp 了，记 (f[i][j]) 代表从前 (i) 个已经取了 (j) 个的最大值。
显然有状态转移方程：(f[i][j]=max(f[i-1][j]+f[i-1][j-1]+val(i)))，但是我们不知道后面还要取多少个数，显然可以再加一维，然后时间复杂度变为 (O(n^3)) 过不了。
重新设计状态，从后往前 dp，(f[i][j]) 代表从 (i) 到最后已经取了 (j) 个的最大值。
这里就可以这么转移了：(f[i][j]=max(f[i+1][j],f[i+1][j-1]+w_i-r_i imes (j-1)))。
CF163D Large Refrigerator
一道玄学题，不过也没有那么难
考虑求 (frac{S}{2}=ab+bc+ac) 的最小值，不妨设 (ale ble c)，这样就显然有 (a le sqrt[3]{V},ble sqrt{frac{V}{a}})。而在 (sqrt[3]{V}) 范围内又是 (V) 的约数的数是非常少的，考虑暴力枚举。
对于枚举出的一个 (a)，再暴力一个 (b)，这样就可以算出 (c) 来更新答案，可是复杂度不太优秀。瓶颈在枚举 (b)，而我们发现很多情况下 (b) 是很不优的，可以发现当确定 (a) 以后，(b,c) 越接近最后的答案越小。这用一个均值就可以证明：(b+cge 2sqrt{bc}) 当 (b=c) 时取等。
所以我们只需找到一个尽可能大的 (b) 就好了。但是我们发现这样子复杂度并没有本质上减少。接着我们发现对于一些 (a) 无论 (b,c) 取什么值都不可能比之前更小，这时我们就不用去递归找 (b)，直接返回即可。
然后这个写代码的时候就有很多细节需要注意，比如说某些地方是上取整，有些是下取整，还有一些边界问题。