Fork me on GitHub

wucstdio的毒瘤模拟赛

$wucstdio$大爷的Flag还是没有倒….

T1: 反正我刚开始对这道题是完全没有什么信心的qaq(才不会告诉你我直接去看的$T2$)
考虑$50$分的情况:一条链。所以就是一个等差数列了qwq
考虑剩余的正解,我们可以把每一步的期望值当成这棵树的权值,然后因为从上向下和从下向上的期望值可能不太一样,所以我们需要两个函数来表示:(相当于两条边)。
我们设$f(x) g(x)$分别表示从下向上和从上向下的情况,所以我们考虑求出$f(x)$时,我们要考虑以下情况:
直接走到这个节点的父节点,所以这种情况下,对这个节点对答案的贡献就是$\frac {1}{d[x]}了$
还有一种情况就是这个节点先跳到他的儿子,再跳回这个节点,再跳过去。这个时候,因为我们需要一步来跳过去,所以这种情况对答案的贡献就是:$\sum_{j=son} \frac {1}{d[x]}[1 + f(x) + f(j) ]$
我们综合考虑一下这两种情况对答案的贡献值,将这两个式子加起来,我们就会得到下边的这个式子:

我们安置我们做期望的一贯思路(好像我做过多少期望一样QwQ),因为$num[son]=p-1$,所以我们可以得到这样一个式子:

化简一下之后有:

然后我们来考虑一下$g(x)$这个东西怎么求,当我们经过观察之后,我们可以发现这个式子有三种情况:
他的父亲直接跳到他这里,这种情况对答案的贡献就是$\frac{1}{d[father]}$
他的父亲先跳到他的爷爷,然后再跳回来,这种情况下,对答案的贡献就是:$\frac{1}{d[father]}\times (1 + g(p) +g(x) )$
他的父亲跳到他的兄弟然后再跳到他自己。
我们把这三种情况加起来,就会有:

继续化简有:

通过这种方式,我们就可以把$g(x) f(x)$算出来,相当于边长。

算出边长后,这个问题就转化成了:给你一颗树,求树的直径。我选择了DP求直径,就很简单了。

代码:

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
#include <cstdio>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

const int N = 2e5 + 10;

int n , m , t;
struct Edge {
int to;
int next;
}e[N << 1];
int head[N];
int now_ans;
int f[N] , g[N] , p[N];
int LongDis[N][2] , SecondDis[N][2];

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
inline void add ( int x , int y ) {
e[++t].to = y;
e[t].next = head[x];
head[x] = t;
return;
}
inline int min ( int x , int y ) {
return x < y ? x : y;
}
inline int max ( int x , int y ) {
return x > y ? x : y;
}
void Find_f ( int root , int fa ) {
f[root] = p[root];
for ( int i = head[root] ; i ; i = e[i].next ) {
int j = e[i].to;
if ( j == fa )
continue;
Find_f ( j , root );
f[root] += f[j];
}
return;
}
void Find_g ( int root , int fa ) {
for ( int i = head[root] ; i ; i = e[i].next ) {
int j = e[i].to;
if ( j == fa )
continue;
g[j] = f[root] + g[root] - f[j];
Find_g ( j , root );
}
return;
}
void Work ( int root , int fa ) {
int Frist = 0 , Second = 0;
for ( int i = head[root] ; i ; i = e[i].next ) {
int j = e[i].to;
if ( j == fa )
continue;
Work ( j , root );
if ( LongDis[j][0] + g[j] > LongDis[root][0] ) {
SecondDis[root][0] = LongDis[root][0];
LongDis[root][0] = LongDis[j][0] + g[j];
Frist = j;
}
else if ( LongDis[j][0] + g[j] > SecondDis[root][0] )
SecondDis[root][0] = LongDis[j][0] + g[j];
if ( LongDis[j][1] + f[j] > LongDis[root][1] ) {
SecondDis[root][1] = LongDis[root][1];
LongDis[root][1] = LongDis[j][1] + f[j];
Second = j;
}
else if ( LongDis[j][1] + f[j] > SecondDis[root][1] )
SecondDis[root][1] = LongDis[j][1] + f[j];
}
if ( Frist != Second )
now_ans = max ( LongDis[root][0] + LongDis[root][1] , now_ans );
else if ( Frist == Second )
now_ans = max ( now_ans , max ( SecondDis[root][1] + LongDis[root][0] , SecondDis[root][0] + LongDis[root][1] ) );
return;
}

int main ( void ) {
freopen ( "tree.in" , "r" , stdin );
freopen ( "tree.out" , "w" , stdout );
n = read ();
for ( int i = 1 ; i < n ; i++ ) {
int x = read () , y = read ();
add ( x , y );
add ( y , x );
p[x]++;
p[y]++;
}
Find_f ( 1 , 0 );
Find_g ( 1 , 0 );
Work ( 1 , 0 );
printf ( "%d.00000\n" , now_ans );
return 0;
}


T2:其实暴力还是挺显然的

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:wucstdio的毒瘤模拟赛

文章作者:KRrrrrrrrr

发布时间:2018年10月18日 - 17:10

最后更新:2019年11月05日 - 09:11

原始链接:http://krrrr.xyz/2018/10/18/wucstdio的毒瘤模拟赛/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。