2016.3.16测试总结
3.28测试总结

3.17测试总结

YYY posted @ 2016年3月17日 22:38 in OI相关 with tags 数学题 线性代数 DP 二叉搜索树 CDQ分治 , 271 阅读
_THIS_IS_START_OF_ARTICLE_
-----------------------------------------------------------------------------
鼎爷的题...
题面大概可以在SuperOj上找到
 
-----------------------------------------------------------------------------
T1:
还不会..
-----------------------------------------------------------------------------
T2:
数据太水,随便搜一搜都有60分...
 
先说一下神犇CZH的做法好了
假设小萝莉可以走的方法是向量集合A
假设坏大叔可以走的方法是向量集合B
首先考虑一维的情况,显然求个gcd就行了
现在考虑二维的情况
现在假设要用B中的向量来表示A中的第i个向量(xi,yi)
假设B中的向量是(aj,bj)
那么有:
xi = Σ(j=1,m)tj*aj(tj∈Z)
yi = Σ(j=1,m)tj*bj(tj∈Z)
选一个下标k,把tk单独放到一边,得到等式
tk = (xi - Σ(1<=j<=m且j≠k)tjaj)/ak = (yi - Σ(1<=j<=m且j≠k)tjbj)/bk
即(xi - Σ(1<=j<=m且j≠k)tjaj)/ak = (yi - Σ(1<=j<=m且j≠k)tjbj)/bk
交叉相乘一下:
ak*yi+bk*xi = Σ(1<=j<=m且j≠k)tj(bk*aj+ak*bj)
然后发现他就变成一维的情况了
然后对每个1<=k<=m都做一次,当且仅当都成功说明(xi,yi)可以被B中的向量线性表示(只做一次不行,因为这样有可能使得tk是分数)
另外这个方法不能处理m<=1的情况,需要特判一下
 
然后是标算:
我们需要搞出一组基(两个向量,构成一个上三角矩阵),使得这个基可以由B中的向量线性表示,并且可以表示出B中的任意一个向量
现在证明这个基是存在的
归纳假设他存在
假设原来基中的向量是a和b,其中a的两个维度都有值
现在考虑加入一个向量c
如果c只有第二个维度有值,那么他和b求一个gcd,求到的向量d既可以线性表示c,也可以线性表示b,用d替代b,就可以线性表示原来所有的向量和c
否则,把c的第二个维度和a辗转相减(第一位跟着一起变),一定可以得到一个第一个维度是0的向量d,这个向量是用a和c线性表示出来的,把d和b求个gcd,用求到的向量d'代替b,那么他可以线性表示b和d,用c代替a,因为d是a,c线性表示出来的,而c在基中,因此a也可以被线性表示出来,因此前面的所有向量都可以被表示,而c也可以被表示
然后只需要看一下求出来的基能不能表示A中的向量就行了
 
以上两种做法都可以扩展到任意维度
-----------------------------------------------------------------------------
T3:
斜率优化,用平衡树或者CDQ分治维护凸壳
其实用平衡树维护凸壳也不是很难写嘛....
-----------------------------------------------------------------------------
 
_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter