3
24
2015
0

20150323省选模拟测试#2

再次滚粗。今天是打表专场吗

A.给出一棵树,每个点有权值v[i]。m个操作,每次可以修改某个点的权值或者查询从树中选出一个连通块要求sigma(v[i])最大。v[i]可以为负数。n,m<=10W

题解;我只写了50分的暴力30分n<=1000可以每次树形DP一下。20分链其实就是最大连续子段和。

    正解考虑树链剖分。每条重链一棵线段树,但是每个点的权值是它往下连出的轻链的DP值之和。这样我们每次就可以沿重链往上跳了。

    DP值之和其实就是线段树的lx。

   没做过这种类型的题QAQ

B.求n个点n条边的无向连通图。n<=5000 %30 n<=10

题解:我yy了一个暴力。。。准备打10的表。。。f[n][m]表示n个点,m条边的无向连通图的个数。

    那么f[n][m]=C(C(n,2),m)-sigma(sigma(f[i][j]*C(n-1,i-1)*C(C(n-i,2),j)) 。

    然后发现爆零了。每个都比ans大 现在还不知道为什么。。。

C.n个白球放成一列,每次随机选择一个合法区间[l,r]将里面的白球全部染白。求期望多少次能把球全部染黑。

题解:CLJWC的题。。。我是真没听懂。。。暴力打表发现每次结果都不一样

 

Category: 模拟赛 | Tags: | Read Count: 296

登录 *


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

| Theme: Aeros 2.0 by TheBuckmaker.com