JOI 2014/2015 春季トレーニング合宿 競技 1

2015.10.27 08:10 Tue| 17 visits oi_2016| 2016_刷题日常| Text

官方网站链接

2015年10月24日(土)~25日(日)、PoPoQQQ 的 NOIP 考试。

然而这竟然是2015年JOI春季合宿题啊!相当于中国的CTSC啊!

コピー&ペースト2 (Copy and Paste 2)

考试的时候只会做小課題 1。正解什么的,永续赤黑木大法好!

永续赤黑木大法好!

永续赤黑木大法好!

事实上,由于 K 的范围真是小(原题解用了无数张幻灯片体现这一点),我们可以用 P[i][j] 表示在第 i 次操作后,最终在 j 位置上的字符的位置。显然,P[N][X] = X。只需要逆序模拟每一次操作,一直求到 P[0][X] 即为答案。

时间复杂度 O(NK),由于 P 数组的第一位可以滚动实现,空间复杂度 O(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
#include <bits/stdc++.h>
using namespace std;

#define N 200005

int k, m, n, a[N], b[N], c[N], f[N];
char str[N];

int main()
{
    cin >> k >> m;
    scanf("%s", str + 1);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
    for (int i = 1; i <= k; ++i)
        f[i] = i;
    for (int i = n; i; --i)
    {
        for (int j = 1; j <= k; ++j)
        {
            if (f[j] <= c[i]) continue;
            else if (f[j] <= c[i] + b[i] - a[i])
                f[j] += a[i] - c[i];
            else
                f[j] -= b[i] - a[i];
        }
    }
    for (int i = 1; i <= k; ++i)
        printf("%c", str[f[i]]);
    puts("");
    return 0;
}

愉快なロゴデザイン (En-JOI-able Logo Design)

简单题。

小课题 1:只需要枚举每一个起点,然后暴力匹配就可以了。时间复杂度 O(42N)。

小课题 2:发现合法串中存在很多段连续相同字符。当依次枚举起点时,只需要计算每一段端点处的变化。经过计算,相同字符有 3N 段,因此时间复杂度可被优化为 O(3N*4N)。

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

#define N 1050000

int n, len, cnt[4], ans;
char str[N];
pair<int, int> to[50];

int main()
{
    cin >> n;
    if (n == 0) { puts("0"); return 0; }
    len = 1 << (n * 2);
    scanf("%s", str);
    for (int i = 0; i < len; ++i)
        if (str[i] == 'J') str[i] = 1;
        else if (str[i] == 'O') str[i] = 2;
        else if (str[i] == 'I') str[i] = 3;
    int now = 0;
    int s = 0;
    for (int i = len / 4; i; i /= 4)
    {
        to[s++] = make_pair(now, 1);
        to[s++] = make_pair(now += i, 2);
        to[s++] = make_pair(now += i, 3); now += i;
    }
    to[s++] = make_pair(len - 1, 0);
    for (int i = 0; i < s - 1; ++i)
    {
        int x = to[i].first, y = to[i + 1].first, z = to[i].second;
        for (int j = x; j < y; ++j)
            if (str[j] == z) ++cnt[z];
    }
    ans = cnt[1] + cnt[2] + cnt[3];
    for (int i = 1; i <= len; ++i)
    {
        for (int j = 0; j < s - 1; ++j)
        {
            int z = to[j].second;
            if (str[to[j].first] == z) --cnt[z];
            if (str[to[j + 1].first] == z) ++cnt[z];
        }
        for (int j = 0; j < s; ++j)
            to[j].first = (to[j].first + 1) % len;
        ans = max(ans, cnt[1] + cnt[2] + cnt[3]);
    }
    cout << len - ans - 1 << endl;
    return 0;
}

たのしいたのしい家庭菜園 (Growing Vegetables is Fun 2)

线段树优化DP。

首先发现草很高,一定要先对草的高度进行离散化处理(很不幸,我这只傻X只会用 map)。

令 f[i][j] 表示对于前 i 根草,在不种植比高度 j 更高的草的前提下所能得到的最大收益。开心地发现只要从前、后分别做两次DP,之后枚举中点就可以得到答案啦。

由于每一根草的铲除和收获都会对答案造成影响,于是可以看作是先将所有的草铲除掉(答案减去所有的 Ci),而种植和收获都会分别产生Ci 和 Pi 的收益。

考虑对于某一根草 i 和某一高度 j,若草 i 的高度大于 j,那么就可以种植草 i,得到 Ci 的收益。而若令草 i 结果,则需要满足 i 草的高度高于之前种下的所有草的高度,能够得到 Ci + Pi 的收益。显而易见,f[i][j] 的值随着 j 的增大单调不减,因此令 i 草结果的最大收益可以直接从 f[i-1][Hi] 转移得到,并能够更新 f[i][Hi] 之上的一段区间。这样操作的时间复杂度为 O(N2)。

容易发现,f[i][j] 只需要支持单点查询、端点查询、区间修改为某一数值、区间加某一数值这样四个操作。直接使用线段树维护,时间复杂度被优化到 O(N*logN)。

再次发现草很值钱,一定要用 long long 记录答案。

然而大家的线段树只使用到了一个修改操作,至今不明所以。

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

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

int n, h[N], h2[N], p[N], c[N];
long long sum, ans, s1[N], s2[N];
long long mint[N << 2], maxt[N << 2], tag[N << 2], tag2[N << 2];
map<int, int> id;

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;
}

void lazy(int pos)
{
    if (tag[pos])
        mint[lson] = maxt[lson] = mint[rson] = maxt[rson] = tag[lson] = tag[rson] = tag[pos],
        tag[pos] = tag2[lson] = tag2[rson] = 0;
    else
    {
        mint[lson] += tag2[pos], maxt[lson] += tag2[pos],
        mint[rson] += tag2[pos], maxt[rson] += tag2[pos];
        if (tag[lson]) tag[lson] += tag2[pos];
        else tag2[lson] += tag2[pos];
        if (tag[rson]) tag[rson] += tag2[pos];
        else tag2[rson] += tag2[pos];
        tag2[pos] = 0;
    }
}

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

int query2(int pos, int l, int r, long long x)
{
    if (maxt[pos] <= x) return r;
    if (tag[pos] || tag2[pos]) lazy(pos);
    int mid = (l + r) >> 1;
    if (mint[rson] > x) return query2(lson, l, mid, x);
    return query2(rson, mid + 1, r, x);
}

void modify(int pos, int l, int r, int x, int y, long long z)
{
    if (x <= l && r <= y)
    {
        mint[pos] = maxt[pos] = tag[pos] = z; tag2[pos] = 0;return;
    }
    if (tag[pos] || tag2[pos]) lazy(pos);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y, z);
    if (y > mid) modify(rson, mid + 1, r, x, y, z);
    mint[pos] = min(mint[lson], mint[rson]);
    maxt[pos] = max(maxt[lson], maxt[rson]);
}

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

int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
        h[i] = read(), p[i] = read(), c[i] = read();
    for (int i = 1; i <= n; ++i)
        sum -= c[i], h2[i] = h[i];
    sort(h2 + 1, h2 + n + 1);
    for (int i = 1; i <= n; ++i)
        id[h2[i]] = i;
    for (int i = 1; i <= n; ++i)
        h[i] = id[h[i]];
    for (int i = 1; i <= n; ++i)
    {
        long long s = query(1, 1, n, h[i]);
        modify2(1, 1, n, h[i], n, c[i]);
        int t = query2(1, 1, n, s + p[i] + c[i]);
        modify(1, 1, n, h[i], t, s + p[i] + c[i]);
        s1[i] = query(1, 1, n, n);
    }
    memset(maxt, 0, sizeof maxt);
    memset(mint, 0, sizeof mint);
    memset(tag, 0, sizeof tag);
    memset(tag2, 0, sizeof tag2);
    for (int i = n; i; --i)
    {
        long long s = query(1, 1, n, h[i]);
        modify2(1, 1, n, h[i], n, c[i]);
        int t = query2(1, 1, n, s + p[i] + c[i]);
        modify(1, 1, n, h[i], t, s + p[i] + c[i]);
        s2[i] = query(1, 1, n, n);
    }
    for (int i = 1; i < n; ++i)
        ans = max(ans, sum + s1[i] + s2[i + 1]);
    cout << ans << endl;
    return 0;
}

IOIOI カード占い (IOIOI Cards)

PoPoQQQ:看到这种题,首先就要想到差分和前缀和。

首先差分一下,发现了有四个需要修改的点。之后建图,枚举两两之间的点对跑最短路即为答案。

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

#define N 1000005

int A, B, C, D, E, n, p[5];
long long d[N], dist[5][5];

int head[N];

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

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 >> A >> B >> C >> D >> E;
    p[1] = A; p[2] = p[1] + B;
    p[3] = p[2] + C; p[4] = p[3] + D;
    cin >> n;
    for (int x, y, i = 1; i <= n; ++i)
    {
        scanf("%d%d", &x, &y);
        add(x - 1, y, y - x + 1), add(y, x - 1, y - x + 1);
    }
    for (int i = 1; i <= 4; ++i)
    {
        spfa(p[i]);
        for (int j = 1; j <= 4; ++j)
            dist[i][j] = d[p[j]];
    }
    long long ans = min(min(dist[1][2] + dist[3][4],
                  dist[1][3] + dist[2][4]),
                  dist[1][4] + dist[2][3]);
    if (ans > 0x3f3f3f3f3f3f3f3fll)
        puts("-1");
    else cout << ans << endl;
    return 0;
}