长春寒假集训模拟赛 Ⅰ

2016.01.19 18:46 Tue| 110 visits oi_2016| 2016_竞赛日常| Text

hole

问题描述

GFS打算去郊外建所别墅,享受生活,于是他耗费巨资买下了一块风水宝地,但令他震惊的是,一群DSJ对GFS的富贵生活深恶痛绝,决定打洞以搞破坏。

现在我们简化一下这个问题,在这片土地上会按顺序发生一系列事件。

①一只DSJ在(x,y)这个点打了一个洞。

②有着高雅品味GFS想建一个等腰直角三角形的别墅,即由(x,y),(x+d,y),(x,y+d)三点围成的三角形,但为了地基的牢固,他想知道当前这块三角形土地内的洞的个数。

GFS现在对DSJ已经忍无可忍了,请你帮他回答这些询问。

初始土地上没有洞。GFS毕竟是GFS,你可以认为土地无限大。

输入格式

第一行一个整数n,表示事件数。接下来n行,每行3个非负整数x,y,d。

若d=0表示DSJ打洞的事件。否则表示GFS建房的询问。

输出格式

对每个询问输出一个整数,表示当时询问的三角形内的洞的个数。

样例输入1

8
1 3 0
1 5 0
3 6 0
4 4 0
2 6 0
1 5 3
1 5 4
1 1 1

样例输出1

3
3
0

样例输入2

4
1 5 0
3 7 0
2 5 6
2 3 4

样例输出2

1
0

数据范围

30%的数据n≤3333。

另30%的数据 GFS只会在DSJ打完洞后才开始询问,xi,yi≤333333。

100%的数据 1≤n≤88888,xi,yi≤3333333。

flood

问题描述

GFS好不容易在千疮百孔的土地上选了一块比较完整的土地,并建好了自己的新家,其中的每堵墙都平行于坐标轴,并且墙只会在房屋的立柱处相交。但GFS毕竟是GFS,他在这片土地上可能建造了不止一座别墅,而且别墅中会出现区域嵌套(包围)的情况,比如环形走廊包围的客厅。也就是说所有的墙不一定连通。

但好景不长,某次FFF进行了大规模的祈雨活动,一时间暴雨如注,位于低洼处的土地出现了地下水倒灌现象,地下水从DSJ打的无数个洞中涌出,包围了GFS的别墅,每一时刻,如果一堵墙两侧分别为空气和水,那么墙会被水冲垮,下一时刻就会有更多的区域会被水淹没,直到GFS的所有别墅都被淹没。

现在GFS想知道哪些墙还能留下来。

输入格式

第一行一个整数n,表示有n根立柱。

接下来n行给出n根立柱的坐标。

接下来一行一个整数m,表示有m堵墙。

接下来m行给出m堵墙两端立柱的编号。

输出格式

第一行包含一个整数ans,表示洪水过后留下的墙的数目。

接下来ans行,每行一个整数表示留下来的墙的编号,按编号从小到大的顺序输出。

样例

为便于样例的阅读,样例单独位于下一页。

数据范围

40%的数据 n≤600 且 坐标范围[0,600]。

55%的数据 n≤600。

100%的数据 2≤n≤100 000,m≤n*2,坐标范围[0,1 000 000]。

样例输入

15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6

样例输出

4
6
15
16
17

aplusb

问题描述

SillyHook要给小朋友出题了,他想,对于初学者,第一题肯定是a+b啊,但当他出完数据后神奇地发现.in不见了,只留下了一些.out,他想还原.in,但情况实在太多了,于是他想要使得a,b尽可能大。

输入格式

输入文件的第一行一个整数T表示数据组数。

接下来T行每行一个整数n,表示.out中的数值,即a+b=n。

输出格式

共T行,每行一个整数表示最大的[a,b]的值。

样例输入

3
2
3
4

样例输出

1
2
3

数据规模与约定

30%的数据满足T≤10,n≤10^3。

100%的数据满足T≤10^4,n≤10^9。

题解

hole

算法描述

30%

统直接暴力枚举已经添加的点,判断是否在等腰直角三角形内。

时间复杂度 O(m^2)

另30%

由于询问前已经添加完了,不存在先后顺序的问题,可直接按(x+y)排序后扫描线扫过去。对于三角形内的点数,可以发现三角形可用 夹在两条扫描线内的所有点 减去 两侧直角边与扫描线构成的平行四边形区域。

如图,两条扫描线中间夹着的部分减去绿色部分后就能得到蓝色部分内的点的数量了。

而这可以用前缀和相减的方法轻松地用树状数组统计。

时间复杂度 O(nlogn) (特殊数据)

100%

从另30%的方法中我们发现,如果可以去掉添加和询问的先后关系,我们可以用nlogn 的时间复杂度完成统计。而冬令营上gyz讲的分治则为我们提供了去掉先后关系的工具。

递归左边,递归右边,统计左边对右边的贡献,而这一步统计就是前面的情况!

时间复杂度 O(nlog^2 n)

考察内容

分治,树状数组,简单容斥。(树套树)

难度:中等

题目来源

30%的情况http://www.codechef.com/FEB13/problems/TRIQUERY

100%的由原题加强而来。

  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
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define M 7000005

int n, m1, m2, m, x[N], y[N], p[N], bit[M], ans[N];

struct traid
{
    int x, y, z, id, t;
    traid() {}
    traid(int _x, int _y, int _z, int _id, int _t)
    : x(_x), y(_y), z(_z), id(_id), t(_t) {}
    bool operator <(const traid &t) const { return y < t.y; }
} d[N * 2], temp[N * 2];

void insert(int x, int y)
{
    for (int i = x; i <= m; i += i & -i)
        bit[i] += y;
}

int query(int x)
{
    int re = 0;
    for (int i = min(x, m); i; i -= i & -i)
        re += bit[i];
    return re;
}

void cdq(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    for (int i = l, tl = l, tr = mid + 1; i <= r; ++i)
        if (d[i].x <= mid) temp[tl++] = d[i];
        else temp[tr++] = d[i];
    for (int i = l; i <= r; ++i)
        d[i] = temp[i];
    cdq(l, mid);
    for (int i = l, j = mid + 1; j <= r; ++j)
    {
        while (i <= mid && d[i].y <= d[j].y)
        {
            if (d[i].t == 0) insert(d[i].z, 1);
            ++i;
        }
        if (d[j].t) ans[d[j].id] += d[j].t * query(d[j].z);
        if (j == r) while (i > l)
        {
            --i;
            if (d[i].t == 0) insert(d[i].z, -1);
        }
    }
    cdq(mid + 1, r);
    sort(d + l, d + r + 1);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    freopen("hole.in", "r", stdin);
    freopen("hole.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        x[i] = read() + 1, y[i] = read() + 1, p[i] = read(),
        m1 = max(m1, x[i]), m2 = max(m2, y[i]);
    m = m1 + m2 - 1;
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (p[i] == 0)
            ++cnt, d[cnt] = traid(cnt, x[i], x[i] + y[i] - 1, i, 0);
        else
        {
            ++cnt, d[cnt] = traid(cnt, x[i] - 1, x[i] + y[i] + p[i] - 1, i, -1);
            ++cnt, d[cnt] = traid(cnt, x[i] + p[i], x[i] + y[i] + p[i] - 1, i, 1);
        }
    }
    sort(d + 1, d + cnt + 1);
    cdq(1, cnt);
    cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (p[i] == 0)
            ++cnt, d[cnt] = traid(cnt, x[i], y[i], i, 0);
        else
        {
            ++cnt, d[cnt] = traid(cnt, x[i] - 1, y[i] - 1, i, 1);
            ++cnt, d[cnt] = traid(cnt, x[i] + p[i], y[i] - 1, i, -1);
        }
    }
    sort(d + 1, d + cnt + 1);
    cdq(1, cnt);
    for (int i = 1; i <= n; ++i)
        if (p[i]) printf("%d\n", ans[i]);
    return 0;
}

flood

算法描述

40%

直接FloodFill(要用01bfs,双端队列)。时间复杂度 O(〖|坐标范围|〗^2)

55%

将图离散后进行FloodFill。时间复杂度 O(n^2)

100%

求平面图的对偶图。把域看作点,bfs得到每个域被淹没的时间,若线段两侧的域时间不同则墙会倒。但不连通时会出现包含关系,但对于这题来说,其实是没关系的,因为包含关系的墙是一定会倒的,直接看成和无限域连接是没事的。

如果询问没有这个性质,而边不全与坐标轴平行,怎么求不连通平面图的域呢?我们可以用下面的做法:

算法思路是添若干条不影响域的边,使得图连通。

先找到平面图中每个连通块,找到其中y坐标最小的点,从这个点向下作一条射线,这条射线不会影响这个连通块内的域。然后找到这条射线上的第一个交点,将交点所在边分裂为两条,并添加射线起点和交点之间的边,这样对交点所在的连通块内的域也不会有影响。如果不存在交点则假设无穷远处有一根无限沿伸的直线,所有射线都与这条线有交点,这样不连通的域就都连通了。

关于找第一个交点,暴力枚举每条边复杂度m^2。用扫描线求m log m。

然后可以用每次找顺时针方向第一条边的方法找出每个域。

为了方便处理,可对读入的点进行了转角度的处理。

时间复杂度 O(m)本题 O(m log m)一般题目

考察内容

平面图求对偶图,不连通情况(特殊情况、一般情况)

难度:中等

题目来源

http://www.lydsy.com/JudgeOnline/problem.php?id=1804 ioi2007

添加了编号从小到大输出的限制避免使用special judge。

  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
#include <bits/stdc++.h>
using namespace std;

#define N 400005
#define inf 0x3f3f3f3f

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int n, m, tot, pre[N], bel[N], head[N], cnt, d[N], ans;
vector<int> v[N];
queue<int> q;

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

inline long long cross(const point &a, const point &b, const point &c)
{ return 1ll * (b.x - a.x) * (c.y - a.y) - 1ll * (b.y - a.y) * (c.x - a.x); }

struct line
{
    int x, y; double ang;
    line() {}
    line(int _x, int _y) : x(_x), y(_y)
    { ang = atan2(p[y].y - p[x].y, p[y].x - p[x].x); }
} l[N];

inline bool cmp(int x, int y)
{
    return l[x].ang < l[y].ang;
}

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N];

inline void add(int x, int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

int main()
{
    freopen("flood.in", "r", stdin);
    freopen("flood.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        p[i].x = read(), p[i].y = read();
    cin >> m;
    for (int x, y, i = 0; i < m << 1; i += 2)
    {
        x = read(), y = read();
        l[i] = line(x, y), v[x].push_back(i);
        l[i ^ 1] = line(y, x), v[y].push_back(i ^ 1);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!v[i].size()) continue;
        sort(v[i].begin(), v[i].end(), cmp);
        pre[v[i][0]] = v[i][v[i].size() - 1];
        for (int j = 1; j < int(v[i].size()); ++j)
            pre[v[i][j]] = v[i][j - 1];
    }
    memset(d, 0x3f, sizeof d);
    for (int i = 0; i < m << 1; ++i)
    {
        if (bel[i]) continue;
        bel[i] = ++tot;
        long long area = 0;
        for (int j = pre[i ^ 1]; j != i; j = pre[j ^ 1])
        {
            if (pre[j ^ 1] != i)
                area += cross(p[l[i].x], p[l[j].x], p[l[j].y]);
            bel[j] = tot;
        }
        if (area < 0) d[tot] = 0, q.push(tot);
    }
    for (int i = 0; i < m << 1; ++i)
        add(bel[i], bel[i ^ 1]);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (d[edge[i].to] == inf)
                d[edge[i].to] = d[x] + 1, q.push(edge[i].to);
    }
    for (int i = 0; i < m << 1; i += 2)
        if (d[bel[i]] == d[bel[i ^ 1]])
            ++ans;
    cout << ans << endl;
    for (int i = 0; i < m << 1; i += 2)
        if (d[bel[i]] == d[bel[i ^ 1]])
            printf("%d\n", i / 2 + 1);
    return 0;
}

aplusb

算法描述

100%

若n为奇数,则a和b相差1最优

若n为偶数,令m=n/2,若m-1和m+1均为奇数,则a=m-1,b=m+1

否则a=m-2,b=m+2

时间复杂度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
#include <bits/stdc++.h>
using namespace std;

int test, n;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int gcd(int a, int b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

int main()
{
    freopen("aplusb.in", "r", stdin);
    freopen("aplusb.out", "w", stdout);
    cin >> test;
    while (test--)
    {
        n = read();
        if (n == 1) puts("0");
        for (int i = n / 2; i; --i)
            if (gcd(i, n - i) == 1)
                { printf("%lld\n", 1ll * i * (n - i)); break; }
    }
    return 0;
}