BZOJ NOI十连测 8thTest
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------------------------
挂零的一场
------------------------------------------------------------------------
T1:
首先知道凸多边形可以被划分成一些三角形,而且这些三角形可以有一个共同点,不妨称这个点为初始点
首先假设初始点定了,可以得到一个n^3:的DP:
f[i][j][k]表示到了初始点顺时针方向第i个点,选了k个点,是否包含原点,然后转移的时候枚举下一个点O(n)转移一下
然后因为初始点不定所以是n^4的
然后可以通过随机选n/k个初始点来把复杂度降到n^3,这是因为选n/k次,一个作为答案的点都没选到的概率是(1-k/n)^(k/n),这个非常小
然后考试的时候我就卡这儿了...
后面的其实我也猜到了,决策是单调的(但是我不会证)
------------------------------------------------------------------------
T2:
先把MST跑出来
依次加入非树边,只需要维护每个人变得不是割点的时间
只需要维护一个节点的所有儿子的子树连出去的时间
每次连接两个点的时候,他们一直到他们的lca的下两层的祖先都连出去了,可以用树链剖分+线段树维护
然后他们的lca下一层的节点的祖先的子树连在了一起,用并查集维护(记录一下连在一起的时间,另外如果连之前就已经连出去了就不用连在一起了)
↑这个是nlog的所以只能拿70分
然后标算好像是用并查集维护的
------------------------------------------------------------------------
T3:
...不会
------------------------------------------------------------------------
评论 (0)
