3.17测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_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分治维护凸壳
其实用平衡树维护凸壳也不是很难写嘛....
-----------------------------------------------------------------------------
评论 (0)
