【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】2013F

【试题编号】
2013F
【名称】
Low Power
【题目大意】
有n台机器 每台2个芯片 每个芯片k个电池 每个电池有个独立的电量 对于一个芯片 能量是最小的电池的电量 一个机器的性能是两个芯片的能量差 求机器性能最大最小
【算法讨论】
因为对于每个芯片 只有最小电池有用 于是对于每个芯片只要考虑最小的电池 再考虑电池的选用
可以证明 对于一台机器的两个芯片的最小电池一定是连续的两个
先二分答案 显然 对于一个固定的delta 取得越前面越好 只要能取满 那么这个delta就是合法的
【时空复杂度】
O(nlogn)
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
#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;
int a[1000005], n, k, m;
bool check(int mid)
{
    for (int i = 0, tot = 0, as = 0; i < m; ++i)
    {
        if (a[i + 1] - a[i] <= mid)
        {
            tot += (k - 1) * 2;
            if (++as == n) break;
            ++i;
        }
        else if (--tot < 0) return false;
    }
    return true;
}
int main()
{
    scanf("%d%d", &n, &k);
    m = 2 * n * k;
    for (int i = 0; i < m; ++i)
        scanf("%d", &a[i]);
    sort(a, a + m);
    int l = -1, r = 10000 * 10000 * 10;
    while (l + 1 < r)
    {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    printf("%d", r);
}