跳转至

250705 模拟赛

P12649 [KOI 2024 Round 2] 收集彩球

题意

有 \(2n\) 个球，每个球是 \(n\) 种颜色中的一种，一种颜色恰有两个球。有 \(n+1\) 个盒子，每个盒子至多容纳两个球；当盒子中存在两个球时，上面的球会压住下面的球，因此你无法操作下面的球。初始时所有球都放在盒子里，并且第 \(n+1\) 个盒子为空。

你可以进行若干次操作，每次操作只能是如下两种中的一种：

  • 选出一个非空盒子 \(i\) 和一个空盒子 \(j\)，将 \(i\) 顶端的球移动到 \(j\) 中；
  • 选出一个非空盒子 \(i\) 和一个盒子 \(j\) 满足 \(j\) 中恰有一个球且与 \(i\) 顶端的球颜色相同，将 \(i\) 顶端的球移动到 \(j\) 中；

问：使对于任意颜色 \(i\)，它的两个球都位于同一个盒子中，最少的操作次数是多少；或报告无解。

\(n\le 2\times 10^5\)

注意到对于一个颜色 \(i\)，要想把它的两个球匹配，需要把压在两个球上面的球全部拿走。容易发现这是一个拓扑序的关系（虽然我太菜了没想出来），因此对于初始时每个盒子，都从顶端的球的颜色向底端球的颜色连一条有向边。

若两个颜色不在同一个连通块内，它们显然不会相互影响。同时注意到当一个连通块完事之后，它又会空出一个空位置；因此各个连通块是独立的。

注意到图上每个节点都有且仅连接了两条边。对于自环（同时重边）的情况，显然合法不需要考虑。对于一个大小超过 \(1\) 的环，也显然可以在 环的大小 \(+\ 1\) 步内解决。

其余情况，若连通块内存在恰好一个出度为 \(2\)（入度为 \(0\)）的点，该连通块形如两条链首尾分别相接；我们先取出入度为 \(0\) 的颜色的两个球，将它们单独匹配；然后两条链是容易的；因此这种情况是合法的，显然可以在 连通块大小 \(+\ 1\) 步内解决；

否则，连通块内存在多于两个出度为 \(2\)（入度为 \(0\)）的点（由于度数守恒，因此也存在相同数量的出度为 \(0\) 的点），由于我们只有一个空位，而一个零度点在开始时就会占用 \(1\) 个空位，因此不合法。

到这里思路已经很清晰了。劝诫大家一定要想明白之后再写，如果一边写一边想可能得不偿失。我的代码太长了，而且不是拓扑排序方法，因此就不展示了。

P12650 [KOI 2024 Round 2] 双 v 字形涂色

题意

给定一个 \(n\times m\) 的网格图，网格图上每个格子是黑白两种颜色。你可以最多进行如下操作两次：

  • 选择一个白色格子 \((i,j)\)，将它染为蓝色，然后不断向左上方走，并将沿途的格子都染为蓝色，直到遇见一个非白色格子；接着从 \((i,j)\) 的右上一个格子开始，不断向右上方走，将沿途的格子都染为蓝色，直到遇见一个非白色格子；

最大化最终蓝色格子的数量。

\(n,m\le 3000\)

预处理 la[i][j] 和 ra[i][j] 表示在初始局面下，从 \((i,j)\) 开始，分别可以向左上、右上扩展多远。

记 v[i][j] = la[i][j] + ra[i][j] - 1，含义显然。

情况不多，可以分讨。设两次操作位置分别为 \((x_1,y_1)\) 和 \((x_2,y_2)\)：

\((x_1,y_1)\) 和 \((x_2,y_2)\) 奇偶性不同

扩展出的两个 V 字一定不会相交。我们分别取奇数和偶数点内部的最优解，相加。

otherwise 并且一个 V 字的延长线圈出的面积严格包含另一个 V 字

容易递推求得答案。

otherwise 并且两个 V 字仍然无交

注意到要么可以用一条斜率为 \(1\) 的直线划分两个 V，要么可以用一条斜率为 \(-1\) 的直线划分两个 \(V\)。

记 fl[i][j] 表示从 \((i,j)\) 位置开始，先向左下扩展，再向左上扩展，最大覆盖范围；特别的，排除直接向左上扩展的情况。fr[i][j] 定义类似，表示向右侧扩展。

将 \((i,j)\) 位置的答案挂在 \(i+j\) 位置，fl 和 fr 各做一遍，分别求前后缀最优解，然后扫一遍即可。对于另一条直线，只需挂在 \(i-j+m\) 处即可。

因为 fl 和 fr 排除了直接向左上、右上扩展的情况，因此记得加上 la 和 ra 的贡献。

otherwise：两个 V 字有交

我们从交点处统计答案，不难写出贡献为 fl[i][j] + fr[i][j] + max(la[i][j], ra[i][j) - 2。

代码 
  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
// 不知道为啥最近的代码写的又 chou 又长
#include<iostream>
#include<cstring>
using namespace std;
const int N = 3010;

int n, m, ans;
int ban[N][N];

int v[N][N], la[N][N], ra[N][N];

void calc1() {
    int aa = 0, ab = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if((i + j) & 1) aa = max(aa, v[i][j]);
            else ab = max(ab, v[i][j]);
        }
    }
    ans = max(ans, aa + ab);
}

void calc2() {
    static int f[N][N];
    for(int i = 3; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            f[i][j] = max(max(f[i - 1][j - 1], f[i - 1][j + 1]), v[i - 2][j]);
            ans = max(ans, f[i][j] + v[i][j]);
        }
    }
}

int fl[N][N], fr[N][N];
void calc3() {
    for(int i = n; i >= 1; i--) {
        for(int j = 1; j <= m; j++) {
            if(ban[i][j]) continue;
            fl[i][j] = max(la[i + 1][j - 1], fl[i + 1][j - 1]) + 1;
            fr[i][j] = max(ra[i + 1][j + 1], fr[i + 1][j + 1]) + 1;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(ban[i][j]) continue;
            ans = max(ans, fl[i][j] + fr[i][j] - 1 + max(la[i][j], ra[i][j]) - 1);
        }
    }
}

inline void gmax(int &a, int b) { a = max(a, b); }

void calc4() {
    static int gl[2 * N], gr[2 * N];
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            gmax(gl[i - j + m], max(fl[i][j], la[i][j]));
            gmax(gr[i - j + m], max(fr[i][j], ra[i][j]));
        }
    }
    for(int i = 1; i <= n + m; i++) gmax(gr[i], gr[i - 1]);
    for(int i = n + m; i >= 1; i--) gmax(gl[i], gl[i + 1]);
    for(int i = 1; i < n + m; i++) {
        ans = max(ans, gl[i + 1] + gr[i]);
    }
    memset(gl, 0, sizeof(gl));
    memset(gr, 0, sizeof(gr));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            gmax(gl[i + j - 1], max(fl[i][j], la[i][j]));
            gmax(gr[i + j - 1], max(fr[i][j], ra[i][j]));
        }
    }
    for(int i = 1; i <= n + m; i++) gmax(gl[i], gl[i - 1]);
    for(int i = n + m; i >= 1; i--) gmax(gr[i], gr[i + 1]);
    for(int i = 1; i < n + m; i++) {
        ans = max(ans, gl[i] + gr[i + 1]);
    }
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            ban[i][j] = c == '0';
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(ban[i][j]) continue;
            la[i][j] = la[i - 1][j - 1] + 1;
            ra[i][j] = ra[i - 1][j + 1] + 1;
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(ban[i][j]) continue;
            v[i][j] = la[i][j] + ra[i][j] - 1;
        }
    }

    calc1();
    calc2();
    calc3();
    calc4();

    cout << ans << endl;

    return 0;
}

P12652 [KOI 2024 Round 2] 拔树游戏

题意

给定一棵以 \(1\) 为根的有根树，点有点权。定义一次“拔除”操作如下：

  • 设当前节点为 \(u\)（初始为 \(1\)），若 \(u\) 是叶子，则删去 \(u\)，操作结束；否则找到 \(u\) 点权最小的儿子 \(v\)，执行 \(a_u\gets a_v\)，然后 \(u\gets v\)；

对原树执行 \(n\) 次拔除操作，问每次操作前根节点的权值是多少。

\(n\le 3\times 10^5\)

考虑暴力怎么做。拔除操作我们可以通过递归函数 f(u) 实现，该函数先处理叶子节点的情况，然后找到权值最小的儿子 \(v\) 进行递归处理。

注意到子树内外是独立的。因此我们可以将每棵子树的答案写成一个序列，表示进行 \(i\) 次拔除操作之前子树的根是序列的第 \(i\) 项。

考虑这个序列如何转移。设当前节点为 \(u\)，先将 \(a_u\) 加入 \(u\) 序列；然后初始时有 \(|to[u]|\) 个指针，依次指向 \(|to[u]|\) 个子节点的序列的第一项；接着，找到所有指针中所指数字最小的一个，加入 \(u\) 序列的末尾；

考虑将儿子节点的序列也展开为这个过程，我们就可以得到一个方法：有一个候选点集 \(S\)，初始只有 \(1\) 号节点；每次，找到 \(S\) 中点权最小的节点 \(u\)，输出 \(u\) 的权值；然后加入 \(u\) 的所有儿子节点；

用堆维护即可，时间复杂度 \(O(n\log n)\)。

代码 
 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<iostream>
#include<queue>
using namespace std;
const int N = 3e5 + 10;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

struct myPair {
    int u, d;
    inline bool operator<(const myPair &b) const {
        return d > b.d;
    }
};

int n;
int a[N];

priority_queue<myPair> que;

int main() {

    cin >> n;
    for(int i = 2; i <= n; i++) {
        int fa;
        cin >> fa;
        addEdge(fa, i);
    }
    for(int i = 1; i <= n; i++) cin >> a[i];

    que.push({1, a[1]});
    while(!que.empty()) {
        int u = que.top().u;
        que.pop();
        cout << a[u] << '\n';
        for(int e = head[u]; e; e = pool[e].next) {
            int v = pool[e].v;
            que.push({v, a[v]});
        }
    }

    return 0;
}