POI 选做

简述

突然记起来 CSP 前特别喜欢的 POI 题还有一堆没写,所以就有了这个坑。

「POI2015」TRZ

写起来还挺麻烦。

我们考虑先把条件写出来:

\[ \begin{cases} s_r^1 – s_{l – 1}^1 \neq s_r^2 – s_{l – 1}^2 \neq s_r^2 – s_{l – 1}^2 \neq s_r^1 – s_{l – 1}^1 \end{cases} \]

进行移项之后发现可以做成自身的特征:

\[ \begin{cases} s_r^1 – s_r^2 \neq s_{l – 1}^1 – s_{l – 1}^2 \\ s_r^1 – s_r^3 \neq s_{l – 1}^1 – s_{l – 1}^3 \\ s_r^2 – s_r^3 \neq s_{l – 1}^2 – s_{l – 1}^3 \end{cases} \]

我们需要找到最长的区间使得这个条件成立,那么其实这就是一个偏序问题。每一个三维的点每一维直接做成其特征即可。而这个偏序需要知道除自己以外的所有信息,所以不能像正常的偏序来搞。所以,我们来进行拼凑。考虑按 \(x\) 排序,然后把 \(y\) 插入权值线段树,最后每个节点维护两个不同的 \(z\) 的极点位置即可。有点难写。

// P3590.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, INF = 0x3f3f3f3f;

int n, ans, ptot = 1;
char str[MAX_N];

struct node
{
    int lson, rson, max_val[2] = {-1, -1}, min_val[2] = {INF, INF};
} nodes[MAX_N * 3];

struct package
{
    int id, x, y, z;
    bool operator<(const package &rhs) const { return x < rhs.x; }
} pre[MAX_N], ai[MAX_N], bi[MAX_N];

int update(int qx, int l, int r, int p, package val)
{
    if (p == 0)
        p = ++ptot;
    if (nodes[p].min_val[0] > val.id)
    {
        if (nodes[p].min_val[0] != INF && bi[nodes[p].min_val[0]].id != val.z)
            nodes[p].min_val[1] = nodes[p].min_val[0];
        nodes[p].min_val[0] = val.id;
    }
    else if (nodes[p].min_val[1] > val.id && bi[nodes[p].min_val[0]].z != val.z)
        nodes[p].min_val[1] = val.id;
    if (nodes[p].max_val[0] < val.id)
    {
        if (nodes[p].max_val[0] != -1 && bi[nodes[p].max_val[0]].z != val.z)
            nodes[p].max_val[1] = nodes[p].max_val[0];
        nodes[p].max_val[0] = val.id;
    }
    else if (nodes[p].max_val[1] < val.id && bi[nodes[p].max_val[0]].z != val.z)
        nodes[p].max_val[1] = val.id;
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    if (qx <= mid)
        nodes[p].lson = update(qx, l, mid, nodes[p].lson, val);
    else
        nodes[p].rson = update(qx, mid + 1, r, nodes[p].rson, val);
    return p;
}

int query(int ql, int qr, int l, int r, int p, package val)
{
    if (p == 0)
        return 0;
    if (ql <= l && r <= qr)
    {
        int min_val, max_val;
        if (nodes[p].min_val[0] == INF)
            return 0;
        min_val = (val.z == bi[nodes[p].min_val[0]].z) ? nodes[p].min_val[1] : nodes[p].min_val[0];
        max_val = (val.z == bi[nodes[p].max_val[0]].z) ? nodes[p].max_val[1] : nodes[p].max_val[0];
        if (min_val == INF || max_val == -1)
            return 0;
        return max(abs(val.id - min_val), abs(val.id - max_val));
    }
    int mid = (l + r) >> 1, ret = 0;
    if (ql <= mid)
        ret = max(ret, query(ql, qr, l, mid, nodes[p].lson, val));
    if (mid < qr)
        ret = max(ret, query(ql, qr, mid + 1, r, nodes[p].rson, val));
    return ret;
}

int main()
{
    scanf("%d%s", &n, str);
    for (int i = 0, ptr = 0; i < n; i++)
    {
        if (str[i] != str[ptr])
            ptr = i;
        ans = max(ans, i - ptr + 1);
    }
    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1];
        if (str[i - 1] == 'C')
            pre[i].x++;
        if (str[i - 1] == 'B')
            pre[i].y++;
        if (str[i - 1] == 'S')
            pre[i].z++;
    }
    int lower = 0;
    for (int i = 1; i <= n; i++)
    {
        ai[i].x = pre[i].x - pre[i].y;
        ai[i].y = pre[i].x - pre[i].z;
        ai[i].z = pre[i].y - pre[i].z;
        lower = min(lower, min(ai[i].x, min(ai[i].y, ai[i].z)));
        ai[i].id = i;
    }
    n++;
    for (int i = 1; i <= n; i++)
        ai[i].x -= lower - 1, ai[i].y -= lower - 1, ai[i].z -= lower - 1;
    for (int i = 1; i <= n; i++)
        bi[i] = ai[i];
    bi[0] = bi[n], sort(ai + 1, ai + 1 + n);
    int domain = n - lower + 1;
    for (int i = 1, ptr = 1; i <= n; i++)
    {
        if (ai[i].x != ai[ptr].x)
            ptr = i;
        if (ai[i].x != ai[i + 1].x)
        {
            for (int j = ptr; j <= i; j++)
                ans = max(ans, max(query(1, ai[j].y - 1, 1, domain, 1, ai[j]), query(ai[j].y + 1, domain, 1, domain, 1, ai[j])));
            for (int j = ptr; j <= i; j++)
                update(ai[j].y, 1, domain, 1, ai[j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

「POI2009」LYZ

之前没学过 Hall 定理,后面发现结论还算是比较显然的:对于任意的左部点集 \(U\),与之相连的极大右部点集 \(S\) 要满足 \(|U| \leq |S|\)。本题在数据范围小的时候显然可以直接二分图匹配做,但是现在的数据并不允许,并要求维护完美匹配性。首先发现最糟情况时存在一个区间 \([l, r]\) 满足:

\[ \sum_{i = l}^r X_i > (r – l + 1 + d) k \]

移项得到:

\[ \sum_{i = l}^r (X_i – k) > d \times k \]

线段树找一段这样的即可。

// P3488.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5 + 200;

typedef long long ll;

int n, m, k, d;

struct node
{
    ll lft, rig, sum, seg;
} nodes[MAX_N << 2];

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

void pushup(int p)
{
    nodes[p].sum = nodes[lson].sum + nodes[rson].sum;
    nodes[p].lft = max(nodes[lson].lft, nodes[lson].sum + nodes[rson].lft);
    nodes[p].rig = max(nodes[rson].rig, nodes[rson].sum + nodes[lson].rig);
    nodes[p].seg = max(nodes[lson].rig + nodes[rson].lft, max(nodes[lson].seg, nodes[rson].seg));
}

void build(int l, int r, int p)
{
    if (l == r)
    {
        nodes[p] = node{0, 0, -k, -k};
        return;
    }
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(p);
}

void update(int qx, int l, int r, int p, int val)
{
    if (l == r)
    {
        nodes[p].sum += val, nodes[p].seg += val;
        nodes[p].lft = nodes[p].rig = max(0LL, nodes[p].sum);
        return;
    }
    if (qx <= mid)
        update(qx, l, mid, lson, val);
    else
        update(qx, mid + 1, r, rson, val);
    pushup(p);
}

#undef mid
#undef rson
#undef lson

int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &d), build(1, n, 1);
    for (int i = 1; i <= m; i++)
    {
        int xpos, val;
        scanf("%d%d", &xpos, &val), update(xpos, 1, n, 1, val);
        puts(nodes[1].seg <= 1LL * d * k ? "TAK" : "NIE");
    }
    return 0;
}

「POI2014」KAR

想起在纪中做过的一道 A 组 SB 题,跟这个比较一致。发现区间之间可以直接维护,那么就上个线段树就好了。

// P3569.cpp
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 4e5 + 200;

int n, ai[MAX_N][2], q;
bool nodes[MAX_N << 2][2][2];

inline char nc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

inline void pushup(int p, int l, int r)
{
    nodes[p][0][0] = nodes[p][1][0] = nodes[p][0][1] = nodes[p][1][1] = false;
    for (register int a = 0; a < 2; a++)
        for (register int b = 0; b < 2; b++)
            for (register int c = 0; c < 2; c++)
                for (register int d = 0; d < 2; d++)
                    nodes[p][a][d] |= nodes[lson][a][c] && nodes[rson][b][d] && ai[mid][c] <= ai[mid + 1][b];
}

inline void update(int qx, int l, int r, int p)
{
    if (l == r)
        return;
    if (qx <= mid)
        update(qx, l, mid, lson);
    else
        update(qx, mid + 1, r, rson);
    pushup(p, l, r);
}

inline void build(int l, int r, int p)
{
    if (l == r)
    {
        nodes[p][0][0] = nodes[p][1][1] = true;
        return;
    }
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(p, l, r);
}

#undef mid
#undef rson
#undef lson

int main()
{
    n = read();
    for (register int i = 1; i <= n; i++)
        ai[i][0] = read(), ai[i][1] = read();
    q = read(), build(1, n, 1);
    while (q--)
    {
        int x = read(), y = read();
        swap(ai[x][0], ai[y][0]), swap(ai[x][1], ai[y][1]);
        update(x, 1, n, 1), update(y, 1, n, 1);
        puts(nodes[1][0][0] || nodes[1][0][1] || nodes[1][1][0] || nodes[1][1][1] ? "TAK" : "NIE");
    }
    return 0;
}

「POI2014」KLO

我们考虑相间而放,用一个堆以大小为关键字来维护可选项。注意的是,我们尽量把和末尾颜色相同的 block 放前。每次选出最大的块、或者是次大的块放置,然后再 check 即可。

// P3569.cpp
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 4e5 + 200;

int n, ai[MAX_N][2], q;
bool nodes[MAX_N << 2][2][2];

inline char nc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

inline void pushup(int p, int l, int r)
{
    nodes[p][0][0] = nodes[p][1][0] = nodes[p][0][1] = nodes[p][1][1] = false;
    for (register int a = 0; a < 2; a++)
        for (register int b = 0; b < 2; b++)
            for (register int c = 0; c < 2; c++)
                for (register int d = 0; d < 2; d++)
                    nodes[p][a][d] |= nodes[lson][a][c] && nodes[rson][b][d] && ai[mid][c] <= ai[mid + 1][b];
}

inline void update(int qx, int l, int r, int p)
{
    if (l == r)
        return;
    if (qx <= mid)
        update(qx, l, mid, lson);
    else
        update(qx, mid + 1, r, rson);
    pushup(p, l, r);
}

inline void build(int l, int r, int p)
{
    if (l == r)
    {
        nodes[p][0][0] = nodes[p][1][1] = true;
        return;
    }
    build(l, mid, lson), build(mid + 1, r, rson);
    pushup(p, l, r);
}

#undef mid
#undef rson
#undef lson

int main()
{
    n = read();
    for (register int i = 1; i <= n; i++)
        ai[i][0] = read(), ai[i][1] = read();
    q = read(), build(1, n, 1);
    while (q--)
    {
        int x = read(), y = read();
        swap(ai[x][0], ai[y][0]), swap(ai[x][1], ai[y][1]);
        update(x, 1, n, 1), update(y, 1, n, 1);
        puts(nodes[1][0][0] || nodes[1][0][1] || nodes[1][1][0] || nodes[1][1][1] ? "TAK" : "NIE");
    }
    return 0;
}

「POI2010」Monotonicity

首先我们可以把符号序列给倍长出来,然后再考虑用子序列匹配那一套进行 DP。而这里只需要单维,也就是说我们并不记录子序列的长度,因为可以注意到最长的答案中间切掉,也是满足最优子结构的(证明),所以可以不用记录,搞个树状数组就完事了。

// BZ2090.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, MAX_M = 5e6 + 200;

int n, m, ai[MAX_N], nodes[3][MAX_M], dp[MAX_N];
char str[MAX_N];

inline int lowbit(int x) { return x & (-x); }

void update(int idx, int x, int d)
{
    for (; x < MAX_M; x += lowbit(x))
        nodes[idx][x] = max(nodes[idx][x], d);
}

int query(int idx, int x, int ret = 0)
{
    for (; x; x -= lowbit(x))
        ret = max(ret, nodes[idx][x]);
    return ret;
}

int main()
{
    char tmp[2];
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    for (int i = 1; i <= m; i++)
        scanf("%s", tmp), str[i] = tmp[0];
    for (int i = m + 1; i <= n; i++)
        str[i] = str[(i - 1) % m + 1];
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        dp[i] = max(nodes[2][ai[i]], max(query(0, ai[i] - 1), query(1, MAX_M - ai[i]))) + 1;
        ans = max(ans, dp[i]);
        if (str[dp[i]] == '=')
            nodes[2][ai[i]] = max(nodes[2][ai[i]], dp[i]);
        else if (str[dp[i]] == '<')
            update(0, ai[i], dp[i]);
        else
            update(1, MAX_M - ai[i] + 1, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}

「POI2005」DWA-Two Parties

这道题就很骚了。

首先有个结论,就是一定能找出一个划分方案,使得某个集合中所有的点都连上了偶数条边,且是最优解。知道这个,我们可以尝试给每个点表一个状态 \(x_i\),代表其集合 ID(0/1)。这样我们可以搞成一个异或方程组,然后高斯消元得到一个方案即可。

// P3429.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 220;

int n, deg[MAX_N], mat[MAX_N][MAX_N];

int main()
{
    scanf("%d", &n);
    for (int i = 1, tot, v; i <= n; i++)
    {
        scanf("%d", &tot);
        while (tot--)
            scanf("%d", &v), mat[i][v] = 1, deg[i]++;
        if (deg[i] & 1)
            mat[i][i] = mat[i][n + 1] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        int key = i;
        for (int j = i + 1; j <= n; j++)
            if (mat[j][i] != 0)
            {
                key = j;
                break;
            }
        if (key != i)
            for (int j = i; j <= n + 1; j++)
                swap(mat[i][j], mat[key][j]);
        for (int j = i + 1; j <= n; j++)
            if (mat[j][i] == 1)
                for (int k = i; k <= n + 1; k++)
                    mat[j][k] ^= mat[i][k];
    }
    mat[n][n] = 1;
    // reverse;
    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = i + 1; j <= n; j++)
            if (mat[i][j] != 0)
                for (int k = j; k <= n + 1; k++)
                    mat[i][k] ^= mat[j][k];
        mat[i][i] = 1;
    }
    int tot = 0;
    for (int i = 1; i <= n; i++)
        tot += mat[i][n + 1];
    printf("%d\n", tot);
    for (int i = 1; i <= n; i++)
        if (mat[i][n + 1])
            printf("%d ", i);
    puts("");
    return 0;
}

「POI2012」STU-Well

大概思路:首先二分那个差值,然后我们再来算每个位置归零的代价,再找最小的位置即可。

那么我们如何快速计算每个位置归零的代价呢?首先我们可以计算让全局合法的最小代价,方式是正反各扫一遍,保证 \(|a_i – a_{i + 1}| \leq mid\)。枚举 \(k\) 时,我们可以分左右来算贡献。以左侧为例,找到一个位置 \(a_{L} > (k – L)mid\),那么 \([L, i – 1]\) 这一部分的和减去等差数列之和就是部分贡献了。我想了一会为什么这样是对的,发现:如果 \(a_{L} > (k – L)mid\),且即使这段区间不是等差的,那么这段区间和减去等差数列之和,「多扣」的部分会从 \(a_L\) 上扣除。右侧原理一致。

// P3534.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 1e6 + 200;

int n;
ll m, xi[MAX_N], ai[MAX_N], pre[MAX_N], prefix[MAX_N], suffix[MAX_N];

int check(int mid)
{
    ai[1] = xi[1];
    for (int i = 2; i <= n; i++)
        ai[i] = min(ai[i - 1] + mid, xi[i]);
    for (int i = n - 1; i >= 1; i--)
        ai[i] = min(ai[i + 1] + mid, ai[i]);
    ll acc = 0;
    for (int i = 1; i <= n; i++)
        acc += xi[i] - ai[i], pre[i] = pre[i - 1] + ai[i];
    if (acc > m)
        return 0;
    for (int i = 1, ptr = 1; i <= n; i++)
    {
        while (ptr < i && ai[ptr] <= 1LL * (i - ptr) * mid)
            ptr++;
        prefix[i] = pre[i - 1] - pre[ptr - 1] - 1LL * (i - ptr) * (i - ptr + 1) / 2 * mid;
    }
    for (int i = n, ptr = n; i >= 1; i--)
    {
        while (ptr > i && ai[ptr] <= 1LL * (ptr - i) * mid)
            ptr--;
        suffix[i] = pre[ptr] - pre[i] - 1LL * (ptr - i) * (ptr - i + 1) / 2 * mid;
    }
    for (int i = 1; i <= n; i++)
        if (prefix[i] + suffix[i] + acc + ai[i] <= m)
            return i;
    return 0;
}

int main()
{
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &xi[i]);
    int l = 0, r = 1e9, res = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid - 1, res = mid;
        else
            l = mid + 1;
    }
    printf("%d %d\n", check(res), res);
    return 0;
}

 

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注