12.19模拟赛总结
12.28测试总结

12.23模拟赛总结

YYY posted @ 2015年12月23日 19:55 in OI相关 with tags 数据结构 线段树 高斯消元 矩阵乘法 可并堆 膜zrq 特征方程 , 316 阅读
_THIS_IS_START_OF_ARTICLE_
JLOI2015 Day1...
-------------------------------------------------------
 
T1:
特征方程法:
假设有数列an+2 = p*an+1 + q*an
假设有an+2 - t*an+1 = s(an+1 - t*an)
那么有:an+2 = (s+t)an+1 - (st)an
所以:
p = s+t
q = -st
因此s,t是x^2 - px - q = 0的两根
且s,t等价(可以互换)
而且有:an+2 - t*an+1 = (a2-t*a1) * s^n
和      an+2 - s*an+1 = (a2-s*a1) * t^n
上式减下式:
(s-t)an+1 = (a2-t*a1)s^n - (a2-s*a1)t^n
把(s-t)除过去:
an+1 = ((a2-t*a1)/(s-t))s^n - ((a2-s*a1)/(s-t))t^n
因为s,t = (p+sqrt(p^2-4*q))/2 , (p-sqrt(p^2-4*q))/2
因此有s-t=sqrt(p^2-4*q)
因此原式 = (1/(sqrt(p^2+4*q)))*((a2-t*a1)*s^n)+(a2-s*a1)*t^n))
 
这样就求出了an的通项公式
给定一组p,q,就可以得到一组s,t
同样给定一组s,t,就可以得到一个递推方程
 
现在令s=((b+sqrt(d))/2)^n,t=((b-sqrt(d))/2)^n,a1=2,a2 = s+t
则可以得到an=s^n+t^n的递推式,并且发现递推式各项都是整数,而我们要求的是s^n
由数据范围可以知道:-1<t<=0
因此:-1<t^n<=1
于是矩乘求出an,判断一下n的奇偶,看是不是要减一
就得到s^n的整数部分了
-------------------------------------------------------
T2:
因为各个人之间是相互独立的,所以先处理谁都没关系
所以对于每一个节点,就先把他的子树的所有节点都处理完,然后这个时候所有勇士都到了这个节点了
然后对于一个勇士,如果他不会死,那么所有比他大的人都不会死
因此每个节点用一个小根堆维护一下,每次把要死的人弹出堆,直到堆顶的人不死了为止,这时所有留在堆中的人都不会死
因此把他们合并到这个节点的父亲处,这样从叶子向根的搞(按BFS序逆序)
至于修改,就弄个标记搞一搞就好了
每个人最多出堆一次(O(n))
最多n次合并,每次lg(n)
因此时间复杂度是O(n*lg(n))
 
另外还有一种挺有意思的线段树做法(O(n*lg(n)*lg(n)))
把整棵树树链剖分
线段树维护跳过这个区间获得的修改
然后对于每一个人,让他向上跳
然后去线段树里面询问修改
如果在这个区间就死了,可以在线段树里面把死的位置询问出来
时间复杂度O(n*lg(n)*lg(n))
精度会被卡,但是可以用long double强行艹过
-------------------------------------------------------
T3:
拟阵线性基什么的我并不会..
说下我的想法吧
平面向量基本定理:任何一个2维向量都可以用2个不共线的向量表示
推广到n维:任何一个n维向量都可以用n个不共n-1维超平面的向量表示
因此如果给定的向量是共x维超平面的,那么至少要选x个
确定了选多少个之后贪心就行了..
现在看要选多少个:
如果当前选到了k个向量,那么可以确定一个k维超平面
这个时候考虑新加进来一个向量
如果它可以用前面的向量表示,那么说明它在这个k维超平面上,不管
否则,说明它不在这个k维超平面上,因此选中它,并令k=k+1
那么如何判断一个向量是不是在已经选好的k个向量所表示的k维超平面里面呢?设这k个向量为a1,a2..ak,设r(i)表示向量r的第i个分量,设当前要判断的向量为p
因此有方程:
a1(1)*x1+a2(1)*x2+...+ak(1)*xk=p(1)
a1(2)*x1+a2(2)*x2+...+ak(2)*xk=p(2)
...
a1(m)*x1+a2(m)*x2+...+ak(m)*xk=p(m)
看这个方程组有没有解就行了,高斯消元即可
然后这样是O(n*n^3)的,过不了
所以考虑这样:
记录last[i]表示目前某个已经选到的第i维不为0的向量且第1~i-1维都为0的向量
现在枚举p的每一维,对于p的某一个不为0的维度v,如果last[v]不存在,就说明p的第v维怎么也不可能消掉,因此选到p,并且令last[v]=p,如果last[v]存在,就用last[v]的第v维把p的第v维搞成0
如果p的所有维都可以搞成0,就说明他可以被前面已经选中的向量表示,因此不选他
这样时间复杂度就降到是O(n^3)了
-------------------------------------------------------
_THIS_IS_END_OF_ARTICLE_

登录 *


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