12.23模拟赛总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_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)了
-------------------------------------------------------
评论 (0)
