BZOJ 3451: Tyvj1953 Normal

考虑两个点a,b
a对b的删除时间有1的贡献当且仅当
在a到b的路径上的所有点中a是第一个删除的
这个有1/dist(a,b)的概率 对答案的贡献是1
所以这题就是求Σ1/(u,v)
这个可以用树分治做(233)
然后树分治合并两棵子树的f的时候要n^2的时间
这个可以fft优化到nlogn
总复杂度nlog^2n

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 300005;
const int P = (1 << 21) * 479 + 1;
const int G = 3;

struct line
{
    int to, next;
}li[maxn * 2];

int be[maxn], mx[maxn], f[maxn], b[maxn], fa[maxn], is[maxn], g[maxn][2], gt[maxn][2], d[maxn], br[maxn];
ll t1[maxn], t2[maxn], tt1[maxn], tt2[maxn];
int l, n, tot, tot1;
ld ans;
queue<int> q;
stack<int> s;
vector<int> v;

int getz(int now)
{
    int tot = 0, as = -1;
    for (q.push(now), b[now] = 1, fa[now] = -1; !q.empty(); )
    {
        int now = q.front();
        ++tot;
        q.pop();
        s.push(now);
        f[now] = mx[now] = 0;
        for (int i = be[now]; i; i = li[i].next)
        {
            int to = li[i].to;
            if (is[to] || b[to]) continue;
            fa[to] = now;
            b[to] = 1;
            q.push(to);
        }
    }
    for (; !s.empty(); )
    {
        int now = s.top();
        s.pop();
        b[now] = 0;
        ++f[now];
        if (fa[now] != -1)
            f[fa[now]] += f[now],
            mx[fa[now]] = max(mx[fa[now]], f[now]);
        mx[now] = max(mx[now], tot - f[now]);
        if (as == -1 || mx[as] > mx[now])
            as = now;
    }
    return as;
}

bool cmp(int a, int b)
{
    return f[a] < f[b];
}

int bitre(int a, int n)
{
    int ans = 0;
    for (int i = 0; i < n; ++i)
        ans += (1 << i) * ((a & (1 << (n - i - 1))) ? 1 : 0);
    return ans;
}

ll power(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n & 1) ans = (ans * a) % P;
        a = (a * a) % P;
        n >>= 1;
    }
    return ans;
}

void fnt(ll y[], const ll b[], ll n, ll rev = 1)
{
    ll len = 1 << n;
  for (ll i = 0; i < len; ++i)
    y[i] = b[bitre(i, n)];
    for (int i = 1; i <= n; ++i)
    {
        ll m = 1 << i;
        ll wn = power(G, (P - 1) / m);
        for (int j = 0; j < len; j += m)
        {
            ll w = 1;
            for (int k = j; k < j + m / 2; ++k)
            {
                ll u = y[k], v = (w * y[k + m / 2]) % P;
                y[k] = (u + v) % P, y[k + m / 2] = (u - v) % P;
                w = (w * wn) % P;
            }
        }
    }
    if (rev == 1) return;
    ll re = power(len, P - 2);
    for (int i = 0; i < len; ++i)
        y[i] = (y[i] * re % P + P) % P;
    reverse(y + 1, y + len);
}

void calc2(int v)
{
    int n, len;
    for (n = 0; (1 << n) < (v + 1) * 2; ++n);
    len = 1 << n;
    for (int i = 0; i < len; ++i)
        t1[i] = g[i][0] != tot1 ? 0 : g[i][1],
        t2[i] = gt[i][0] != tot ? 0 : gt[i][1];
    fnt(tt1, t1, n);
    fnt(tt2, t2, n);
    for (int i = 0; i < len; ++i) tt1[i] = (tt1[i] * tt2[i]) % P;
    fnt(t1, tt1, n, -1);
    for (int i = 2; i < len; ++i)
        ans += 1.0 / i * t1[i];
}

void calc(int now)
{
    getz(now);
    while (!v.empty()) v.pop_back();
    for (int i = be[now]; i; i = li[i].next)
        if (!is[li[i].to])
            v.push_back(li[i].to);
    sort(v.begin(), v.end(), cmp);
    ++tot1;
    for (int k = 0; k < v.size(); ++k)
    {
        int to = v[k];
        ++tot;
        for (q.push(to), br[to] = tot, d[to] = 1; !q.empty();)
        {
            int now = q.front();
            q.pop();
            if (gt[d[now]][0] != tot)
                gt[d[now]][0] = tot,
                gt[d[now]][1] = 0;
            ++gt[d[now]][1];
            for (int i = be[now]; i; i = li[i].next)
            {
                int to = li[i].to;
                if (br[to] == tot || is[to]) continue;
                br[to] = tot;
                d[to] = d[now] + 1;
                q.push(to);
            }
        }
        for (int i = 1; i <= f[to]; ++i)
        {
            if (gt[i][0] != tot) break;
            ans += 1.0 / (i + 1) * gt[i][1];
        }
        calc2(f[to] + 1);
        for (int i = 1; i <= f[to]; ++i)
        {
            if (g[i + 1][0] != tot1)
                g[i + 1][0] = tot1,
                g[i + 1][1] = 0;
            if (gt[i][0] != tot) break;
            g[i + 1][1] += gt[i][1];
        }
    }
}

void solve(int now)
{
    int z = getz(now);
    is[z] = 1;
    calc(z);
    for (int i = be[z]; i; i = li[i].next)
        if (!is[li[i].to])
            solve(li[i].to);
}

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; ++i)
    {
        int fr, to;
        scanf("%d%d", &fr, &to);
        makeline(fr, to);
        makeline(to, fr);
    }
    solve(0);
    printf("%.4f", n + (double)ans * 2);
    fclose(stdin);fclose(stdout);
}

【FJOI2014-1】游记/题解

FJOI2014-1 “FJ为提高考试有效度 良心出题 成功保证所有人分数都不低于中位数”
我就是中位数啊XD 大家好啊~
WC刚被虐完就去了fz
各种颓废键盘基本没动的度过了两天(ban’nian)= =
考试的时候自然得hh
开考看题 第一题 想了20+min基本想出了正解
第二题 妈蛋 这不是昨天讲的原题?=-=
第三题 奇怪的几何 感觉20分说不定枚举中线什么的还是可以拿的233
//此时≈8:30 估分220
先pa第三题骗分 试了任意两点中点连线 中垂线 直接连线等各种奇怪的方法依然过不了= =
去上了个厕所决定不管这题了=-=
//此时≈9:20 估分200
第二题稍微回忆了下昨天讲课的东西 就开始敲
半个多小时后敲完了 发现样例过不了 手画了画 发现题目看错了XD
已经过去一半时间了 有点虚了=-=
想了十几分钟的正解 想的比较乱 也就没想出来
直接怒pa暴力磙粗=-=
//此时≈10:20 估分130
剩下第一题 奇怪的求树+树分治
树分治我就没打过几遍啊 但是感觉pa的出来于是就开始。。
一个多小时过去了//我考试的时候树分治写的不能更hh 300+行不能多说
写完了 调调样例 错了 改了改 过了 随便改了个数据 错了。。再也没有改出来QvQ
//此时12:00 估分30
中午略=-=
下午看成绩 第二题暴力全崩
//此时14:30 分数:0
【再见】

=第一题=
先求一个最短路图 然后再这个图上dfs 对于一个点的所有出点 按编号从小到大dfs
这样可以保证dfs树就是题目要求的树
然后在这棵树上跑树分治 f[i][j][2]表示前i棵子树 从根出发链长为j [0:最长长度][1:这个长度条件下的方案数]
对于第i+1棵子树 单独跑一个f'[i][j][2]意义一样 枚举这颗子树上链长 和f一起更新答案 然后用f‘更新f

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 30005;

struct line
{
    int to, next, v;
};

struct lin
{
    line li[200005];
    int be_[maxn], l;

    int be(int i) { return be_[i]; }
    int v(int i) { return li[i].v; }
    int to(int i) { return li[i].to; }
    int next(int i) { return li[i].next; }

    void makeline(int fr, int to, int v)
    {
        ++l;
        li[l].next = be_[fr];
        be_[fr] = l;
        li[l].to = to;
        li[l].v = v;
    }
}L1, L2;

queue<int> q;
stack<int> s;

int fa[maxn], n, m, k, f[maxn], g[maxn], d[maxn], fun[maxn][3], fun2[maxn][3], tot, tot2, tot1, b[maxn], dist[maxn], ans1, ans2, is[maxn], tb[maxn];
vector<pair<int, int> > v[maxn];

bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first > b.first;
}

void spfa()
{
    memset(dist, 0x3f, sizeof(dist));
    for (q.push(1), b[1] = 1, dist[1] = 0; !q.empty();)
    {
        int now = q.front();
        q.pop();
        for (int i = L1.be(now); i; i = L1.next(i))
        {
            int to = L1.to(i);
            if (dist[to] <= dist[now] + L1.v(i)) continue;
            dist[to] = dist[now] + L1.v(i);
            if (!b[to])
            {
                b[to] = 1;
                q.push(to);
            }
        }
        b[now] = 0;
    }
}

void get_dfs(int now)
{
    for (int i = L1.be(now); i; i = L1.next(i))
    {
        int to = L1.to(i);
        if (b[to] || dist[to] != dist[now] + L1.v(i)) continue;
        b[to] = 1;
        L2.makeline(now, to, L1.v(i));
        L2.makeline(to, now, L1.v(i));
        get_dfs(to);
    }
}

int get_center(int now)
{
    int tot = 0;
    for (q.push(now), b[now] = 1; !q.empty();)
    {
        int now = q.front();
        q.pop();
        f[now] = g[now] = 0;
        s.push(now);
        ++tot;
        for (int i = L2.be(now); i; i = L2.next(i))
        {
            int to = L2.to(i);
            if (b[to] || is[to]) continue;
            fa[to] = now;
            b[to] = 1;
            q.push(to);
        }
    }
    int ret = -1;
    for (; !s.empty();)
    {
        int now = s.top();
        s.pop();
        b[now] = 0;
        f[fa[now]] += ++f[now];
        g[fa[now]] = max(g[fa[now]], f[now]);
        g[now] = max(g[now], tot - f[now]);
        if (ret == -1 || g[now] < g[ret])
            ret = now;
    }
    return ret;
}

void re(int &a, int &b, int c, int d)
{
    if (d == 0) return;
    if (a < c) a = c, b = d;
    else if (a == c) b += d;
}

void calc(int now)
{
    ++tot, ++tot1;
    fun[0][0] = tot1, fun[0][1] = 0, fun[0][2] = 1;
    int tans1 = 0, tans2 = 0;
    d[now] = 0;

    for (int p = L2.be(now); p; p = L2.next(p))
    {
        int now = L2.to(p);
        if (is[now]) continue;
        ++tot2;
        fun2[1][0] = tot2, fun2[1][1] = L2.v(p), fun2[1][2] = 1;
        for (q.push(now), b[now] = tot, d[now] = 1, dist[now] = L2.v(p); !q.empty();)
        {
            int now = q.front();
            q.pop();
            for (int i = L2.be(now); i; i = L2.next(i))
            {
                int to = L2.to(i);
                if (is[to] || b[to] == tot) continue;
                b[to] = tot;
                d[to] = d[now] + 1;
                dist[to] = dist[now] + L2.v(i);
                if (fun2[d[to]][0] != tot2)
                    fun2[d[to]][0] = tot2, fun2[d[to]][1] = dist[to], fun2[d[to]][2] = 1;
                else
                    re(fun2[d[to]][1], fun2[d[to]][2], dist[to], 1);
                q.push(to);
            }
        }
       
        for (int i = 1; i <= k; ++i)
        {
            if (fun2[i][0] != tot2) break;
            if (fun[k - i - 1][0] != tot1) continue;
            re(tans1, tans2, fun2[i][1] + fun[k - i - 1][1], fun2[i][2] * fun[k - i - 1][2]);
        }
       
        for (int i = 1; i <= k; ++i)
        {
            if (fun2[i][0] != tot2) break;
            if (fun[i][0] != tot1)
                fun[i][0] = tot1, fun[i][1] = fun2[i][1], fun[i][2] = fun2[i][2];
            else
                re(fun[i][1], fun[i][2], fun2[i][1], fun2[i][2]);
        }
    }
    re(ans1, ans2, tans1, tans2);
}

void solve(int now)
{
    int center = get_center(now);
    is[center] = 1;
    calc(center);
    for (int i = L2.be(center); i; i = L2.next(i))
    {
        int to = L2.to(i);
        if (is[to]) continue;
        solve(to);
    }
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; ++i)
    {
        int fr, to, vv;
        scanf("%d%d%d", &fr, &to, &vv);
        v[fr].push_back(make_pair(to, vv));
        v[to].push_back(make_pair(fr, vv));
    }
    for (int i = 1; i <= n; ++i)
    {
        sort(v[i].begin(), v[i].end(), cmp);
        for (int j = 0; j < v[i].size(); ++j)
            L1.makeline(i, v[i][j].first, v[i][j].second);
    }
    spfa();
    b[1] = 1;
    get_dfs(1);
    ans1 = ans2 = 0;
    memset(b, 0, sizeof(b));
    solve(1);
    printf("%d %d", ans1, ans2);
    fclose(stdin);fclose(stdout);
}

=第二题=
首先对于两个重心的情况 可以在中间加一个点 变为一个重心的情况 记住答案-1
树形dp
f[i][j]表示以i为根的子树 大小为j的方案数
转移可以用背包把一个根的所有子树合并
计算f数组复杂度O(n^3)
然后对于根 求
g[i][j][k]表示 前i棵子树 最大节点数<=j 节点数和为k的方案数 更新用背包更新 直接枚举当前子树取多少 前面的一共取多少什么的 如果直接这样做 复杂度是O(n^4)的 可以把根的所有子树按size从小到大排序 这样就可以保证对于i j只要枚举O(第i棵子树大小) 即共为Σ(size[i])=n 降了一维 然后枚举最大的子树的大小 设为k 可以证明只要满足总节点数>k*2则这个根为唯一重心、
这里g数组的第二维表示的是最大节点数不超过j的方案数
可以用g[][j][] – g[][j – 1][]则可以表示最大节点数位j的方案数
即ans=Σ(g[m][k][k * 2] – g[m][k – 1][k * 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
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int inf = 10007;

struct line
{
    int next, to;
}li[1005];

int f[205][205], be[205], l, n, m, mx[205], t[205][2], tot, g[205][205][205];
vector<int> v[205], ve;

void re(int i, int v)
{
    if (t[i][0] != tot)
        t[i][0] = tot, t[i][1] = v;
    else
        t[i][1] = (t[i][1] + v) % inf;
}

int dp(int now, int last)
{
    int sum = 1;
    f[now][0] = f[now][1] = 1;
    for (int i = be[now]; i; i = li[i].next)
    {
        int to = li[i].to;
        if (to == last) continue;
        int tp = dp(to, now);
        ++tot;
        for (int j = 1; j <= tp; ++j)
            for (int k = 1; k <= sum; ++k)
                re(j + k, f[to][j] * f[now][k] % inf);

        for (int k = 1; k <= sum + tp; ++k)
            if (t[k][0] == tot)
                f[now][k] = (f[now][k] + t[k][1]) % inf;
        sum += tp;
    }
    return mx[now] = sum;
}

bool cmp(int a, int b)
{
    return mx[a] < mx[b];
}

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int dfs(int now, int last)
{
    int ans = 1;
    for (int i = 0; i < v[now].size(); ++i)
        if (v[now][i] != last)
            ans += dfs(v[now][i], now);
    return ans;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    int test, te = 0;
    scanf("%d", &test);
    while (test--)
    {
        memset(f, 0, sizeof(f));
        memset(be, 0, sizeof(be));
        memset(mx, 0, sizeof(mx));
        memset(t, 0, sizeof(t));
        memset(g, 0, sizeof(g));
        tot = m = l = 0;
        while (!ve.empty()) ve.pop_back();
        for (int i = 0; i < 205; ++i)
            while (!v[i].empty())
                v[i].pop_back();

        scanf("%d", &n);
        int ans = 0;
        for (int i = 1; i < n; ++i)
        {
            int fr, to;
            scanf("%d%d", &fr, &to);
            v[fr].push_back(to);
            v[to].push_back(fr);
        }
        if (n <= 2)
        {
            printf("Case %d: %d\n", ++te, 1);
            continue;
        }
        int mi = 0x7fffffff;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j < v[i].size(); ++j)
                mx[i] = max(mx[i], dfs(v[i][j], i));
            mi = min(mi, mx[i]);
        }

        int root = -1;
        mx[n + 1] = -1;
        bool br = false;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j < v[i].size(); ++j)
                if (mx[i] == mi && mx[v[i][j]] == mi)
                    makeline(i, n + 1),
                    makeline(n + 1, i),
                    root = n + 1,
                    br = true;
                else makeline(i, v[i][j]);
            if (root == -1 || mx[root] > mx[i]) root = i;
        }
        if (br) ++n, ans = -1;
        dp(root, 0);
        for (int i = be[root]; i; i = li[i].next)
            ve.push_back(li[i].to);
        sort(ve.begin(), ve.end(), cmp);
        m = ve.size();
        int sum = 0;
        for (int i = 0; i <= 200; ++i)
            g[0][i][0] = g[0][i][1] = 1;
        for (int i = 1; i <= m; ++i)
        {
            int now = ve[i - 1];
            for (int j = 1; j <= mx[now]; ++j)
            {
                int p = i == 1 ? j : min(j, mx[ve[i - 2]]);
                for (int k = 0; k <= j; ++k)
                    for (int l = 0; l <= sum; ++l)
                        g[i][j][k + l] = (g[i][j][k + l] + f[now][k] * g[i - 1][p][l]) % inf;
            }
            sum += mx[now];
        }
        ++ans;
        int mxx = mx[ve[m - 1]];
        for (int i = 1; i <= mxx; ++i)
            for (int j = i * 2; j <= sum; ++j)
                ans = (ans + g[m][i][j] - g[m][i - 1][j]) % inf;
        printf("Case %d: %d\n", ++te, (ans % inf + inf) % inf);
    }
    fclose(stdin);fclose(stdout);
}

=第三题=
根据点到直线距离公式 可以知道
ans=min(Σ(kxi-yi+b)^2 / (k^2 + 1))
这个可以三分套三分算出最优解(我怎么知道为什么QvQ
算这个式子这个略慢=-=
展开可以发现只要预处理出Σxi、Σxi、Σyi、Σxi^2、Σyi^2、Σxiyi
就可以O(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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;

struct point
{
    int x, y;
}p[maxn];

int n, x, y, a, b, c, sx, sy, sxx, syy, sxy;

ld sqr(ld a)
{
    return a * a;
}

ld calc2(ld k, ld b)
{/*
    ld t = 1 / (k * k + 1);
    ld ans = t * k * k * sxx + t * syy + t * b * b - 2 * k * sxy - 2 * sy * b + 2 * b * k * sx;
    if (ans < 10)
        cout << "Sdf";*/

    return (k * k * sxx + syy + n * b * b - 2 * k * sxy - 2 * sy * b + 2 * b * k * sx) / (k * k + 1);
    /*ld ans = 0;
    for (int i = 0; i < n; ++i)
        ans += sqr(k * p[i].x - p[i].y + b) / (k * k + 1);
    return ans;*/

}

ld calc(ld k)
{
    ld l = -1e9, r = 1e9;
    while (l + 1e-6 < r)
    {
        ld lmid = l + (r - l) / 3,
                     rmid = l + (r - l) / 3 * 2;
        ld v1 = calc2(k, lmid),
                     v2 = calc2(k, rmid);
        if (v1 < v2) r = rmid;
        else l = lmid;
    }
    return calc2(k, l);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    int test;
    scanf("%d", &test);
    for (int te = 1; te <= test; ++te)
    {
        scanf("%d%d%d%d%d%d", &n, &x, &y, &a, &b, &c);
        p[0].x = x, p[0].y = y;
        for (int i = 1; i < n; ++i)
            p[i].x = (a * p[i - 1].x * p[i - 1].x + b * p[i - 1].x + c) % 107,
            p[i].y = (a * p[i - 1].y * p[i - 1].y + b * p[i - 1].y + c) % 107;
        sx = sy = sxx = syy = sxy = 0;
        for (int i = 0; i < n; ++i)
            sx += p[i].x,
            sy += p[i].y,
            sxx += sqr(p[i].x),
            syy += sqr(p[i].y),
            sxy += p[i].x * p[i].y;
        ld l = -1e9, r = 1e9;
        while (l + 1e-6 < r)
        {
            ld lmid = l + (r - l) / 3,
                         rmid = l + (r - l) / 3 * 2;
            ld v1 = calc(lmid),
                         v2 = calc(rmid);
            if (v1 < v2) r = rmid;
            else l = lmid;
        }
        printf("Case %d: %.5f\n", te, (double)calc(l) * acos(-1) / n);
    }
    fclose(stdin);fclose(stdout);
}

下一场考完还不能当队长我也不过如此了啊233

 

 

BZOJ 1468: [POJ1741]Tree

求树上距离小于等于k的点对数

使用传说中的树分治算法!
本蒟蒻本来不会这个神算法的。。直到hhs神犇教了我。。然后发现其实这个算法也不难0 0.
(另外kd-tree也是hhs神犇教本蒟蒻的 OrzOrzOrz)

树分治有边分治和点分治 这题可以用点分治解决
所谓点分治 对于一条树路径 只有经过或不经过一个点的情况
对于不经过的情况 把一颗树按这个点拆成好几颗分治就行了
考虑经过这个点的情况
对于这题 可以对这个点延伸出的几颗子树各做一次bfs
算出每颗子树中有出现的距离值
对于一棵树的距离值数组 把它排序(hash也可以)
然后枚举两颗子树 对它们做一次单调队列算答案即可
另外对于这个点就是树路径的一个端点的情况要特殊考虑
//这里用枚举两棵子树的方法可能被菊花图卡
//可把所有距离排序 求一次ans1
//再对每棵子树分别求一个自己对自己的ans2
//ans1-Σans2即为最后的ans
//因为这题数据没有卡这个的 我就没用这个算法。。

至于这个点要选哪个点 这个至关重要
每次选取当前树的重心 这样能保证时间复杂度是nlogn级的
数的重心的定义就是如果一个点是树的重心 那么他的子树节点数的最大值最小
—————-code————–

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
const int maxn = 40005;
struct line
{
  int next, to, v;
}li[maxn * 2];
struct range
{
  int l, r;
  range(int a = 0, int b = 0) : l(a), r(b) {}
}g[maxn];
struct point
{
  int now, fa;
  ll va;
  point(int a = 0, int c = 0, ll b = 0) : now(a), fa(c), va(b) {}
};
int be[maxn], b[maxn], bb[maxn], n, m, sum[maxn], z, mi, l;
ll a[maxn], ans;
queue<int> q;
queue<point> qq;
int getnum(int no)
{
  q.push(no);
  b[no] = no;
  int ans = 0;
  while (!q.empty())
  {
    ++ans;
    int now = q.front();
    q.pop();
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (bb[to] || b[to] == no) continue;
      b[to] = no;
      q.push(to);
    }
  }
  return ans;
}
int getz(int now, int tot, int fa)
{
  int mx = 0, sum = 0;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (to == fa || bb[to]) continue;
    int t = getz(to, tot, now);
    mx = max(mx, t);
    sum += t;
  }
  ++sum;
  mx = max(mx, tot – sum);
  if (mx < mi) mi = mx, z = now;
  return sum;
}
int bfs(int now, int l, int va)
{
  qq.push(point(now, 0, va));
  while (!qq.empty())
  {
    point now = qq.front();
    qq.pop();
    a[l++] = now.va;
    if (now.va <= m) ++ans;
    for (int i = be[now.now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (bb[to] || to == now.fa) continue;
      qq.push(point(to, now.now, now.va + li[i].v));
    }
  }
  return l – 1;
}
void getans(range u, range v)
{
  int r = v.r;
  for (int i = u.l; i <= u.r; ++i)
  {
    while (r >= v.l && a[r] + a[i] > m) –r;
    ans += r – v.l + 1;
  }
}
void dfs(int now)
{
  mi = 0x7fffffff;
  getz(now, getnum(now), 0);
  int t = z;
  bb[t] = 1;
  int la = 0, k = 0;
  for (int i = be[t]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (bb[to]) continue;
    g[k].l = la;
    la = g[k++].r = bfs(to, la, li[i].v);
    ++la;
  }
  for (int i = 0; i < k; ++i) sort(a + g[i].l, a + g[i].r + 1);
  for (int i = 0; i < k; ++i)
    for (int j = i + 1; j < k; ++j)
      getans(g[i], g[j]);
  for (int i = be[t]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (bb[to]) continue;
    dfs(to);
  }
}
void makeline(int fr, int to, int v)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
  li[l].v = v;
}
int main()
{
  scanf(“%d”, &n);
  for (int i = 1; i < n; ++i)
  {
    int fr, to, v;
    scanf(“%d%d%d”, &fr, &to, &v);
    makeline(fr, to, v);
    makeline(to, fr, v);
  }
  scanf(“%d”, &m);
  dfs(1);
  printf(“%lld”, ans);
}