C

给出一段长度为n的括号序列,在其前和后分别添加一些括号使得长度为n,且每个左括号匹配一个右括号

DP
dp[i][j] 表示前i个括号中,()多j个,注意二者是对称的,即d[i][j] = d[i][-j]
转移即
dp[i][j] += dp[i-1][j+1] (+ dp[i-1][j-1] (j>0))
统计给出序列中的左右括号个数差t,注意记录统计过程中的min(t),要保证匹配则 j+min(t) >= 0
答案即为$\sum$d[i][j]*d[n-m-i][j-t]

复杂度$O((n-m)^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL mod = 1e9 + 7;
const int maxn = 2010;
int n,m;
LL d[maxn][maxn];
char s[int(1e5) + 10];

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d",&n,&m);
memset(d,0,sizeof d);
d[0][0] = 1;
int t = n-m;

for(int i=1;i<=t;++i)
for(int j=0;j<=i;++j)
if(!j)
d[i][j] = (d[i][j] + d[i-1][j+1]) %mod;
else
d[i][j] = (d[i][j] + d[i-1][j+1] + d[i-1][j-1]) %mod;

scanf("%s",s);
int mn = 0,cur = 0;
for(int i=0;i<m;++i)
{
cur += (s[i] == '('?1:-1);
mn = min(mn,cur);
}

LL ans = 0;
for(int i=0;i<=t;++i)
for(int j=0;j<=i;++j)
{
if(j + mn < 0 || abs(j+cur) > t-i) continue;
ans = (ans+d[i][j]*d[t-i][abs(j+cur)]) %mod;
}
printf("%lld\n",ans);
return 0;
}

D

给n个圆柱体,当前圆柱体上面只能放给定顺序之前的,体积不大于它的一个圆柱体。

树状数组
将圆柱体按体积排序,离散化,维护前p小的体积为底的体积和最大值,并更新答案

复杂度$O(nlog(n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1e5 + 10;
const double pi = acos(-1.0);
int n,r[maxn],h[maxn];
LL v[maxn],d[maxn];

inline int lowbit(int x)
{
return x&-x;
}

void modify(int x,LL mx)
{
for(int i=x;i<=n;i+=lowbit(i))
{
d[i] = max(d[i],mx);
}
}

LL query(int x)
{
LL res = 0;
for(int i=x;i>0;i-=lowbit(i))
{
res = max(res,d[i]);
}
return res;
}

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d %d",r+i,h+i),v[i] = (LL)r[i]*r[i]*h[i];
sort(v,v+n);
int pn = unique(v,v+n) - v;
memset(d,0,sizeof d);
LL ans = 0;
for(int i=0;i<n;++i)
{
LL vol = (LL)r[i]*r[i]*h[i],cur;
int p = lower_bound(v,v+pn,vol) - v +1;
cur = vol + query(p-1);
ans = max(ans,cur);
modify(p,cur);
}
//printf("%lld\n",ans);
printf("%.12lf\n",pi*ans);
return 0;
}

E

一棵n个结点的树,m次询问,每次询问给出(u,v),问在树上添加一条路径,使得(u,v)在一个环上时,环的长度的期望。

dfs乱搞

我们先假设$deep_u \leq deep_v$
$cnt_u$表示以u为根的子树的结点数
$len_u$表示以u为根的子树的所有结点到u的路径长度和,
$lenup_u$表示树上所有结点到u的路径长度和
s表示u,v到$LCA(u,v)$的路径长度和

若$LCA(u,v) \neq u$,则为上述
若$LCA(u,v) = u$,pv为v的祖先,u的一个子节点,$cnt_{u} = cnt_{1} - cnt_{pv}$,$len_u = lenup_u - lenup_{pv} - cnt_{pv}$

$$ans = \frac{cnt_ulen_v + cnt_vlen_u }{cnt_ucnt_v} + s + 1$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1e5 + 10;
const int maxd = 18;
int n,m;
int cnt[maxn],dep[maxn],p[maxn][maxd];
LL len[maxn],lenup[maxn];
vector<int> G[maxn];

void dfs(int u,int fa)
{
p[u][0] = fa;
dep[u] = dep[fa] + 1;
len[u] = 0;
cnt[u] = 1;
for(int i=1;i<maxd;++i) p[u][i] = p[p[u][i-1]][i-1];

for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v != fa)
{
dfs(v,u);
cnt[u] += cnt[v];
len[u] += len[v] + cnt[v];
}
}
}


void dfs2(int u,int fa)
{
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v == fa) continue;
lenup[v] = lenup[u] + (n - cnt[v]) - cnt[v];
dfs2(v,u);
}
}

int lca(int u,int v)
{
int len = 0;
if(dep[u] < dep[v]) swap(u,v);
for(int i=maxd-1;i>=0;--i)
if(dep[p[u][i]] >= dep[v])
{
len += 1<<i;
u = p[u][i];
}
if(u == v) return -len;
for(int i=maxd-1;i>=0;--i)
{
if(p[u][i] != p[v][i])
{
u = p[u][i];
v = p[v][i];
len += 2*(1<<i);
}
}
len += 2;
return len;
}

double solve(int u,int v)
{
int t = lca(u,v);
//printf("%d\n",t);
if(t > 0)
{
LL num = (LL)cnt[u]*cnt[v];
return ((LL)cnt[u]*len[v] + (LL)cnt[v]*len[u] + num*(t+1))/(double)num;
}
else
{
t = -t;
if(dep[u] > dep[v]) swap(u,v);
int pv = v;
for(int i=maxd-1;i>=0;--i)
if(dep[p[pv][i]] > dep[u])
{
pv = p[pv][i];
}
LL lenu = lenup[u] - len[pv] - cnt[pv];
int cntu = cnt[1] - cnt[pv];
LL num = (LL)cntu*cnt[v];
//printf("%d %d\n",lenu,cntu);
return ((LL)cntu*len[v] + (LL)cnt[v]*lenu + num*(t+1))/(double)num;
}
}



int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d",&n,&m);
for(int i=1;i<n;++i)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
lenup[1] = len[1];
dfs2(1,0);
for(int i=0;i<m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
printf("%.12lf\n",solve(u,v));
}
return 0;
}