JOI 2014/2015 本選

2015.10.28 16:13 Wed| 17 visits oi_2016| 2016_刷题日常| Text

官方网站链接

日本的本选题做起来感觉自己萌萌哒并不是特别困难,比较注重思想性而不是代码能力。没有鬼畜题、大数据结构和超过NOIP范围的知识点,应该也与比较紧的时限有关(三个半小时五道题)。而且考试还是有开启 c++11 开关的(好评)。面白いですね。

另外,果然日本人的题解写得很有趣啊!

鉄道旅行 (RailroadTrip)

紙の切符?IC カード?这是个问题。

这真是一道简单得不行的线段树啊!出题人都懒得出一道树上问题或者图上问题么?

其实官方原题解是用前缀和什么的过的。难道日本参加国赛的学生还不会线段树?

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

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

int n, m, p[N], tag[N << 2];
long long ans;

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

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

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

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        scanf("%d", &p[i]);
    for (int i = 1; i < m; ++i)
        insert(1, 1, n, min(p[i], p[i + 1]), max(p[i], p[i + 1]) - 1);
    for (int a, b, c, i = 1; i < n; ++i)
    {
        scanf("%d%d%d", &a, &b, &c);
        int x = query(1, 1, n, i);
        ans += min(c + 1ll * b * x, 1ll * a * x);
    }
    cout << ans << endl;
    return 0;
}

ケーキの切り分け2 (Cake2)

JOI くん和 IOI ちゃん要分蛋糕啦。JOI くん取第一块,之后两人从缺口开始轮流取一块蛋糕。IOI ちゃん只知道取两块蛋糕中较大的一块。问 JOI くん最多能取到多少蛋糕呢?

首先发现这不是博弈论问题因为对方傻。所以考虑 DP,令 F[x][y] 表示还剩下编号从 x 到 y 的蛋糕时 JOI くん最大能够取到的蛋糕大小。考虑转移:

若当前轮到 JOI くん 取蛋糕,F[x][y] = min(F[x+1][y] + A[x], F[x][y-1] + A[y]);

否则 F[x][y] = A[x] > A[y] ? F[x+1][y] : F[x][y-1]。

最后枚举第一块取的蛋糕编号,就可以得到答案啦!总时间复杂度为 O(N2)。

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

int n, a[2005];
long long ans, f[2005][2005];

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    int flag = n & 1;
    if (flag)
        for (int i = 0; i < n; ++i)
            f[i][0] = a[i];
    for (int i = 1; i < n; ++i)
    {
        flag ^= 1;
        for (int j = 0; j < n; ++j)
        {
            if (flag)
                f[j][i] = max(f[j][i - 1] + a[(j + i) % n], f[(j + 1) % n][i - 1] + a[j]);
            else
                f[j][i] = a[(j + i) % n] > a[j] ? f[j][i - 1] : f[(j + 1) % n][i - 1];
        }
    }
    for (int i = 0; i < n; ++i)
        ans = max(ans, a[i] + f[(i + 1) % n][n - 2]);
    cout << ans << endl;
    return 0;
}

JOI公園 (JOIPark)

最开始被题意卡住了 T^T(论外语题的危害),想到了最小生成树什么的东西。

有 N 个广场、M 条双向通道,维修每一条通道需要花费一定费用。现在可以在以广场 1 为中心、半径为 X 的范围内建造地下道,地下道可以让覆盖的所有广场互相连通,从而不再需要维修它们在地上的通道。建造这一地下道需要花费 C*X 的费用。问实施维修计划至少需要花费多少钱。

显然可以注意到 X 的大小一定刚好等于某一个广场和广场 1 之间的距离,否则会造成浪费。从原点 1 开始跑一遍单源最短路径,之后按照距离从小到大依次枚举每一个点,遍历从该点出发的边,判断其是否需要维护。总时间复杂度 O(N*logN+M)。

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

#define N 100005
#define M 400005

int n, m, c;
bool vis[N]; int head[N];
long long sum, ans, d[N];

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

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

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

void spfa(int s)
{
    memset(d, 0x3f, sizeof d);
    d[s] = 0; q.push(make_pair(-d[s], 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 (d[edge[i].to] > y + edge[i].val)
                d[edge[i].to] = y + edge[i].val,
                q.push(make_pair(-d[edge[i].to], edge[i].to));
        }
    }
}

int main()
{
    cin >> n >> m >> c;
    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), sum += z;
    spfa(1);
    for (int i = 1; i <= n; ++i)
        q.push(make_pair(-d[i], i));
    ans = sum;
    for (int i = 1; i <= n; ++i)
    {
        int x = q.top().second; q.pop(); vis[x] = true;
        for (int i = head[x]; i; i = edge[i].next)
            if (vis[edge[i].to])
                sum -= edge[i].val;
        ans = min(ans, sum + 1ll * d[x] * c);
    }
    cout << ans << endl;
    return 0;
}

舞踏会 (Ball)

有 N 个贵族(N 为偶数)参加公主的生日晚宴,每人都有一个舞蹈指数(踊りのうまさ)。他们需要排成一队,然后进行以下配对操作,直到队列中仅剩一人:

令队列前三个人出队,将舞蹈指数最高的和最低的两位贵族配对,让剩余一人排在队列尾端。

现在有 M 个人的位置已经确定了,需要安排剩余贵族的位置,使得最后剩余的贵族舞蹈指数最大。求这一最大值。

题解是树形 DP。如图所示,将序列变成树的样子。

如果二分答案的话,结点的值可以转化为 low 和 high 两种。设 f[x] 表示当 x 结点取到 high 时子树内取值不确定的叶子结点间取值为 high 的结点的最少个数。

对于某一叶子结点,若权值已经确定,则可断定 f[x] = inf(无解) 或 f[x] = 0(不存在取值不确定的结点);否则 f[x] = 1。

对于某一非叶子结点,若取值为 high,需要子结点中至少有两个取值为 high。

细节:取三个数 a、b、c 中较大两个数之和的操作可以通过 a + b + c - min(a, b, c) 实现。

最后判断一下 f[root] 是否符合条件即可。

注意到原序列就是按照新建的树的中根遍历序给出的,因此实现的时候直接用两个指针来进行 DP 就好了。

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

#define N 500005
#define inf 0x3f3f3f3f

int n, m, a[N], p[N], f[N];

int calc(int a, int b, int c)
{
    return a + b + c - max(max(a, b), c);
}

bool check(int mid)
{
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        f[i] = 1;
    for (int i = 1; i <= m; ++i)
        f[p[i]] = a[i] >= mid ? 0 : inf;
    for (int i = m + 1; i <= n; ++i)
        if (a[i] >= mid) ++cnt;
    int l = 1, r = n + 1;
    while (l < r)
        f[r++] = min(inf, calc(f[l], f[l + 1], f[l + 2])), l += 3;
    return f[l - 3] <= cnt;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        if (i <= m) scanf("%d", &p[i]);
    }
    int l = 1, r = 1000000000, 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;
}

城壁 (Rampart)

询问在 H 行 W 列的王国中避开 P 个障碍物,建造边长至少为 L 的城墙的方案数。

分别预处理出每一个点到左上和右下的“限界长”。然后对于每一个斜向下 45° 的对角线,借助树状数组统计左上顶点和右下顶点都在这条对角线上的正方形个数。

时间复杂度 O(N2处理限界长+N枚举对角线*NlogN树状数组统计答案)

事实上,常数是会很小的(优美的树状数组和 L 的限制),实际运行时间远远小于给定的时限(10 s)。

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

#define N 4005

int h, w, l, p, n;
int f1[N][N], f2[N][N], f3[N][N], f4[N][N], t[N];
long long ans;

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

int query(int x)
{
    int re = 0;
    for (int i = x; i; i -= i & -i)
        re += t[i];
    return re;
}

int main()
{
    cin >> h >> w >> l >> p;
    memset(f1, -1, sizeof f1); memset(f2, -1, sizeof f2);
    memset(f3, -1, sizeof f3); memset(f4, -1, sizeof f4);
    for (int x, y, i = 1; i <= p; ++i)
        scanf("%d%d", &x, &y),
        f1[x][y] = f2[x][y] = f3[x][y] = f4[x][y] = 0;
    for (int i = 1; i <= h; ++i)
    {
        f1[i][0] = 0; f2[i][w + 1] = 0;
        for (int j = 1; j <= w; ++j)
            if (f1[i][j] == -1)
                f1[i][j] = f1[i][j - 1] + 1;
        for (int j = w; j >= 1; --j)
            if (f2[i][j] == -1)
                f2[i][j] = f2[i][j + 1] + 1;
    }
    for (int i = 1; i <= w; ++i)
    {
        f3[0][i] = 0; f4[h + 1][i] = 0;
        for (int j = 1; j <= h; ++j)
            if (f3[j][i] == -1)
                f3[j][i] = f3[j - 1][i] + 1;
        for (int j = h; j >= 1; --j)
            if (f4[j][i] == -1)
                f4[j][i] = f4[j + 1][i] + 1;
    }
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            f1[i][j] = min(f1[i][j], f3[i][j]),
            f2[i][j] = min(f2[i][j], f4[i][j]);
    for (int x = h, y = 1; y <= w; x == 1 ? ++y : --x)
    {
        n = 0;
        for (int i = x, j = y; i <= h && j <= w; ++i, ++j) ++n;
        memset(t, 0, sizeof t);
        vector<pair<int, int>> v[N];
        for (int i = 1; i <= n; ++i)
        {
            for (auto j: v[i])
                insert(j.first, j.second);
            if (f1[x + i - 1][y + i - 1] >= l)
                ans += query(i - l + 1),
                ans -= query(i - f1[x + i - 1][y + i - 1]);
            if (f2[x + i - 1][y + i - 1] >= l)
                v[i + l - 1].push_back(make_pair(i, 1)),
                v[i + f2[x + i - 1][y + i - 1]].push_back(make_pair(i, -1));
        }
    }
    cout << ans << endl;
    return 0;
}