「九省联考 2018」部分题解

发表于 |

前言

快要省选了。这个小菜鸡准备在考前突击一下——把去年的省选题做完。

但是他太菜了，看了题解之后也只会四道题目。

今年他究竟能否进入省队呢？让我们拭目以待。

2019.4.7 upd: 最后还是苟进省队了 QAQ

目录

好的现在我们步入正题 —— 九省联考 2018 题解。

Day \ Task Task 1 Task 2 Task 3
Day 1 一双木棋 链接 题解 IIIDX 链接 题解 秘密袭击 链接 暂无题解
Day 2 劈配 链接 题解 林克卡特树 链接 题解 制胡窜 链接 暂无题解

「Day 1 / Task 1」一双木棋

思路分析

简单的博弈 + 状态压缩动态规划，使用 map + 记忆化搜索实现即可。

代码实现

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
//「SHOI 2018」Chess
#include <cstdio>
#include <map>
using namespace std;

typedef long long ll;
const int maxn = 10, inf = 1e9 + 1;
int n, m, a[maxn + 3][maxn + 3], b[maxn + 3][maxn + 3], r[maxn];
ll p[maxn];
map<ll, int> dp;

int dfs(ll x, int type) {
    if (dp.count(x)) return dp[x];
    int &res = dp[x] = type ? inf : -inf;
    for (int i = 1; i <= n; i++) if (r[i] < r[i - 1]) {
        r[i]++;
        ll s = x + p[n - i];
        if (type) res = min(res, dfs(s, type ^ 1) - b[i][r[i]]);
        else res = max(res, dfs(s, type ^ 1) + a[i][r[i]]);
        r[i]--;
    }
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &b[i][j]);
    p[0] = 1;
    for(int i = 1; i <= n; i++) p[i] = p[i - 1] << 4;
    ll t = 0;
    for (int i = 1; i <= n; i++) t = t << 4 | m;
    dp[t] = 0, r[0] = m;
    printf("%d\n", dfs(0, 0));
    return 0;
}

「Day 1 / Task 2」IIIDX

思路分析

首先将 $i$ 和 $\lfloor \frac{i}{k} \rfloor$ 连边，问题转化成给定一棵树，它的 BFS 序是 $1$ 到 $n$，再给定一个序列 $A_1, A_2, \cdots, A_n$，将数填入树中，使得对于每条边父亲的权值小于等于儿子的权值。问字典序最大的方案。

容易想到试填法，对 $1$ 到 $n$ 号点依次找到它的的最大权值。现在的问题变成了如何快速查询某个点的最大权值。假设点 $v$ 上的数为 $x$，那么它子树中的数要大于等于 $x$，也就是大于等于 $x$ 的数要留下 $\text{size}(v)$ 个。我们将 $A$ 从小到大排序，记 $B_i$ 表示序列中的后 $n - i + 1$ 个数被借走了一些后还剩几个，那么任意时刻都要保证 $B_i \ge 0$。预留 $x$ 个下标大于等于 $i$ 的数就相当于给 $B_1, B_2, \cdots, B_i$ 减去 $x$。查询某个点的最大权值就相当于查询最大的权值 $x$，使得它所在的下标 $i$ 满足 $B_1, B_2, \cdots, B_i \ge \text{size}(v)$（容易发现选的 $i$ 越小越好）。用线段树维护两种操作即可，时间复杂度 $O(n \log n)$。

代码实现

实现的时候注意第二种操作中在权值最大的情况下选的下标必须最小，我们可以开一个 $\text{cnt}$ 数组来 $O(1)$ 完成这个操作。具体见代码。

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
//「SHOI 2018」IIIDX
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define ls (x << 1)
#define rs (ls | 1)
#define mid ((l + r) / 2)
const int maxn = 5e5, maxm = 1 << 20;
int n, sz[maxn + 3], fa[maxn + 3], a[maxn + 3], ans[maxn + 3];
int cnt[maxn + 3], mn[maxm + 3], tag[maxm + 3];
bool vis[maxn + 3];
double k;
vector<int> G[maxn + 3];

void dfs(int u) {
    sz[u] = 1;
    for (int i = 0, v; i < G[u].size(); i++) {
        v = G[u][i], fa[v] = u;
        dfs(v), sz[u] += sz[v];
    }
}

void maintain(int x) {
    mn[x] = min(mn[ls], mn[rs]);
}

void build(int x, int l, int r) {
    if (l == r) return mn[x] = n - l + 1, void();
    build(ls, l, mid), build(rs, mid + 1, r);
    maintain(x);
}

void push_down(int x) {
    mn[ls] += tag[x], tag[ls] += tag[x];
    mn[rs] += tag[x], tag[rs] += tag[x];
    tag[x] = 0;
}

void modify(int x, int l, int r, int lx, int rx, int y) {
    if (l >= lx && r <= rx) return mn[x] += y, tag[x] += y, void();
    push_down(x);
    if (lx <= mid) modify(ls, l, mid, lx, rx, y);
    if (rx > mid) modify(rs, mid + 1, r, lx, rx, y);
    maintain(x);
}

int query(int x, int l, int r, int y) {
    if (l == r) return y > mn[x] ? l - 1 : l;
    push_down(x);
    if (y > mn[ls]) return query(ls, l, mid, y);
    else return query(rs, mid + 1, r, y);
}

int main() {
    scanf("%d %lf", &n, &k);
    for (int i = 1; i <= n; i++) {
        G[int(i / k)].push_back(i);
    }
    dfs(0);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    for (int i = 2; i <= n; i++) {
        cnt[i] = a[i] == a[i - 1] ? cnt[i - 1] + 1 : 0;
    }
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        if (fa[i] && !vis[fa[i]]) vis[fa[i]] = true, modify(1, 1, n, 1, ans[fa[i]], sz[fa[i]] - 1);
        ans[i] = query(1, 1, n, sz[i]);
        ans[i] -= cnt[ans[i]], ans[i] += cnt[ans[i]]++;
        modify(1, 1, n, 1, ans[i], -sz[i]);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", a[ans[i]], " \n"[i == n]);
    }
    return 0;
}

「Day 2 / Task 1」劈配

思路分析

先考虑求解第一问。将每位选手依次考虑，每次选出可行的最高志愿的导师。考虑二分图匹配，如果匹配的导师还未满员，那么选他一定可行。否则考虑该导师是否有一个学生能够在他已经确定的最高志愿栏目中选出一个其他老师，使得这个方案可行。这个算法十分类似二分图匹配算法。

接下来考虑第二问。发现答案有单调性，可以二分。每次 $\text{check(id, rank)}$ 时我们一定会取出前 $\text{rank} - 1$ 个人匹配好的结果，然后把 $\text{id}$ 插入进去。我们可以记录前 $i$ 个人劈配好的结果 $(0 \le i < n)$，就可以快速地进行一次二分。

第一问的时间复杂度 $O(T n^2 C)$，第二问的时间复杂度 $O(T n^2 C \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
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
//「SHOI 2018」Matching
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 200;
bool vis[maxn + 3];
int T, n, m, b[maxn + 3], a[maxn + 3][maxn + 3], s[maxn + 3];
int res[maxn + 3], ans[maxn + 3];
vector<int> G[maxn + 3][maxn + 3], lnk[maxn + 3], hist[maxn + 3][maxn + 3];

bool match(int id, int lv) {
    for (int i = 0, x; i < G[id][lv].size(); i++) {
        x = G[id][lv][i];
        if (vis[x]) continue;
        vis[x] = true;
        if (lnk[x].size() < b[x]) {
            lnk[x].push_back(id);
            return true;
        }
        for (int j = 0, y; j < lnk[x].size(); j++) {
            y = lnk[x][j];
            if (match(y, a[y][x])) {
                lnk[x][j] = id;
                return true;
            }
        }
    }
    return false;
}

bool check(int id, int low) {
    for (int i = 1; i <= m; i++) {
        lnk[i] = hist[low][i];
    }
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= s[id]; i++) {
        if (match(id, i)) return true;
    }
    return false;
}

int main() {
    scanf("%d %*d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= m; i++) {
            scanf("%d", &b[i]);
            lnk[i].clear();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                G[i][j].clear();
            }
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
                if (a[i][j]) G[i][a[i][j]].push_back(j);
            }
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &s[i]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                hist[i][j] = lnk[j];
            }
            memset(vis, false, sizeof(vis));
            res[i] = 1;
            for (int j = 1; j <= m; j++) {
                if (match(i, j)) break;
                res[i]++;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (res[i] <= s[i]) {
                ans[i] = 0;
                continue;
            }
            int l = 0, r = i - 1, mid;
            while (l < r) {
                mid = (l + r + 1) / 2;
                if (check(i, mid)) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            ans[i] = i - l;
        }
        for (int i = 1; i <= n; i++) {
            printf("%d%c", res[i], " \n"[i == n]);
        }
        for (int i = 1; i <= n; i++) {
            printf("%d%c", ans[i], " \n"[i == n]);
        }
    }
    return 0;
}

「Day 2 / Task 2」林克卡特树

思路分析

首先将题目转化为最大化 $k + 1$ 条不相交的链的最大权值和。先考虑 $k \le 100$ 的子任务。令 $\text{dp}(u, i, d \in \{0, 1, 2\})$ 表示 $u$ 点的子树中选了 $i$ 条链，$u$ 的度数为 $d$ 的最优解。转移如下：

时间复杂度 $O(nk)$。

接下来考虑原题，发现如果在平面直角坐标系中画出 $\left( 1, \text{dp}(1, 1, 0) \right), \left( 2, \text{dp}(1, 2, 0) \right), \cdots$，这些点就会形成一个上凸的函数。于是考虑 $\text{wqs}$ 二分，每次给每条边加上一个值 $v$。令 $\text{dp}(u, d \in \{0, 1, 2\})$ 表示在边权修改后的树上，$u$ 的度数为 $d$ 的最优解。一次 $\text{dp}$ 时间复杂度 $O(n)$，套上二分后总时间复杂度 $O(n \log v)$。

代码实现

细节较多，具体见代码。

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
//「SHOI 2018」LCT
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

struct state {
    ll x; int y;
    void clear() { x = 0, y = 0; }
    friend bool operator< (const state &a, const state &b) { return a.x == b.x ? a.y > b.y : a.x < b.x; }
    friend state operator+ (const state &a, const state &b) { return { a.x + b.x, a.y + b.y }; }
    friend state operator+ (const state &a, const int &b) { return { a.x + b, a.y }; }
};

const int maxn = 3e5, maxm = 2 * maxn;
const ll lim = 1ll * maxn * 1e6 + 1, inf = 1ll * maxn * maxn * 1e6 + 1;
int n, k, tot, ter[maxm + 3], wei[maxm + 3], nxt[maxm + 3], lnk[maxn + 3];
state dp[maxn + 3][3];

void add_edge(int u, int v, int w) {
    ter[++tot] = v, wei[tot] = w;
    nxt[tot] = lnk[u], lnk[u] = tot;
}

state new_chain(state a, ll val) {
    return { a.x - val, a.y + 1 };
}

void dfs(int u, ll val, int pa = 0) {
    for (int i = 0; i < 3; i++) dp[u][i].clear();
    dp[u][2] = max(dp[u][2], { -inf, 1 });
    for (int i = lnk[u], v, w; i; i = nxt[i]) {
        v = ter[i], w = wei[i];
        if (v == pa) continue;
        dfs(v, val, u);
        dp[u][2] = max(dp[u][2] + dp[v][0], new_chain(dp[u][1] + dp[v][1] + w, val));
        dp[u][1] = max(dp[u][1] + dp[v][0], dp[u][0] + dp[v][1] + w);
        dp[u][0] = dp[u][0] + dp[v][0];
    }
    dp[u][0] = max(dp[u][0], max(new_chain(dp[u][1], val), dp[u][2]));
}

int main() {
    scanf("%d %d", &n, &k), k++;
    for (int i = 1, u, v, w; i < n; i++) {
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w), add_edge(v, u, w);
    }
    ll l = -lim, r = lim;
    while (l < r) {
        ll mid = (l + r + lim * 2) / 2 - lim;
        dfs(1, mid);
        if (dp[1][0].y <= k) r = mid;
        else l = mid + 1;
    }
    dfs(1, l);
    state ans = dp[1][0];
    printf("%lld\n", ans.x + k * l);
    return 0;
}