HNOI2011 部分题题解

Posted on 2012-04-24 21:25 Mato_No1 阅读(729) 评论(0)  编辑 收藏 引用 所属分类: HNOI
【最近很想被各种省选题虐……于是,就开始找各种省选题……发现能虐本沙茶的实在是太多了(谁叫我是沙茶呢囧)】

homework:
很能令人想歪的题目……想到某种数论模型……
正解是递推+矩阵优化。可以这么想,本题如果暴力递推的话,设F[i]为1到i组成的数(具体的数,不是取模以后的结果,虽然这个值是无法存储的),则有F[i]=(F[i-1]*10T)+i,其中T是i在十进制下的位数,边界F[0]=0。这个式子是可以矩阵优化的,矩阵为
10T 0 0
1 1 0
1 1 1
则1*3矩阵[F[i-1], i-1, 1]乘以这个矩阵之后就是[F[i], i, 1],然后对于各个T分开处理一下就行了……这里的取模完全就是个幌子……
(另外,矩阵优化递推是一个很重要的专题……)

race:
(最近刚好在某MO神犇的资料里面看到了柯西不等式……发现此题可以用这个来搞……就囧掉了)
柯西不等式:(a12+a22+...+an2)(b12+b22+...+bn2)>=(a1b1+a2b2+...+anbn)2  【*】,
等号成立当且仅当对于任意1<=i, j<=n, i≠j,有aibj-ajbi=0,也就是(a1, b1), (a2, b2)...(an, bn)这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都是质数……)


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理