JOI 2012/2013 本選

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

官方网站链接

这一段时间做的几套日本本选题,发现日本题命题的时候是有一定的套路的:

第一题是一眼题,第二题是DP题,三、四题分别考察最短路和二分答案,而第五题考察的是强大的分析能力以及脑洞,用线段树和树状数组等进行区间操作。

日本人的得分情况:

从2013年开始分数逐年增高(2015竟然有AK的大神),而第四、五题的平均分都在10分以下(第五题的平均分竟然经常低于1分)。

做这套题的时候,我用了一个半小时得到了第一题和第三题的一共200分,成功进入 A ランク!所以之后会做几套春季合宿题了。

電飾 (Illumination)

一串灯泡,有暗有亮。可以最多进行一次操作,选定一段区间,使其中的所有灯泡的明暗发生改变。问最终得到的灯泡序列中亮暗相间的“交互列”的最长长度。

很容易发现,需要改变的序列一定是一串最长的交互列。这样直接枚举每一段交互列就可以在 O(N) 的时间内计算出了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

#define N 100005

int n, a[N], cnt[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int now = 1; cnt[now] = 1;
    for (int i = 2; i <= n; ++i)
        if (a[i] != a[i - 1])
            ++cnt[now];
        else ++cnt[++now];
    int ans = 0;
    for (int i = 1; i <= now; ++i)
        ans = max(ans, cnt[i] + cnt[i - 1] + cnt[i + 1]);
    cout << ans << endl;
    return 0;
}

IOI 列車で行こう (Takethe‘IOI’train)

车厢有“I”、“O”两种,而我们需要编成一列由这两种车厢交替相连组成的列车,其中第一节车厢和最后一节车厢都为“I”种类。有两个车库 S、T,其中分别有 N 节和 M 节车厢。我们可以按照顺序从中车库取出车厢加入到编成中的列车的末尾。在开始编成列车以前还可以从车库中取出车厢到待机用轨道中,不参与列车的编成。问编成的“IOIOI”列车的最长长度。

设 dp[X][Y][type] 表示取出 S 车库中的前 X 节车厢、T车库中的前 Y 节车厢,编成的列车的最后一节车厢种类为 type = 0? "O" : "I" 的编成列车的最长长度,最终答案为 max{dp[0...N][0...M][1]}。

转移时需要分别判断 S[X] 和T[Y] 的种类进行讨论。转移方程很显而易见。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

#define N 2005

char s[N], t[N];
int n, m, f[N][N][2], ans;

int main()
{
    cin >> n >> m;
    scanf("%s%s", s + 1, t + 1);
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
        {
            if (s[i] == 'O' && f[i - 1][j][1]) f[i][j][0] = f[i - 1][j][1] + 1;
            if (s[i] == 'I') f[i][j][1] = f[i - 1][j][0] + 1;
            if (t[j] == 'O' && f[i][j - 1][1]) f[i][j][0] = max(f[i][j][0], f[i][j - 1][1] + 1);
            if (t[j] == 'I') f[i][j][1] = max(f[i][j][1], f[i][j - 1][0] + 1);
            ans = max(ans, f[i][j][1]);
        }
    cout << ans << endl;
    return 0;
}

現代的な屋敷 (ModernMansion)

有一个又大又现代化的宅邸,由 M*N 个正方形的房间组成,每相邻的两个房间之间都有门连接(住在这样的房子里面不怕闹鬼么)。在某一时刻,只有可能南北向的门开启、东西向的门关闭或东西向的门开启,南北向的门关闭。有一些房间里有开关,按动开关可以让当时开启的门关闭,关闭的门开启。从一个房间走到相邻的房间或按动开关都需要一单位时间。初始时刻,你在 (1, 1) 的房间内,而只有南北向的门是开启的。你想要去到 (M, N) 的房间内,至少需要花费多少时间?

首先注意到 N、M 的范围都很大。经过观察后发现,只有起点、终点和存在开关的点需要考虑。可以把两种开门的状态想象成两个平行世界。按动开关,就会实现两个世界间的跳跃,花费时间为 1。每一个世界中,在能够互相到达的每一对关键点间连边,边权为两点间距离。

这样只需要从原点开始,跑一遍最短路即可,最终到两个世界中的终点的时间的最小值即为答案。

利用这种思想,建图的时候,点数为 O(K),边数为 O(K2)。而注意到很多边是冗余的(如下图所示),可以在建图时直接删去。边数也就被转化成了 O(K),符合时间要求。

实现的时候可以利用 vector+sort。很荣幸,我是 STL 重度依赖症。

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

#define N 200005

int m, n, k, x[N], y[N];
long long d[N * 2];
vector<pair<int, int>> v1[N], v2[N];

int head[N * 2];

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

inline 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 (d[x] != y) 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 >> m >> n >> k;
    v1[1].push_back(make_pair(1, k * 2 + 1));
    v1[m].push_back(make_pair(n, 0));
    v2[n].push_back(make_pair(m, 0));
    for (int i = 1; i <= k; ++i)
    {
        scanf("%d%d", &x[i], &y[i]);
        v1[x[i]].push_back(make_pair(y[i], i)),
        v2[y[i]].push_back(make_pair(x[i], k + i)),
        add(i, k + i, 1), add(k + i, i, 1);
    }
    for (int i = 1; i <= m; ++i)
    {
        sort(v1[i].begin(), v1[i].end());
        for (int j = 1; j < (int)v1[i].size(); ++j)
            add(v1[i][j - 1].second, v1[i][j].second,
                    v1[i][j].first - v1[i][j - 1].first),
            add(v1[i][j].second, v1[i][j - 1].second,
                    v1[i][j].first - v1[i][j - 1].first);
    }
    for (int i = 1; i <= n; ++i)
    {
        sort(v2[i].begin(), v2[i].end());
        for (int j = 1; j < (int)v2[i].size(); ++j)
            add(v2[i][j - 1].second, v2[i][j].second,
                    v2[i][j].first - v2[i][j - 1].first),
            add(v2[i][j].second, v2[i][j - 1].second,
                    v2[i][j].first - v2[i][j - 1].first);
    }
    spfa(0);
    if (d[k * 2 + 1] == 0x3f3f3f3f3f3f3f3fll) puts("-1");
    else cout << d[k * 2 + 1] << endl;
    return 0;
}

JOIOIの塔 (TowerofJOIOI)

从前有一座由圆盘叠成的高塔,圆盘自上而下半径依次增大,上面分别写着“J”、“O”、“I”三个字母之一。现在要拆掉高塔,堆叠成许多小塔,使得每一个小塔上的字符自上而下依次是“JOI”或“IOI”且圆盘半径单调递增。问最多能叠成多少个小塔。

官方题解——お疲れ様でした。

观察两种小塔,底座都是相同的“I-O”,只有顶部不相同。要得到最大答案,需要尽量让半径较大的“I”圆盘当作底座。

二分答案。若需要叠成 X 个圆盘,显然至少需要 X 个底座。贪心让半径最大的的 X 个“I”圆盘当作底座一定能够使答案最优,根据这一结论就可以实现在 O(N) 的时间里完成判断了。总时间复杂度 O(N*logN),刚刚好可以接受。

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

#define N 1000005

int n;
char str[N];

bool check(int mid)
{
    int ans = 0, cnt = 0, s1 = 0, s2 = 0;
    for (int i = n; i; --i)
    {
        if (str[i] == 'I')
        {
            if (cnt < mid) ++cnt, ++s1;
            else if (s2) --s2, ++ans;
        }
        else if (str[i] == 'O')
        {
            if (s1) --s1, ++s2;
        }
        else if(s2) --s2, ++ans;
    }
    return ans == mid;
}

int main()
{
    cin >> n;
    scanf("%s", str + 1);
    int l = 0, r = n / 3 + 1, ans = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

バブルソート (BubbleSort)

本题后20分才是精华!!!

本题后20分才是精华!!!

本题后20分才是精华!!!

给定一个数串。你需要先交换其中的两个数,之后对其进行冒泡排序。那么你在进行冒泡排序的时候至少要进行多少次交换呢?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void bubble_sort(int *a, int n) {
  int i, j;
  for (i = 0; i < n - 1; ++i) {
    for (j = 0; j < n - 1; ++j) {
      if (a[j] > a[j + 1]) {
      /* 以下 3 行が 1 回の整数の交換に相当 */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

首先对于给定的一个数串,可以利用树状数组在 O(N*logN) 的时间内求出需要交换的次数。

最原始的想法是枚举开始时交换的两个数字,再进行判断。然而这道题竟然连暴力分都不愿意给!!!从第一个测试点开始 N 就等于1000也真是让人醉了。

只有傻子和真·大神才会在考场上写这种题!

先来膜拜原题解。@iwiwi

首先需要特判:若原本数列就会单调递增的话输出 0 或 1。

其余的情况下一定可以交换两个点使得答案变小。以编号为X坐标,数值为Y坐标把所有数放在平面坐标系中。可以发现,所有的点横坐标两两不同,而纵坐标有可能会相同。

考虑交换两个点,则首先可以知道前一个点的纵坐标一定大于后一个点的纵坐标。设其分别为 a、b。交换后答案的减少量等于在这两个点之间纵坐标大于 a 且小于等于 b 的点数 + 纵坐标大于等于 a 且小于 b 的点数 + 1(当前的两个点之间交换)。其中前两个加数大概是在以这两个点为对顶点的矩形内的点的个数(上下边界需要特殊处理)。

还可以发现需要交换的两点一定分别在左上凸包和右下凸包上(如下图所示,正确性显然)。

左上の候補は,自分より左上に点がない点(上に赤色で示した 3 つだけ)。

同様に,右下の候補も絞れる(青い点)。点が 3 種類に分類された!

首先枚举右下角的蓝色点。对于当前点左侧的所有黑色点,判断其可更新多少个红色点的答案。发现一个黑色点只能够更新在它的左上方的红色点。对于红色点维护一个线段树,进行区间修改。最后只需要询问红色点在线段树中的最大权值的就可以更新答案了。

显然对于每一个蓝色点而言,如果去枚举每一个黑色点会产生很多浪费。

如图所示,对于相邻的两个蓝色点而言(咦?第二个怎么变绿了),更新时需要删去纵坐标较小的点,加上横坐标较大的点。我在代码中使用了优先队列去查找计入答案的点集中纵坐标最小的点。

仍然需要注意纵坐标相等的情况! >>这可真是令人疲惫啊!

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

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

bool vis[N];
int n, a[N], ans, s1, s2, maxt[N * 4], tag[N * 4], f[N];
vector<int> v;
vector<pair<int, int>> aka, ao;
priority_queue<pair<int, int>> q, q2;

void BIT_insert(int x)
{
    for (int i = x; i; i -= i & -i)
        ++f[i];
}

int BIT_query(int x)
{
    int re = 0;
    for (int i = x; i <= n; i += i & -i)
        re += f[i];
    return re;
}

long long calc()
{
    long long re = 0;
    for (int i = 1; i <= n; ++i)
        re += BIT_query(a[i] + 2), BIT_insert(a[i] + 1);
    return re;
}

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

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

bool cmp(pair<int, int> x, pair<int, int> y)
{
    if (x.second == y.second) return x.first < y.first;
    return x.second < y.second;
}

void insert_p(int opt, int x, int y, int z)
{
    int l, r;
    l = upper_bound(aka.begin(), aka.end(), make_pair(-1, y), cmp) - aka.begin();
    r = upper_bound(aka.begin(), aka.end(), make_pair(x, -1)) - aka.begin();
    insert(1, 1, s1, l + 1, r, z);
    if (opt) return;
    if (aka[l].second == y) ++l;
    if (l <= r)
        insert(1, 1, s1, l + 1, r, z);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]), v.push_back(a[i]);
    for (int i = 2; i <= n; ++i)
        if (a[i] < a[i - 1]) goto begin;
    for (int i = 2; i <= n; ++i)
        if (a[i] == a[i - 1])
            { puts("0"); return 0; }
    puts("1"); return 0;

    begin: ;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();

    for (int i = 1; i <= n; ++i)
        if (aka.empty() || a[i] > (aka.end() - 1)->second)
            aka.push_back(make_pair(i, a[i])), vis[i] = true;
    for (int i = n; i >= 1; --i)
        if (!vis[i] && (ao.empty() || a[i] < (ao.end() - 1)->second))
            ao.push_back(make_pair(i, a[i])), vis[i] = true;
    ao.push_back(make_pair(0, -1));
    reverse(ao.begin(), ao.end());

    s1 = aka.size(), s2 = ao.size();
    for (int i = 1; i < s2; ++i)
    {
        while (!q.empty() && -q.top().first < ao[i].second)
            insert_p(0, q.top().second, -q.top().first, -1), q.pop();
        for (int j = ao[i - 1].first + 1; j < ao[i].first; ++j)
            if (!vis[j])
                insert_p(0, j, a[j], 1), q.push(make_pair(-a[j], j));
        while (!q.empty() && -q.top().first == ao[i].second)
            insert_p(1, q.top().second, -q.top().first, -1),
            q2.push(q.top()), q.pop();
        ans = max(ans, maxt[1] + 1);
        while (!q2.empty() && -q2.top().first == ao[i].second)
            insert_p(1, q2.top().second, -q2.top().first, 1),
            insert_p(0, q2.top().second, -q2.top().first, -1), q2.pop();
    }
    cout << calc() - ans << endl;
    return 0;
}