Posted on 2012-04-24 21:25
Mato_No1 阅读(830)
评论(0) 编辑 收藏 引用 所属分类:
HNOI
【最近很想被各种省选题虐……于是，就开始找各种省选题……发现能虐本沙茶的实在是太多了（谁叫我是沙茶呢囧）】
homework：
很能令人想歪的题目……想到某种数论模型……
正解是递推+矩阵优化。可以这么想，本题如果暴力递推的话，设F[i]为1到i组成的数（具体的数，不是取模以后的结果，虽然这个值是无法存储的），则有F[i]=(F[i-1]*10
T)+i，其中T是i在十进制下的位数，边界F[0]=0。这个式子是可以矩阵优化的，矩阵为
10
T 0 0
1 1 0
1 1 1
则1*3矩阵[F[i-1], i-1, 1]乘以这个矩阵之后就是[F[i], i, 1]，然后对于各个T分开处理一下就行了……这里的取模完全就是个幌子……
（另外，矩阵优化递推是一个很重要的专题……）
race：
（最近刚好在某MO神犇的资料里面看到了柯西不等式……发现此题可以用这个来搞……就囧掉了）
柯西不等式：(a
12+a
22+...+a
n2)(b
12+b
22+...+b
n2)>=(a
1b
1+a
2b
2+...+a
nb
n)
2 【*】，
等号成立当且仅当对于任意1<=i, j<=n, i≠j，有a
ib
j-a
jb
i=0，也就是(a
1, b
1), (a
2, b
2)...(a
n, b
n)这n个点共线。具体证明的话，把两边的乘法列成一个矩阵的形式，去掉主对角线（相同），把关于主对角线对称的位置对应相减，得到类似叉积的平方和的形式即可。
对于本题，假设不考虑耗油量为负时取0的情况，设F0=(F-Σ(b*Li*Si))/a，则问题就转化为求一组vi使得ΣLivi=F0且Σ(Li/vi)的值最小。这样，可以设ai=sqrt(Li/vi)，bi=sqrt(Livi)，代入【*】式……傻眼了囧……不仅能得到最小值，还能发现取得最小值时所有的v都相等，且可以算出来……当然如果F0<0就无解了囧……
不过本题最囧的问题是对于耗油量为负的情况。最好的处理办法是，如果按照【*】式得到的v值会导致某些s<0的路段耗油量为负，则对于这些路段单独处理，使得它们的耗油量刚好为0（除非此时的速度已超过上限），并将它们删去，然后对于剩下的路段，重新代入(*)式计算v，直到不出现耗油量为负的情况即可。当然，如果在此过程中出现F0<0，就无解了。
brackets：
这个应该不用再说了，直接看这里。
rectangle：
思想比较巧妙的话说……应该枚举线段，按照中点和线段长度进行排序（因为两条线段若能组成矩形的两对角线，则它们必然等长，且中点重合），然后扫一遍，顺带枚举就是了……表面上来看时间复杂度可能到O(N3)级别，其实根本无法出卡这种方法的数据……
canon：
这个没什么好说的，就是硬推公式，结果为
(C(2n, m) - C(2n-1, m/2)) / 2n + C(2n-1, m/2) （当m % 4 == 0或3时）
(C(2n, m) + C(2n-1, m/2)) / 2n - C(2n-1, m/2) （当m % 4 == 0或3时）
对于当中的取模问题：加、乘直接取模；减法要在取模后判定是否小于0，若小于0再加上待取模数；除法要转化为乘逆元（反正这里的MOD都是质数……）