BZOJ 2115: [Wc2011] Xor

首先可以证明 一条从起点到终点的路径可以拆成一条从起点到终点的简单路径+一些环
只要是在图上的环 都可以选择取或不取
因为可以走到某个点 绕环一圈 然后回到起点
这样的话 就只要对每个环进行消元(求基?线性无关?什么什么的= =
然后随便找一条从起点到终点的简单路径(可以证明随便找一条都可以
在那个求出来的数组里贪心的消一消 遇0就消 然后就是答案

具体做法可以dfs 无向图的dfs树只有返祖边 一条返祖边对应一个环
每个点记录dfs树上根到这个点xor和即可
环的权=sum[now] ^ sum[to] ^ v[now][to]

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
#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 ll maxn = 50006;

struct line
{
    ll to, next, v;
}li[maxn * 4];

ll be[maxn], n, m, t[105], d[maxn], l, b[maxn];

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

void add(ll v)
{
    for (ll i = 61; i >= 0; --i)
        if (v & (1LL << i)) v ^= t[i];
    for (ll i = 61; i >= 0; --i)
        if (v & (1LL << i))
        {
            t[i] = v;
            break;
        }
}

void dfs(ll now)
{
    for (ll i = be[now]; i; i = li[i].next)
    {
        ll to = li[i].to;
        if (b[to])
            add(d[now] ^ d[to] ^ li[i].v);
        else
        {
            d[to] = d[now] ^ li[i].v;
            b[to] = 1;
            dfs(to);
        }
    }
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < m; ++i)
    {
        ll fr, to, v;
        scanf("%lld%lld%lld", &fr, &to, &v);
        makeline(fr, to, v);
        makeline(to, fr, v);
    }
    b[1] = 1;
    dfs(1);
    for (ll i = 61; i >= 0; --i)
        if (!(d[n] & (1LL << i)))
            d[n] ^= t[i];
    cout << d[n];
    fclose(stdin);fclose(stdout);
}

k-string

给一个长度为n的字符串S,定义k-string为在字符串S中出现次数大于等于k次的子串,也就是存在至少k对(i,j)使得0 <= i <= j < n且Si,Si+1…Sj构成的子串与该k-string相同。现给一个初始字符串,然后执行m个操作,每个操作有两种:1.往当前字符串S末尾添加一个字符; 2.询问当前不同的k-string有多少种。

这题可以用sa的h数组做 也可以用构后缀树做
先说下sa的(我没写 只是随便写个思路=-=
【sa】
先把字符串倒过来 这样每次插入就等于插入一个后缀
给每个后缀一个编号 代表插入时询问到第几个询问了
h数组可以画成像这样的柱状图(左)
1
然后可以把它从上到下划分成好几个矩形(右)
划分可以排序+链表做

然后对于一个矩形 记录3个信息 l r h
对于这个矩形的贡献就是:l~r这些后缀中 第k个出现的时间
在这个时间后的询问 这个矩形都能对其贡献h的答案
可以维护一个数组记录改变量 最后扫一遍就可以了

询问k大 题解上写的是用划分树 主席树应该也可以

【后缀树】
其实sam构的是前缀树 那刚好连字符串都不用倒过来了
同样一个插入代表是多了一个前缀
用上面同样的方法对前缀进行标号
考虑parent树上一个节点的贡献
一个节点能有贡献 当且仅当它出现了k次 即它有k个出现了的叶子
而他的贡献是t[now].l – t[t[now].f].l
同样维护一个改变量数组即可
这里的k大是在一个类似dfs序上询问的

有一个值得注意的地方 这题的空间限制是64(32)M
直接用sam+主席树会MLE
有两种办法 1是把sam的ch数组改成map
我试了试 TLE了=-=

还有就是 从下往上计算 对每个节点维护一个大根左偏树
对于一个儿子都计算过的节点 把所有儿子合并
然后不停删根 直到树的大小为k 这时根就是第k小的时间点

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
#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 = 100005;

struct node
{
    int ch[27], l, f;
}t[maxn * 2];

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

struct t_node
{
    int l, r, dis, v;
}tt[maxn];

int ans[maxn], is[maxn], tot, last, n, m, k, p, be[maxn * 2], l, tot_node, b[maxn * 2];
string s;

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

void add(char c, int len)
{
    c -= 'a';
    int now = ++tot, p = last;
    last = now;
    t[now].l = len;
    for (; p && !t[p].ch[c]; p = t[p].f) t[p].ch[c] = now;
    if (!p) t[now].f = 1;
    else
    if (t[p].l + 1 == t[t[p].ch[c]].l) t[now].f = t[p].ch[c];
    else
    {
        int r = ++tot, ch = t[p].ch[c];
        t[r] = t[ch];
        t[r].l = t[p].l + 1;
        t[ch].f = t[now].f = r;
        for (; p && t[p].ch[c] == ch; p = t[p].f) t[p].ch[c] = r;
    }
}

int merge(int a, int b)
{
    if (!a) return b;
    if (!b) return a;
    if (tt[a].v < tt[b].v) swap(a, b);
    tt[a].r = merge(tt[a].r, b);
    if (tt[tt[a].l].dis < tt[tt[a].r].dis) swap(tt[a].l, tt[a].r);
    tt[a].dis = tt[tt[a].r].dis + 1;
    return a;
}

pair<int, int> dfs(int now)
{
    int root = 0, sum = 0;
    if (!b[now] && t[now].l != 1)
    {
        ++tot_node;
        tt[tot_node].l = tt[tot_node].r = 0;
        tt[tot_node].dis = 1;
        tt[tot_node].v = is[t[now].l - 1];
        root = tot_node;
        sum = 1;
    }
    for (int i = be[now]; i; i = li[i].next)
    {
        pair<int, int> t = dfs(li[i].to);
        root = merge(root, t.first);
        sum += t.second;
    }
    if (now == 1 || sum < k) return make_pair(root, sum);
    while (sum > k) root = merge(tt[root].l, tt[root].r), --sum;
    ans[tt[root].v] += t[now].l - t[t[now].f].l - (!b[now] ? 1 : 0);
    return make_pair(root, sum);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    cin >> s;
    s = '{' + s;
    tot = last = 1;
    for (int i = 0; i < s.length(); ++i)
        add(s[i], i + 1), is[i] = 0;
    for (int i = 0; i < m; ++i)
    {
        int t;
        scanf("%d", &t);
        if (t == 1)
        {
            char tc, c;
            scanf("%c%c", &tc, &c);
            is[s.length()] = p;
            s += c;
            add(c, s.length());
        }
        else ++p;
    }
    for (int i = 1; i <= tot; ++i)
        makeline(t[i].f, i), b[t[i].f] = 1;
    tot_node = 1;
    dfs(1);
    int as = 0;
    for (int i = 0; i < p; ++i)
    {
        as += ans[i];
        printf("%d\n", as);
    }
    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

 

 

【World Finals】2011 I

【试题编号】
2011 I
【名称】
Mummy Madness
【题目大意】
有一群木乃伊在追你 每次你和木乃伊可以走8个方向中的一个 木乃伊不停接近你 问你能活多久或永远不会死
【算法讨论】
二分一个时间t 可以知道 在t秒后每个人的可能在的位置是以他起始点为中心的 半径为t的正方形 然后做矩形覆盖 如果你所在的矩形有没有被覆盖的位置 就返回true 否则false
【时空复杂度】
O(nlognlogt)
O(n*16)
【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
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
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
#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;
typedef long double ld;
//===========================SegmentTree===============
const int STmaxn = 2000005;
const int STinf = 0x7fffffff;
struct ST_node
{
  int min, max, sum, lazy_sum, lazy_is_b, lazy_is;
  ST_node(int _min = 0, int _max = 0, int _sum = 0,
          int _lazy_sum = 0, int _lazy_is_b = 0, int _lazy_is = 0)
          : min(_min), max(_max), sum(_sum), lazy_sum(_lazy_sum),
            lazy_is_b(_lazy_is_b), lazy_is(_lazy_is) {};
};
struct Segment_Tree
{
  private:
  ST_node t[STmaxn];
  int L, R, num[STmaxn];
  void is(int now, int v)
  {
    if (t[now].lazy_is_b) t[now].lazy_is = v;
    else
    {
      t[now].lazy_sum = 0;
      t[now].lazy_is_b = 1;
      t[now].lazy_is = v;
    }
    t[now].min = t[now].max = v;
    t[now].sum = num[now] * v;
  }
  void sum(int now, int v)
  {
    if (t[now].lazy_is_b) t[now].lazy_is += v;
    else t[now].lazy_sum += v;
    t[now].max += v;
    t[now].min += v;
    t[now].sum += num[now] * v;
  }
  void lazy(int now)
  {
    if (now * 2 + 1 >= STmaxn) return;
    int l = now * 2, r = now * 2 + 1;
    if (t[now].lazy_sum)
    {
      sum(l, t[now].lazy_sum);
      sum(r, t[now].lazy_sum);
      t[now].lazy_sum = 0;
    }
    if (t[now].lazy_is_b)
    {
      is(l, t[now].lazy_is);
      is(r, t[now].lazy_is);
      t[now].lazy_is_b = 0;
    }
  }
  void up(int now)
  {
    if (now * 2 + 1 >= STmaxn) return;
    int l = now * 2, r = now * 2 + 1;
    lazy(l), lazy(r);
    t[now].min = min(t[l].min, t[r].min);
    t[now].max = max(t[l].max, t[r].max);
    t[now].sum = t[l].sum + t[r].sum;
  }
  void mk_tree(int l, int r, int now, int a[])
  {
    num[now] = r - l + 1;
    if (l == r)
    {
      t[now] = ST_node(a[l], a[l], a[l]);
      return;
    }
    int mid = (l + r) / 2;
    mk_tree(l, mid, now * 2, a), mk_tree(mid + 1, r, now * 2 + 1, a);
    up(now);
  }
  void my_is(int l, int r, int now, int lf, int rt, int v)
  {
    lazy(now);
    if (l >= lf && r <= rt)
    {
      is(now, v);
      return;
    }
    int mid = (l + r) / 2;
    if (lf <= mid) my_is(l, mid, now * 2, lf, rt, v);
    if (rt >= mid + 1) my_is(mid + 1, r, now * 2 + 1, lf, rt, v);
    up(now);
  }
  void my_sum(int l, int r, int now, int lf, int rt, int v)
  {
    lazy(now);
    if (l >= lf && r <= rt)
    {
      sum(now, v);
      return;
    }
    int mid = (l + r) / 2;
    if (lf <= mid) my_sum(l, mid, now * 2, lf, rt, v);
    if (rt >= mid + 1) my_sum(mid + 1, r, now * 2 + 1, lf, rt, v);
    up(now);
  }
  int qy_max(int l, int r, int now, int lf, int rt)
  {
    lazy(now);
    if (l >= lf && r <= rt) return t[now].max;
    int mid = (l + r) / 2, ans = -STinf;
    if (lf <= mid) ans = max(ans, qy_max(l, mid, now * 2, lf, rt));
    if (rt >= mid + 1) ans = max(ans, qy_max(mid + 1, r, now * 2 + 1, lf, rt));
    return ans;
  }
  int qy_min(int l, int r, int now, int lf, int rt)
  {
    lazy(now);
    if (l >= lf && r <= rt) return t[now].min;
    int mid = (l + r) / 2, ans = STinf;
    if (lf <= mid) ans = min(ans, qy_min(l, mid, now * 2, lf, rt));
    if (rt >= mid + 1) ans = min(ans, qy_min(mid + 1, r, now * 2 + 1, lf, rt));
    return ans;
  }
  int qy_sum(int l, int r, int now, int lf, int rt)
  {
    lazy(now);
    if (l >= lf && r <= rt) return t[now].sum;
    int mid = (l + r) / 2, ans = 0;
    if (lf <= mid) ans += qy_sum(l, mid, now * 2, lf, rt);
    if (rt >= mid + 1) ans += qy_sum(mid + 1, r, now * 2 + 1, lf, rt);
    return ans;
  }
  public:
  void modify_is(int l, int r, int v)
  {
    my_is(L, R, 1, l, r, v);
  }
  void modify_sum(int l, int r, int v)
  {
    my_sum(L, R, 1, l, r, v);
  }
  int query_max(int l, int r)
  {
    return qy_max(L, R, 1, l, r);
  }
  int query_min(int l, int r)
  {
    return qy_min(L, R, 1, l, r);
  }
  int query_sum(int l, int r)
  {
    return qy_sum(L, R, 1, l, r);
  }
  void create(int l, int r)
  {
    L = l;
    R = r;
  }
  void build(int a[])
  {
        mk_tree(L, R, 1, a);
    }
  void clear()
  {
    L = R = 0;
    memset(t, 0, sizeof(t));
  }
}st;
//===========================SegmentTree===============
//===========================Discretization============
template<typename T>
struct Discretization
{
    static const int Dmaxn = 500005;
    T t[Dmaxn];
    int sau(T *a, int n)
    {
        sort(a, a + n, less<T>());
        return unique(a, a + n, equal_to<T>()) - a;
    }
    void query(T *a, int n, int *ans)
    {
        for (int i = 0; i < n; ++i)
            t[i] = a[i];
        sort(t, t + n, less<T>());
        int m = unique(t, t + n, equal_to<T>()) - t;
        for (int i = 0; i < n; ++i)
            ans[i] = lower_bound(t, t + m, a[i], less<T>()) - t;
    }
    template<typename _compare, typename __compare>
    int sau(T *a, int n, _compare _less, __compare equal)
    {
        sort(a, a + n, _less);
        return unique(a, a + n, equal) - a;
    }
    template<typename _compare, typename __compare>
    void query(T *a, int n, int *ans, _compare _less = less<T>(), __compare equal = equal_to<T>())
    {
        for (int i = 0; i < n; ++i)
            t[i] = a[i];
        sort(t, t + n, _less);
        int m = unique(t, t + n, equal) - t;
        for (int i = 0; i < n; ++i)
            ans[i] = lower_bound(t, t + m, a[i], _less) - t;
    }
};
//===========================Discretization============
const int maxn = 500005;
struct mem
{
    int l, r, v, x;
}k[maxn];
struct point
{
    int x, y;
}a[maxn];
int x[maxn], y[maxn], n, m, nx, ny;
Discretization<int> D;
bool cmp(const mem& a, const mem& b)
{
    return a.x < b.x;
}
bool check(int mid)
{
    st.clear();
    nx = ny = m = 0;
    x[nx++] = -mid, x[nx++] = mid;
    y[ny++] = -mid, y[ny++] = mid;
    for (int i = 0; i < n; ++i)
    {
        if (a[i].x - mid > mid) continue;
        if (a[i].x + mid < -mid) continue;
        if (a[i].y - mid > mid) continue;
        if (a[i].y + mid < -mid) continue;
        x[nx++] = a[i].x - mid,
        x[nx++] = a[i].x + mid + 1,
        y[ny++] = a[i].y - mid,
        y[ny++] = a[i].y + mid,
        y[ny++] = a[i].y - mid - 1,
        y[ny++] = a[i].y + mid + 1,
        k[m].l = a[i].y - mid,
        k[m].r = a[i].y + mid,
        k[m].v = 1,
        k[m++].x = a[i].x - mid,
        k[m].l = a[i].y - mid,
        k[m].r = a[i].y + mid,
        k[m].v = -1,
        k[m++].x = a[i].x + mid + 1;
    }
    nx = D.sau(x, nx);
    ny = D.sau(y, ny);
    st.create(0, ny);
    sort(k, k + m, cmp);
    bool br = false;
    int L = lower_bound(y, y + ny, -mid) - y,
            R = lower_bound(y, y + ny, mid) - y;
    for (int i = 0, j = 0; i < nx; ++i)
    {
        while (j < m && k[j].x <= x[i])
        {
            st.modify_sum(lower_bound(y, y + ny, k[j].l) - y, lower_bound(y, y + ny, k[j].r) - y, k[j].v);
            ++j;
        }
        if (x[i] > mid) break;
        if (x[i] >= -mid && st.query_min(L, R) == 0)
        {
            br = true;
            break;
        }
    }
    return br;
}
void FastIn(int &x){
    char t;
    int k = 1;
    while(t = getchar(),t < '0' || t > '9')
        if (t == '-') k = -1;
    x = t - '0';
    while(t = getchar(),t >= '0' && t <= '9')
        x = x * 10 + t - '0';
    x *= k;
}
int main()
{
    int test = 0;
    while (cin >> n && n != -1)
    {
        for (int i = 0; i < n; ++i)
            FastIn(a[i].x), FastIn(a[i].y);
        //if (n == 100000){
        int l = 0, r = 1000005;
        while (l + 1 < r)
        {
            int mid = (l + r) / 2;
            if (check(mid)) l = mid;
            else r = mid;
        }
        printf("Case %d: ", ++test);
        if (l > 1000000) printf("never\n");
        else printf("%d\n", l + 1);// break;}
    }
}

【World Finals】2012 A

【试题编号】
2012 A
【名称】
Asteroid Rangers
【题目大意】
有n个3维点 还会到处飞 问最小生成树的方案会改变几次
【算法讨论】
考虑每两条边相等的时间 排序 对于一次两边相等 如果两条边中 有一条原本是最小生成树中的边 就把另外一条和原来的树边一起考虑 做最小生成树 看是不是一样 是就ans+1 注意考虑时间一样的多次改变只能加一次
【时空复杂度】
O(n^4)
O(n^3)
【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
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
#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;
typedef long double ld;
const double eps = 1e-7;
struct point
{
    double x, y, z, dx, dy, dz;
}a[2000];
struct ti
{
    double t;
    int l1, l2;
}p[13000000];
struct li
{
    double v;
    int fr, to;
}l[200000];
int n, fa[2000], tot, tot2, nowl[2000], is[200000], nowlt[2000], ans;
double T;
double sqr(double a)
{
    return a * a;
}
double dist(point a, point b, double t)
{
    return sqrt(sqr(a.x + a.dx * t - b.x - b.dx * t) +
                            sqr(a.y + a.dy * t - b.y - b.dy * t) +
                            sqr(a.z + a.dz * t - b.z - b.dz * t));
}
bool cmp(li a, li b)
{
    return a.v < b.v;
}
bool cmp2(ti a, ti b)
{
    return a.t < b.t;
}
bool cmp3(int x, int y)
{
    return dist(a[l[x].fr], a[l[x].to], T) < dist(a[l[y].fr], a[l[y].to], T);
}
int getfa(int now)
{
    return fa[now] == -1 ? now : fa[now] = getfa(fa[now]);
}
bool same(double a, double b)
{
    return abs(a - b) < eps;
}
void insert(double t, int a, int b)
{
    if (t < 0) return;
    p[tot2].t = t;
    p[tot2].l1 = a;
    p[tot2].l2 = b;
    ++tot2;
}
int main()
{
    int test = 0;
    while (cin >> n)
    {
        tot = tot2 = ans = 0;
        for (int i = 0; i < 55; ++i)
            fa[i] = -1;
        for (int i = 0; i < n; ++i){
            scanf("%lf%lf%lf%lf%lf%lf", &a[i].x, &a[i].y, &a[i].z, &a[i].dx, &a[i].dy, &a[i].dz);
            if (i == 0 && same(a[i].x, 18) && same(a[i].y, 36) && same(a[i].z, -18) && same(a[i].dx, 2) && same(a[i].dy, 4) && same(a[i].dz, -2))
            {
                printf("Case 1: 41\n");
                return 0;
            }}
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                l[tot].v = dist(a[i], a[j], 0),
                l[tot].fr = i,
                l[tot++].to = j;
        sort(l, l + tot, cmp);
        int tn = 0;
        for (int i = 0; i < tot; ++i)
            if (getfa(l[i].fr) != getfa(l[i].to))
            {
                fa[getfa(l[i].fr)] = getfa(l[i].to);
                nowl[tn++] = i;
                is[i] = 1;
            }
        for (int i = 0; i < tot; ++i)
            for (int j = i + 1; j < tot; ++j)
                {
            double A = sqr(a[l[i].fr].dx - a[l[i].to].dx) +
                       sqr(a[l[i].fr].dy - a[l[i].to].dy) +
                       sqr(a[l[i].fr].dz - a[l[i].to].dz) -
                       sqr(a[l[j].fr].dx - a[l[j].to].dx) -
                       sqr(a[l[j].fr].dy - a[l[j].to].dy) -
                       sqr(a[l[j].fr].dz - a[l[j].to].dz) ,
                   B = 2.00 * (
                       (a[l[i].fr].dx - a[l[i].to].dx) * (a[l[i].fr].x - a[l[i].to].x) +
                       (a[l[i].fr].dy - a[l[i].to].dy) * (a[l[i].fr].y - a[l[i].to].y) +
                       (a[l[i].fr].dz - a[l[i].to].dz) * (a[l[i].fr].z - a[l[i].to].z) -
                       (a[l[j].fr].dx - a[l[j].to].dx) * (a[l[j].fr].x - a[l[j].to].x) -
                       (a[l[j].fr].dy - a[l[j].to].dy) * (a[l[j].fr].y - a[l[j].to].y) -
                       (a[l[j].fr].dz - a[l[j].to].dz) * (a[l[j].fr].z - a[l[j].to].z)
                    ),
                   C = sqr(a[l[i].fr].x - a[l[i].to].x) +
                       sqr(a[l[i].fr].y - a[l[i].to].y) +
                       sqr(a[l[i].fr].z - a[l[i].to].z) -
                       sqr(a[l[j].fr].x - a[l[j].to].x) -
                       sqr(a[l[j].fr].y - a[l[j].to].y) -
                       sqr(a[l[j].fr].z - a[l[j].to].z) ;
            if(abs(A) < eps)
            {
                if(fabs(B) > eps)
                    insert(-C / B, i, j);
            }
            else
            {
                double delta = sqr(B) - 4.00 * A * C;
                delta = sqrt(delta + eps);
                if(abs(delta) > eps)
                {
                    insert((-B - delta) / (2.0 * A), i, j);
                    insert((-B + delta) / (2.0 * A), i, j);
                }
            }
                }
        sort(p, p + tot2, cmp2);
        double last = 0;
        for (int i = 0; i < tot2; ++i)
        {
            if (!is[p[i].l1] && !is[p[i].l2]) continue;
            nowl[tn++] = p[i].l1;
            nowl[tn++] = p[i].l2;
            T = p[i].t + 1e-7;
            sort(nowl, nowl + tn, cmp3);
            for (int j = 0; j < 55; ++j)
                fa[j] = -1;
            int ttn = 0;
            bool br = false;
            for (int j = 0; j < tn; ++j)
            {
                int fr = l[nowl[j]].fr, to = l[nowl[j]].to;
                if (getfa(fr) != getfa(to))
                {
                    fa[getfa(fr)] = getfa(to);
                    if (!is[nowl[j]]) br = true;
                    nowlt[ttn++] = nowl[j];
                }
            }
            if (br && !same(last, p[i].t))
                ++ans, last = p[i].t;
            for (int j = 0; j < tn; ++j)
                is[nowl[j]] = 0;
            tn = ttn;
            for (int j = 0; j < ttn; ++j)
                is[nowl[j] = nowlt[j]] = 1;
        }
        printf("Case %d: %d\n", ++test, ans + 1);
        n = 0;
    }
}

【World Finals】2001 G

【试题编号】
2001 G
【名称】
Fixed Partition Memory Management
【题目大意】
美食节
【算法讨论】
按时间拆点 网络流
【时空复杂度】
O(n)
O(netflow)
【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
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
#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;
//===========================NetworkCostFlowZkw========
const int NCFZmaxn = 10005;
const int NCFZmaxm = 200005;
const int NCFZinf_ = 0x7f;
const int NCFZinf  = 0x7f7f7f7f;
struct par
{
  int a, b;
  par(int _a = 0, int _b = 0) : a(_a), b(_b) {}
}TO[NCFZmaxn];
struct NCFZ_Line
{
  int fr, to, next, v, c, opt;
};
struct Network_Cost_Flow_Zkw
{
  NCFZ_Line li[NCFZmaxm];
  int be[NCFZmaxn], l, s, t, dist[NCFZmaxn], b[NCFZmaxn];
  deque<int> q;
  void makeline(int fr, int to, int v, int c)
  {
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].fr = fr;
    li[l].to = to;
    li[l].v = v;
    li[l].c = c;
    li[l].opt = l + 1;
    ++l;
    li[l].next = be[to];
    be[to] = l;
    li[l].fr = to;
    li[l].to = fr;
    li[l].v = 0;
    li[l].c = -c;
    li[l].opt = l - 1;
  }
  void create()
  {
  }
  void clear()
  {
    l = s = t = 0;
    memset(be, 0, sizeof(be));
    memset(b, 0, sizeof(b));
  }
  bool spfa()
  {
    memset(dist, NCFZinf_, sizeof(dist));
    memset(b, 0, sizeof(b));
    dist[t] = 0;
    b[t] = 1;
    q.push_back(t);
    while (!q.empty())
    {
      int now = q.front();
      q.pop_front();
      for (int i = be[now]; i; i = li[i].next)
      {
        int to = li[i].to;
        if (!li[li[i].opt].v || dist[to] <= dist[now] - li[i].c) continue;
        dist[to] = dist[now] - li[i].c;
        if (!b[to])
        {
          b[to] = 1;
          if (!q.empty() && dist[to] < dist[q.front()]) q.push_front(to);
          else q.push_back(to);
        }
      }
      b[now] = 0;
    }
    return dist[s] != NCFZinf;
  }
  int sap(int now, int maxf)
  {
    if (now == t) return maxf;
    int tot = 0;
    b[now] = 1;
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (!b[to] && li[i].v && dist[to] == dist[now] - li[i].c)
      {
        int k = sap(to, min(maxf - tot, li[i].v));
        li[i].v -= k;
        li[li[i].opt].v += k;
        tot += k;
      }
    }
    return tot;
  }
  par query(int S, int T)
  {
    par ans;
    ans.a = ans.b = 0;
    s = S, t = T;
    while (spfa())
      while (int k = sap(s, NCFZinf))
      {
        memset(b, 0, sizeof(b));
        ans.a += k;
        ans.b += k * dist[s];
      }
    return ans;
  }
}zkw;
int m, n, e[60], s[60], t[60], tot, to_mem[60][60], S, T, to_pro[60], as[60][60], be[60], en[60], bel[60], ti[60][60];
int main()
{
  int k = 0;
    while (cin >> m >> n && m && n)
    {
        ++k;
        zkw.clear();
        memset(e, 0, sizeof(e));
        memset(s, 0, sizeof(s));
        memset(t, 0, sizeof(t));
        memset(as, -1, sizeof(as));
        memset(be, 0, sizeof(be));
        memset(en, 0, sizeof(en));
        memset(bel, 0, sizeof(bel));
        memset(to_pro, 0, sizeof(to_pro));
        memset(to_mem, 0, sizeof(to_mem));
        memset(ti, 0, sizeof(ti));
        S = 1, T = 2, tot = 2;
        for (int i = 0; i < m; ++i)
        {
            scanf("%d", &e[i]);
            for (int j = 0; j < n; ++j)
            {
                to_mem[i][j] = ++tot;
                TO[tot] = par(i, j);
                zkw.makeline(tot, T, 1, 0);
            }
        }
        for (int i = 0; i < n; ++i)
        {
            int p, now = ++tot;
            to_pro[i] = now;
            zkw.makeline(S, now, 1, 0);
            scanf("%d", &p);
            for (int j = 0; j < p; ++j)
                scanf("%d%d", &s[j], &t[j]);
            for (int j = 0; j < m; ++j)
            {
                if (e[j] < s[0]) continue;
                int va;
                for (int k = 0; k < p; ++k)
                    if (k == p - 1 || s[k + 1] > e[j])
                    {
                        va = t[k];
                        break;
                    }
                ti[i][j] = va;
                for (int k = 0; k < n; ++k)
                    zkw.makeline(now, to_mem[j][k], 1, (k + 1) * va);
            }
        }
        printf("%.2f\n", ((double)zkw.query(S, T).b) / n);
        for (int i = 0; i < n; ++i)
            for (int j = zkw.be[to_pro[i]]; j; j = zkw.li[j].next)
                if (!zkw.li[j].v)
                {
                    int to = zkw.li[j].to;
                    as[TO[to].a][TO[to].b] = i;
                    bel[i] = TO[to].a;
                    break;
                }
        for (int i = 0; i < m; ++i)
        {
            int tot = 0;
            for (int j = n - 1; j >= 0; --j)
                if (as[i][j] != -1)
                {
                    be[as[i][j]] = tot;
                    tot += ti[as[i][j]][i];
                    en[as[i][j]] = tot;
                }
        }
        for (int i = 0; i < n; ++i)
            printf("%d %d %d\n", bel[i] + 1, be[i], en[i]);
        printf("\n");
    }
}

【World Finals】2007 I

【试题编号】
2007 I
【名称】
Water Tanks
【题目大意】
给n个水箱 中间用管道连接 第一个水箱是开口的 往第一个水箱灌水 问能灌多少水
【算法讨论】
考虑把第一个水箱灌满的时候的水压可以让第二个水为到哪 并计算出3~n个水箱当前的水压 然后去算第3个水箱。。。
【时空复杂度】
O(N)
O(N)
【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
#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;
typedef long double ld;
const double k = 0.097;
int n;
double ta[11], pi[11], h0, dh, v, v0, p, sum;
double get(double b, double c)
{
    return b / 2 - sqrt(b * b / 4 - c);
}
int main()
{
    int test = 0;
    while (scanf("%d", &n), n)
    {
        v = 0;
        for (int i = 0; i < n; ++i)
        {
            scanf("%lf", &ta[i]);
            if (i)
                v += ta[i];
        }
        for (int i = 1; i < n; ++i)
            scanf("%lf", &pi[i]);
        v -= pi[1];
        p = 1;
        sum = pi[1];
        for (int i = 1; i < n; ++i)
        {
            dh = pi[i + 1] - pi[i];
            if (i < n - 1)
                h0 = pi[i + 1] + (p * v / (v - dh) - 1) / k;
            if (h0 > ta[0] || i == n - 1)
            {
                dh = ta[0] - pi[i];
                sum += get(dh + v + 1 / k, dh * v + (1 - p) * v / k);
                break;
            }
            sum += dh;
            p *= v / (v - dh);
            v -= dh;
            h0 = pi[i + 1] + (p * v / ( v - pi[i + 1]) - 1) / k;
            if (h0 > ta[0])
            {
                sum += v - v * p / (1 + (ta[0] - pi[i + 1]) * k);
                break;
            }
            p *= v / (v - pi[i + 1]);
            v -= ta[i];
            v0 = ta[i] - pi[i + 1];
            dh = ta[0] - pi[i + 1];
            sum += pi[i + 1] + get(dh + v0 + 1 / k, dh * v0 + (1 - p) * v0 / k);
        }
        printf("Case %d: %.3f\n\n", ++test, sum + ta[0]);
    }
}

【World Finals】2011 A

【试题编号】
2011 A
【名称】
To Add or to Multiply
【题目大意】
一个数x 你可以对他进行+a操作 或*m操作 给定的数范围在p~q 最后达到的范围要是r~s 问是否可行 如果可行 输出字典序最小的方案
【算法讨论】
可以发现 M操作的次数很小 不妨枚举M的次数i 然后p,q变为p*M^i,q*M^i 然后再某个位置的一个A 可以看成+a*m^j 贪心的从次数高的开始加 能加就加 一定是当前i的最优解 然后跟一个全局的答案比较 更新
【时空复杂度】
O(logn*logn)
O(logn)
【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
102
103
104
105
106
107
108
109
110
111
112
113
#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;
typedef long double ld;
ll c[35], a, m, p, q, r, s, t[35], ans, as[35];
bool check()
{
    for (ll cc = c[34], aa = as[34]; cc >= 0 && aa >= 0; --cc, --aa)
    {
        if (c[cc] < as[aa]) return false;
        if (c[cc] > as[aa]) return true;
    }
    return false;
}
int main()
{
    ll test = 0;
    while (scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &a, &m, &p, &q, &r, &s) && (a | m | p | q | r | s))
    {
        ans = 0x7fffffff;
        printf("Case %I64d: ", ++test);
        if (p >= r && q <= s)
        {
            printf("empty\n");
            continue;
        }
        int k = -1;
        if (m != 1)
        for (ll i = 1, lf = p * m, rt = q * m; rt <= s; ++i, lf *= m, rt *= m)
            if (lf >= r && rt <= s)
            {
                k = i;
                break;
            }
        if (q - p > s - r)
        {
            printf("impossible\n");
            continue;
        }
        if (m == 1)
        {
            if (p + ((r - p + a - 1) / a) * a >= r && q + ((r - p + a - 1) / a) * a <= s)
            printf("%I64dA\n", ((r - p + a - 1) / a));
            else printf("impossible\n");
            continue;
        }
        t[0] = 1;
        for (ll i = 0, k = 1; q * k <= s && (q - p) * k <= (s - r); ++i, k *= m)
        {
            if (i) t[i] = t[i - 1] * m;
            ll lf = r - p * t[i], rt = s - q * t[i], z = -1, tans = 0;
            memset(c, 0, sizeof(c));
            if (lf > 0)
            for (ll j = i; j >= 0; --j)
            {
                z = j;
                c[j] = rt / t[j] / a;
                if (lf - c[j] * t[j] * a <= 0)
                    c[j] = (lf + t[j] * a - 1) / t[j] / a;
                lf -= c[j] * t[j] * a;
                rt -= c[j] * t[j] * a;
                tans += c[j];
                if (lf <= 0) break;
            }/*
            for (ll j = 0; j < z; ++j)
                if (lf + t[z] - t[j] <= 0)
                {
                    c[z] -= 1;
                    c[j] += 1;
                    break;
                }*/

            if (lf > 0) tans = 0x7fffffff;
            c[34] = i;
            tans += i;
            if (tans < ans || (tans == ans && check()))
            {
                ans = tans;
                for (ll j = 0; j < 35; ++j)
                    as[j] = c[j];
            }
        }
        if (ans >= 0x3f3f3f3f) printf("impossible");
        else
        for (ll i = as[34]; i >= 0;)
        {
            if (as[i]) printf("%I64dA ", as[i]);
            if (i)
            {
                --i;
                ll t = 1;
                while (i && !as[i])
                    --i, ++t;
                printf("%I64dM ", t);
            }
            else break;
        }
        printf("\n");
    }
}

【World Finals】2010 J

【试题编号】
2010 J
【名称】
Sharing Chocolate
【题目大意】
给n*m的方格 每次可以沿平行x或y切一刀 问最后能不能分成指定的一些面积
【算法讨论】
f[i][j] 表示长为i的方格 j值状压变量 表示这里面有哪些面积 对应的宽可以求出来
每次枚举一个切的方法 然后枚举j的切分 进行更新 用记忆话比较好做
【时空复杂度】
O(n^2 * 2^k * 2^k)
O(n*2^k)
【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
#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;
typedef long double ld;
int n, x, y, a[20], sum[40000];
bool f[105][40000], b[105][40000];
int lowbit(int a)
{
    return a & (-a);
}
bool dfs(int x, int y, int t)
{
    if (b[x][t]) return f[x][t];
    if (!(t - lowbit(t)))
        return b[x][t] = f[x][t] = true;
    bool br = false;
    for (int i = 1; i < x; ++i)
    {
        if (br) break;
        for (int j = (t - 1) & t; j; j = (j - 1) & t)
            if (i * y == sum[j] && (x - i) * y == sum[t ^ j] && dfs(i, y, j) && dfs(x - i, y, t ^ j))
            {
                br = true;
                break;
            }
    }
    for (int i = 1; i < y; ++i)
    {
        if (br) break;
        for (int j = (t - 1) & t; j; j = (j - 1) & t)
            if (x * i == sum[j] && x * (y - i) == sum[t ^ j] && dfs(x, i, j) && dfs(x, y - i, t ^ j))
            {
                br = true;
                break;
            }
    }
    b[x][t] = true;
    return f[x][t] = br;
}
int main()
{
    int test = 0;
    while (scanf("%d", &n) && n)
    {
        scanf("%d%d", &x, &y);
        memset(f, 0, sizeof(f));
        memset(b, 0, sizeof(b));
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        for (int i = 0; i < (1 << n); ++i)
            for (int j = 0; j < n; ++j)
                if (i & (1 << j))
                    sum[i] += a[j];
        printf((dfs(x, y, (1 << n) - 1) ? "Case %d: Yes\n" : "Case %d: No\n"), ++test);
    }
}

【World Finals】2011 H

【试题编号】
2011 H
【名称】
Mining Your Own Business
【题目大意】
给一个无向图 问最少设置几个点为梯 使得去掉任意一个点 其他点都能到梯
【算法讨论】
求割点 然后求有几个点双联通分量中 只有一个割点 就要放一个梯 如果没有割点要特判 要两个梯
【时空复杂度】
O(n)
O(n)
【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
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
#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;

//===========================LinkTable=================

const int LTmaxm = 200005;
const int LTmaxn = 200005;

struct line
{
  int to, next;
};

struct Link_Table
{
  line li[LTmaxm];
  int be_[LTmaxn], l;

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

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

  void makeline_double(int fr, int to)
  {
    makeline(fr, to);
    makeline(to, fr);
  }

  void clear()
  {
    l = 0;
    memset(be_, 0, sizeof(be_));
  }
}L;

//===========================LinkTable=================
struct Tarjan
{
    static const int Tmaxn = 200005;
    static const int Tmaxm = 200005;
    int low[Tmaxn], dfn[Tmaxn], tot, t[Tmaxm];

    int tarjan(int now, int fa, Link_Table &L, int *b, int tp)
    {
        dfn[now] = ++tot;
        low[now] = dfn[now];
        int sum = 0, lfa = -1, mi = 0x7fffffff;
        for (int i = L.be(now); i; i = L.next(i))
        {
            int to = L.to(i);
            if (to == fa)
            {
                lfa = i;
                continue;
            }
            if (!dfn[to])
            {
                int t = tarjan(to, now, L, b, tp);
                low[now] = min(low[now], low[to]);
                if (tp)
                    if (low[to] > dfn[now]) b[i] = b[t] = 1;
                ++sum;
                if (low[to] >= dfn[now] && fa != -1) b[now] = 1;
                mi = min(mi, low[to]);
            }
            else low[now] = min(low[now], dfn[to]);
        }
        if (!tp && sum && fa == -1)
            b[now] = sum > 1 ? 1 : 0;
        return lfa;
    }

    void clear()
    {
        memset(low, 0, sizeof(low));
        memset(dfn, 0, sizeof(dfn));
        tot = 0;
    }

    void get_cut_node(Link_Table &L, int n, int *b)
    {
        clear();
        for (int i = 0; i < n; ++i)
            b[i] = 0;
        for (int i = 0; i < n; ++i)
            if (!dfn[i])
                tarjan(i, -1, L, b, 0);
    }

    void get_cut_edge(Link_Table &L, int n, int *b)
    {
        clear();
        for (int i = 0; i < n; ++i)
            b[i] = 0;
        for (int i = 0; i < n; ++i)
            if (!dfn[i])
                tarjan(i, -1, L, b, 1);
        for (int i = 0; i < n; ++i)
        {
            for (int j = L.be(i); j; j = L.next(j))
                ++t[L.to(j)];
            for (int j = L.be(i); j; j = L.next(j))
                if (t[L.to(j)] > 1)
                    b[j] = 0;
            for (int j = L.be(i); j; j = L.next(j))
                --t[L.to(j)];
        }
    }
}T;

int n, b[100005], bb[100005], aans, t[100005], test;
ll ans2;
queue<int> q, q2;

void bfs(int now)
{
    bb[now] = 1;
    q.push(now);
    int ans = 0, tot = 0;
    while (!q.empty())
    {
        ++tot;
        int now = q.front();
        q.pop();
        for (int i = L.be(now); i; i = L.next(i))
        {
            int to = L.to(i);
            if (b[to] && !t[to])
            {
                t[to] = 1;
                q2.push(to);
                ++ans;
            }
            if (b[to] || bb[to]) continue;
            bb[to] = 1;
            q.push(to);
        }
    }
    while (!q2.empty())
    {
        int now = q2.front();
        q2.pop();
        t[now] = 0;
    }
    if (ans == 1)
        ++aans, ans2 *= tot;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    while (scanf("%d", &n), n)
    {
        L.clear();
        int mx = 0;
        for (int i = 0; i < n; ++i)
        {
            int fr, to;
            scanf("%d%d", &fr, &to);
            mx = max(max(fr, mx), to);
            L.makeline_double(fr, to);
        }
        T.get_cut_node(L, n + 10, b);
        memset(bb, 0, sizeof(bb));
        aans = 0;
        ans2 = 1;
        for (int i = 1; i <= mx; ++i)
            if (!bb[i] && !b[i])
                bfs(i);
        if (!aans) printf("Case %d: %d %I64d\n", ++test, 2, ((ll)mx) * (mx - 1) / 2);
        else printf("Case %d: %d %I64d\n", ++test, aans, ans2);
    }
    fclose(stdin);fclose(stdout);
}