2.24测试总结

----------------------------------------------------------------
 
大概可以在superoj上找到..
----------------------------------------------------------------
T1:
先说一下70分的离线算法:
对时间分治。
设当前只考虑[l,r]这个区间
因此只考虑出现时间和[l,r]有交集的边
考虑所有覆盖了[l,r]的边,若这些边已经使得当前图不是二分图了,那么就对这个区间内所有时间回答false
否则,分治,选出和覆盖了左边的边,加入图中,用并查集判断是否构成二分图,然后挑出和左边有交集的边,向左分治
然后把刚刚加的边删掉(在并查集中断开边,因为这个原因不能压缩路径,可以按秩合并来保证时间复杂度)然后向右做同样的操作
 
100分算法:
考虑维护关于删除时间的最大生成树
每次加入一条边的时候,如果两点已经连通就把两点之间最小边断开,如果这两点间的环(原来的路径长度加上这条边)大小是奇数,就把这条边加入一个集合s
每次删除一条边的时候,如果这个边在集合里面,就把它从集合里面删掉,然后在图上删掉即可
任何时候只要集合中存在边,就不是二分图,否则是
关于这个算法的正确性,自己YY一下就好了
----------------------------------------------------------------
T2:
先说下30分暴力:
设f(i,j)表示还要玩i场,还剩j*(1/g)个币的期望胜场数
有转移:f(i,j) = (∑(i=1,n)max{pi+f(i-1,min{j+1,r*g}),f(i,j-r)})/n
 
标算:
首先二分答案mid
设一个值s,玩一把s减mid,赢一把s加1
因此mid和答案的大小可以通过s的期望正负来判定
现在考虑怎么求s的期望正负
这里有个结论:就是玩家手里游戏币的变化坑定是从r减小,再变回r,再减小,再变回r,这样的(为什么呢?我也不知道,不过YY一下感觉是对的,因为,不然呢)
设a[i]表示现在有i个游戏币,第一次达到有i+1/g个游戏币的期望s变化量(i<r)
而a[r]表示现在有r个游戏币,下一次再有r个游戏币的期望s变化量
因为有之前那个结论,所以a[r]的正负就是s最后的正负
现在考虑求a
对于a[i](i<1),因为不能用游戏币,所以a[i]=(∑(j=1,n)(pj-mid))/n
对于a[i](1<=i<r),考虑枚举最弱的k个英雄用游戏币,有a[i]=(k*∑(j=0,g)a[j-1+i/g]+∑(j=k+1,n)(pj-mid))/n
(解释一下为什么:这是因为用了一次之后到了j-1,然后要回到j+1/G,坑定是先回到j-1+1/G,然后j-1+1/G...最后j+1+(g+1)/g,而回到j-1+i/g的期望s变化就是a[j-1+(i-1)/g])
移项可得a[i]的表达式:a[i]=(k*∑(j=0,g-1)a[j-1+i/g]+∑(j=k+1,n)(pj-mid))/(n-k)
然后对于a[r],有a[i]=(k*∑(j=0,g-1)a[j-1+i/g]+∑(j=k+1,n)(pj-mid))/n(道理和上面一样,只是这次不是回到j+1/g而是回到j)
然后枚举一下k,二分答案一下,每一次验证求一下a[r]就好
----------------------------------------------------------------
T3:
50分算法:
因为逆矩阵乘以行列式等于伴随矩阵,而伴随矩阵就是代数余子式的转置,因此求逆矩阵即可,O(n^4)
 
100分:
考虑加了一行一列之后怎么快速求逆矩阵
见图:
这里求出逆矩阵之后需要求到A的行列式来得到伴随矩阵,只需要把新加的那一行拿来高斯消元就可以了
 
----------------------------------------------------------------