2.24测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
----------------------------------------------------------------
大概可以在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的行列式来得到伴随矩阵，只需要把新加的那一行拿来高斯消元就可以了
----------------------------------------------------------------
评论 (0)
