JOI 2013/2014 本選

2015.10.29 20:06 Thu| 20 visits oi_2016| 2016_刷题日常| Text

JOI 紋章 (JOIEmblem)

有 M 行 N 列的 JOI 旗和 2 行 2 列的 JOI 纹章。最多修改 JOI 旗中的一个字符,问修改后的 JOI 旗中最多包含多少个 JOI 纹章。

看到数据范围感觉好像很卡时的样子啊。

枚举每一个位置,判断它对答案的贡献与将它修改成其他字符对答案的贡献,最终取最大值即为答案。时间复杂度是开(fa)心(xu)的 O(K*MN)(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
#include <bits/stdc++.h>
using namespace std;

#define N 4005

int n, m, ans;
char str[N][N], aim[3][3], cnt[N][N][4];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        scanf("%s", str[i] + 1);
    for (int i = 1; i <= 2; ++i)
        scanf("%s", aim[i] + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            str[i][j] = str[i][j] == 'J' ? 1 : str[i][j] == 'O' ? 2 : 3;
    for (int i = 1; i <= 2; ++i)
        for (int j = 1; j <= 2; ++j)
            aim[i][j] = aim[i][j] == 'J' ? 1 : aim[i][j] == 'O' ? 2 : 3;
    for (int i = 1; i < n; ++i)
        for (int j = 1; j < m; ++j)
        {
            int temp = 0, x = i + 1, y = j + 1;
            temp = (str[i][j] == aim[1][1]) + (str[x][j] == aim[2][1])
                + (str[i][y] == aim[1][2]) + (str[x][y] == aim[2][2]);
            if (temp == 4)
                ++ans, --cnt[i][j][0], --cnt[x][j][0],
                --cnt[i][y][0], --cnt[x][y][0];
            else if (temp == 3)
            {
                if (str[i][j] != aim[1][1]) ++cnt[i][j][(int)aim[1][1]];
                else if (str[x][j] != aim[2][1]) ++cnt[x][j][(int)aim[2][1]];
                else if (str[i][y] != aim[1][2]) ++cnt[i][y][(int)aim[1][2]];
                else ++cnt[x][y][(int)aim[2][2]];
            }
        }
    int t = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            t = max(t, cnt[i][j][0] + max(cnt[i][j][1],
                                        max(cnt[i][j][2], cnt[i][j][3])));
    cout << ans + t << endl;
    return 0;
}

IOI 饅頭 (IOIManju)

有 M 个馒头和 N 个箱子。要把馒头装在箱子里卖。每一个馒头都可以卖一定的钱数;每一个箱子都需要花费一定钱数购买,且能够装一定数量的馒头。问最大收益是多少钱。

显然用背包解决就好了。首先 DP 处理出买至少能够装 X 个馒头的箱子所需要花的钱数。之后将馒头按照价格从大到小排序,枚举数量更新答案就好了。

多么水的一道裸题……

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

#define N 10005

int m, n, p[N], c[N], e[N], f[N * 2];

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= m; ++i)
        scanf("%d", &p[i]);
    sort(p + 1, p + m + 1);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &c[i], &e[i]);
    for (int i = m - 1; i; --i)
        p[i] += p[i + 1];
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 20000; j >= c[i]; --j)
            f[j] = min(f[j], f[j - c[i]] + e[i]);
    for (int i = 19999; i; --i)
        f[i] = min(f[i], f[i + 1]);
    int ans = 0;
    for (int i = 1; i <= m; ++i)
        ans = max(ans, p[m - i + 1] - f[i]);
    cout << ans << endl;
    return 0;
}

バームクーヘン (Baumkuchen)

题目来源于德语,年轮蛋糕。

一个年轮蛋糕,预先已经分成了 N 部分。只能在某两部分的交界处下刀,要用三刀将蛋糕切成三大块。问其中最小的一块最大是多少。

由于 JOI 题型很有模式化,而第四题显然是最短路,所以这道题就一定是二分答案了(口胡)。

对于答案 X,首先需要枚举下第一刀的位置,之后可以依次暴力(或二分)找出距离前一刀不小于 X 的位置去切后两刀。最后判断第一刀和第三刀之间的距离是否小于 X 就可以了。发现在枚举切第一刀的位置的同时,第二刀和第三道的位置是单调不后退的。因此可以在之后继续枚举下去。这一过程中,时间复杂度仅为 O(N)。因此总时间复杂度 O(N*log∑Ai),能够接受。

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

#define N 200005

int n;
long long a[N];

inline long long calc(int l, int r) { return a[r] - a[l]; }

bool check(long long mid)
{
    int t1 = 0, t2 = 0, t3 = 0;
    for (t1 = 0; t1 < n; ++t1)
    {
        while (calc(t1, t2) < mid) ++t2;
        t3 = max(t2, t3);
        while (t3 < t1 + n && calc(t2, t3) < mid) ++t3;
        if (calc(t3, t1 + n) >= mid) return true;
    }
    return false;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]), a[n + i] = a[i];
    for (int i = 2; i <= n * 2; ++i)
        a[i] += a[i - 1];
    long long l = 1, r = a[n], mid, ans = 0;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

フクロモモンガ (SugarGlider)

这种神奇的小动物叫做蜜袋鼯,别称澳洲飞袋鼠。蜜袋鼯产于澳洲新几内亚和南澳洲,大多数时间在树上活动,舔食树蜜。蜜袋鼯的身体两侧拥有滑行膜, 从手关节延伸到脚踝,有利它们在树林间滑行。

蜜袋鼯为何在树间飞来飞去。

有一只名叫 JOI 的蜜袋鼯,想要从树 1 移动到树 N 的顶端。当他在一棵树上的时候,可以花费一秒钟的时间向上走一米或向下走一米。他还可以在某些树之间飞跃。在两棵树之间进行转移需要花费一定时间。设这个时间为 T,则蜜袋鼯在空中会下降 T 米。要求不能让我们萌萌哒蜜袋鼯君在飞行时摔在地上,也不能让他跳到另一棵树的时候位置太高,从而越过这棵树(玩脱了)。现在给出树 i 的高度 Hi 和在某些树之间飞跃需要的时间,蜜袋鼯最初的位置在树 1 上距离地面 X 米处。问它最少需要多久能够移动到树 N 顶端。(若不能移动到输出 -1)。

从小课题 2 出发:

限制是 X=0。可以发现,从树根开始往上爬,如果爬得太高,会导致后来转移到另一棵树上时需要先向下爬。这毫无疑问会浪费时间。因此让蜜袋鼯每一次向上爬的高度恰好能够使它转移到另一棵树的树根处,一定能够得到最优答案。答案就是从树 1 到树 N 的最短路径长度 * 2 + HN

对于全部的测试数据,取消了 X=0 的限制。于是最优解存在以下可能:开始时不需要向上爬,而是一直向下爬或向其它树滑行直到一次滑行后高度降到零。从这以后,情景便和小课题 2 中描述的相同了。

这里可以假设树的高度一直延伸到负无穷,那么蜜袋鼯在到达树 N 之前就完全没有向上爬的必要了。设 f[X] 表示蜜袋鼯到达 X 点时的最高位置,那么 X - f[N] + HN - f[N] 就是答案了。对于 X 数组,我们仍然可以使用最短路来求。

实现的时候需要判断每两棵树之间是否真的能够到达,并且更新答案时还要注意 f[i] 的永远不能大于 Hi

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

#define N 100005
#define M 600005
#define _inf -4557430888798830400ll

int n, m, h[N];
long long X, d[N];

priority_queue<pair<long long, int>> q;

int head[N];

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

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

void spfa(int s)
{
    memset(d, 0xc0, sizeof d);
    d[s] = X;
    q.push(make_pair(X, s));
    while (!q.empty())
    {
        int x = q.top().second; long long y = q.top().first; q.pop();
        if (y != d[x]) continue;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val <= h[x])
            if (d[edge[i].to] < min(y - edge[i].val, 1ll * h[edge[i].to]))
                d[edge[i].to] = min(y - edge[i].val, 1ll * h[edge[i].to]),
                q.push(make_pair(d[edge[i].to], edge[i].to));
    }
}

int main()
{
    cin >> n >> m >> X;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &h[i]);
    for (int x, y, z, i = 1; i <= m; ++i)
        scanf("%d%d%d", &x, &y, &z),
        add(x, y, z), add(y, x, z);
    spfa(1);
    if (d[n] == _inf) cout << -1 << endl;
    else cout << (X - d[n]) * 2 - X + h[n] << endl;
    return 0;
}

切り取り線 (Cutting)

有一张长方形纸。现在平行于边在纸上切几刀,问最终会得到多少张小纸片。

这可真是神之线段树,全场平均分 0.5。

首先我们会发现在一张纸上切来切去的实在是太麻烦了。但是,如果将这张纸看作是用四刀从一个平面上切下来的,就可以将问题转化到平面上了。最终要求的答案就是这个平面被分成的区域数 -1(外界)。

另外发现纸片被切出的形状真是可以稀奇古怪,所以还是先要把它们分割成一个一个小长方形,然后用并查集来维护每一个长方形所在的区域。分割的方法如下图所示:

(我无法抑制自己去搬原题解的冲动)。

在这样分割的基础上,很容易想到我们可以按照纵坐标从下到上去依次处理每一个纵坐标区间!在我们从下到上依次枚举需要关注的纵坐标时,可以观察到这样三种事件:

  • 一条竖线的下端出现了
  • 一条竖线的上端出现了
  • 一条横线完整地出现了

对于以上的每一种事件,观察并查集和答案的变化情况:

  1. 如果出现了一条竖线的下端,并查集中的点数并没有变化,而只是将区间分成了两部分而已。

  2. 如果出现了一条竖线的下端,则需要将原本被直线所隔开的两个区域在并查集中的结点合并到一起,并将答案数 -1。特别地,如果这两个区域本来就在同一个集合中,答案数就不会发生改变了。

  3. 如果出现了一条横线,在横线之间的区域就会被横线切分成两半,而并查集中就会产生许多新的结点。这条横线对答案的贡献是新增的区域数,即这条横线穿过的竖线条数 -1。特别地,如果竖线条数过少,这条横线对答案的贡献是 0(完全没有派上用场)。

    到此为止,我们可以想到用线段树去维护当前的竖线存在的位置和数量,需要支持单点加入、单点删除、区间元素个数查询。(当然,set 什么的也完全可以)。
    发现现在的算法复杂度仍然是 O(N^2*logN?),之所以这样慢的瓶颈就在于我们发现一条横线了之后需要在并查集中为新增加的区域建立结点。然而,很多结点再也没有用上。于是,在更新的时候,我们可以不为新产生的区域建立结点,而是在线段树中做标记,标明这里是还没有在并查集中建立结点的区域。当我们发现在某一个新产生的区域中发生了前两种事件时,再为区域建立结点也为时不晚。
    这样,在线段树中只需要再维护一个标记的区间添加和单点删除,就可以在 O(N*logN) 的时间、O(N) 的空间内解决这道问题了。
    细节:当某一个坐标处同时出现了三种变化时,先考虑哪一种变化呢?

    将这几条切线都看作略微出了点头,就可以很明显地知道了需要依次处理某条竖线的出现、某条横线的出现和某条竖线的消失。

原题解还提供了另外一种做法:

由平面上的欧拉定理,可以知道

线的交点的数量 + 切线的联通块数量 - 切线将平面划分成区域的数量 - 切线的总数 = -1。

这个结论在题解中的证明运用的是观察和归纳法。

其中第四项为已知,第一项可以很容易地用维护。那么想要知道第三项的取值,只需要知道切线间联通块的数量即可。关于这一项的求法,大概用到了排序,最终时间复杂度是 O(Nlog^2N)。然而具体实现方法我并没有看懂。

ここまで,近三年 JOI 本选目标达成!

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

#define N 100010
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int w, h, n, x1[N], y1[N], x2[N], y2[N];
int id[N * 4], fa[N * 4];
int sum[N * 8]; bool tag[N * 8];
vector<int> vx;
set<int> s;

struct data
{
    int y, type, l, r;
    data() {}
    data(int _y, int _type, int _l, int _r = 0)
    : y(_y), type(_type), l(_l), r(_r) {}
    inline bool operator <(data &d)
    {
        return make_pair(make_pair(y, type), make_pair(l, r))
                < make_pair(make_pair(d.y, d.type), make_pair(d.l, d.r));
    }
} opt[N * 2];

int find(int x)
{
    if (fa[x] == -1) return x;
    return fa[x] = find(fa[x]);
}

bool join(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx == fy) return false;
    fa[fx] = fy;
    return true;
}

void insert(int pos, int l, int r, int x, int y)
{
    sum[pos] += y;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) insert(lson, l, mid, x, y);
    else insert(rson, mid + 1, r, x, y);
}

int query(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y) return sum[pos];
    int mid = (l + r) >> 1, re = 0;;
    if (x <= mid) re += query(lson, l, mid, x, y);
    if (y > mid) re += query(rson, mid + 1, r, x, y);
    return re;
}

void lazy(int pos)
{
    tag[lson] = tag[rson] = 1; tag[pos] = 0;
}

void color(int pos, int l, int r, int x)
{
    if (l == r) { tag[pos] = 0; return; }
    int mid = (l + r) >> 1;
    if (tag[pos]) lazy(pos);
    if (x <= mid) color(lson, l, mid, x);
    else color(rson, mid + 1, r, x);
}

void clear(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        { tag[pos] = 1; return; }
    if (tag[pos]) return;
    int mid = (l + r) >> 1;
    if (x <= mid) clear(lson, l, mid, x, y);
    if (y > mid) clear(rson, mid + 1, r, x, y);
}

bool check(int pos, int l, int r, int x)
{
    if (tag[pos]) return true;
    if (l == r) return false;
    int mid = (l + r) >> 1;
    if (x <= mid) return check(lson, l, mid, x);
    return check(rson, mid + 1, r, x);
}

void give(int x)
{
    static int tot = 0;
    if (check(1, 0, n * 2, x))
        color(1, 0, n * 2, x), id[x] = ++tot;
}

int main()
{
    cin >> w >> h >> n;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
        if (x1[i] > x2[i]) swap(x1[i], x2[i]);
        if (y1[i] > y2[i]) swap(y1[i], y2[i]);
    }
    x1[n + 1] = 0, y1[n + 1] = 0, x2[n + 1] = w, y2[n + 1] = 0;
    x1[n + 2] = 0, y1[n + 2] = h, x2[n + 2] = w, y2[n + 2] = h;
    x1[n + 3] = 0, y1[n + 3] = 0, x2[n + 3] = 0, y2[n + 3] = h;
    x1[n + 4] = w, y1[n + 4] = 0, x2[n + 4] = w, y2[n + 4] = h;
    n += 4;

    vx.push_back(-1);
    for (int i = 1; i <= n; ++i)
        vx.push_back(x1[i]), vx.push_back(x2[i]);
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    for (int i = 1; i <= n; ++i)
        x1[i] = lower_bound(vx.begin(), vx.end(), x1[i]) - vx.begin(),
        x2[i] = lower_bound(vx.begin(), vx.end(), x2[i]) - vx.begin();

    memset(id, -1, sizeof id);
    memset(fa, -1, sizeof fa);
    s.insert(0); id[0] = 0;

    for (int i = n; i; --i)
        if (x1[i] == x2[i])
            opt[i] = data(y1[i], 0, x1[i]),
            opt[++n] = data(y2[i], 2, x1[i]);
        else
            opt[i] = data(y1[i], 1, x1[i], x2[i]);
    sort(opt + 1, opt + n + 1);

    long long ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (opt[i].type == 0)
        {
            int r = opt[i].l, l = *--s.lower_bound(r);
            give(l), give(r); id[r] = id[l];
            s.insert(r); insert(1, 0, n * 2, r, 1);
        }
        else if (opt[i].type == 1)
        {
            int l = opt[i].l, r = opt[i].r,
                temp = query(1, 0, n * 2, l, r);
            if (temp < 2) continue; ans += temp - 1;
            clear(1, 0, n * 2, l, *--s.upper_bound(r) - 1);
        }
        else if (opt[i].type == 2)
        {
            int r = opt[i].l, l = *--s.lower_bound(r);
            give(l), give(r);
            if (join(id[l], id[r])) --ans;
            s.erase(r); insert(1, 0, n * 2, r, -1);
        }
    }
    cout << ans << endl;
    return 0;
}