【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

 

 

【World Finals】2008G

【试题编号】
2008G
【名称】
Net Loss
【题目大意】
给一个图像 让你画两条线段 使他们差的平方积分最小 两条线段一定交于x=c的直线上
【算法讨论】
先三分直线上的y 然后分别三分两边的y即可
【时空复杂度】
O(nlogn)
O(1)
【code】

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
#include <cstdio>
#include <cstring>
#include <algorithm>
const long double eps = 1e-4;
int n;
long double c,a0,a1,b0,b1;
struct Function
{
    long double a[30];
    int len;
    Function():a(),len(){}
    Function(const long double x1,const long double y1,const long double x2,const long double y2):a(),len()
    {
        memset(a,0,sizeof a);
        len = 2;
        a[1] = (y2 - y1)/(x2 - x1);
        a[0] = -a[1] * x1 + y1;
    }
}p;
long double calc_val(const Function &y,long double x)
{
    long double res = .0,t = 1;
    for (int i = 0; i < y.len; ++i,t *= x)
        res += y.a[i]*t;
    return res;
}
Function operator*(const Function &a,const Function &b)
{
    Function c;
    c.len = a.len + b.len - 1;
    memset(c.a,0,sizeof c.a);
    for (int i = 0; i < a.len; ++i)
        for (int j = 0; j < b.len; ++j)
            c.a[i + j] += a.a[i] * b.a[j];
    return c;
}
Function operator-(const Function &a,const Function &b)
{
    Function c;
    memset(c.a,0,sizeof c.a);
    c.len = std::max(a.len,b.len);
    for (int i = 0; i < c.len; ++i)
        c.a[i] = a.a[i] - b.a[i];
    return c;
}
Function anti(const Function &a)
{
    Function c;
    c.len = a.len + 1; memset(c.a,0,sizeof c.a);
    for (int i = 0; i < a.len; ++i)
        c.a[i + 1] = a.a[i]/(i + 1);
    return c;
}
long double defi_integral(const Function &a,const long double l,const long double r){return calc_val(anti(a),r) - calc_val(anti(a),l);}
long double sub_calc(const long double mid1,const long double mid2,long double x1,long double x2)
{
    Function t = Function(x1,mid1,x2,mid2) - p;
    if (x1 > x2) std::swap(x1,x2);
    return defi_integral(t*t,x1,x2);
}
long double sub_val(const long double mid,const long double x1,const long double x2)
{
    long double l = -1e4,r = 1e4;
    while (l + eps < r) {
        const long double mid1 = (r - l)/3 + l,mid2 = (r - l)/3*2 + l;
        //printf("%.3f %.3f\n",l,r);
        if (sub_calc(mid1,mid,x1,x2) < sub_calc(mid2,mid,x1,x2)) r = mid2;
        else l = mid1;
    }
    Function t = Function(x1,r,x2,mid);
    sub_calc(0.633,mid,x1,x2);
    if (x1 < x2) a1 = t.a[1],a0 = t.a[0];
    else b1 = t.a[1],b0 = t.a[0];
    return sub_calc(r,mid,x1,x2);
}
long double val(const long double mid){return sub_val(mid,-1,c) + sub_val(mid,1,c);}
int main()
{
    int testcase = 0;
    while (scanf("%d",&n),n) {
        memset(p.a,0,sizeof p.a);
        for (int i = 0; i <= n; ++i)
        {
            double d;
            scanf("%lf", &d);
            p.a[n - i] = d;
        }
        p.len = n + 1;
        double t;
        scanf("%lf",&t);
        c = t;
        long double l = -1e4,r = 1e4;
        while (l + eps < r) {
            const long double mid1 = (r - l)/3 + l,mid2 = (r - l)/3*2 + l;
            if (val(mid1) > val(mid2)) l = mid1;
            else r = mid2;
        }
        //printf("%.3f\n",r);
        printf("Case %d: %.3f %.3f %.3f %.3f\n",++testcase,(double)a1,(double)a0,(double)b1,(double)b0);
    }
}