day2下午

清北学堂--刷题班
by mjt
2017.10.29

题解

t1

t2

筛出素数

一种方法:

for (int a=2; a<=n; ++a) 
    for (int b=a+a; b<=n; b+=a) // 可以a*a
        not_prime[b] = true;
nlogn
by zhx

另一种方法

for (int a=2; a<=n; ++a)
    if (not_prime[a]) 
        for (int b=a+a; b<=n; b+=a)
            not_prime[b] = true;

nloglogn

线性筛

for (int i=2; i<=N; i++) {
    if (!noprime[i]) {
        prime[++tot]=i;
    }
    for (int j=1; j<=tot&&i*prime[j]<=N; j++) {
        noprime[i*prime[j]] = true;
        if(i % prime[j] == 0) break ;  
    }
}
O(n)

然后二分+前缀和
难度：标准的noipT2难度 by zhx

t3

30%暴力建树暴力查询。
60%线性算算树的值，树形dp
算一棵树的答案，
$t_i = t_k+t_j$
首先$f[t_i] = f[t_j]+f[t_k]$
这是在合并前的树内的价值
然后是，$t_j的点和t_k的点$
$size[t_j]*size[t_k]*l$经过l的价值,中间的边
合并的点为c,d,
对于每个$t_j$的点，先让他到c，然后乘以$size[t_k]$
那么，对于所有点都是这样合并。
设$g[j][c]$为所j树种所有的点到c的距离。
$t_k$同理
那么知道g了就可以做了

.

求g[j][p]
j中的答案是g[j][c]
合并上$t_k$
经过中间的边的价值(dis[j][c][d]*size[k])
$在t_k树中的价值（到达d）$加上g[k][d]
$t_j = t_a+t_b$

.

g[][]第二维在$2^m$级别
开不下
记忆化搜索，
因为只有合并的点c,d有用，记忆化搜索这两个点，map

.

求dis[i][c][b]
考虑i是有jk两棵树转移
所以如果两个cd在j树中=dis[j][c][d]
不在一棵树中，那么，jk由x,y合并，那么=dis[j][c][x]+dis[k][d][y];
即j树中的c点先 到x点，k树中的d点先到y点，然后求出。
可以记忆化搜索。

gg1

gg2

gg3

解题报告及总结

预计100+100+？
实际100+100+0

t1

北京时做过，当时写的60分动规写炸了，然后就记住了这个题

t2

二分答案，30%的暴力算的。
一个bug，没开long long 。。
最后临收时，发现，怕一改错了，没改，然后也全过了

t3

有了一个多小时，先看懂了题目，又推出了样例，然后开始写，没调处来。