AHOI / HNOI 2018 大赏

2020-03-14

其实不想再写 18 年的题了… 再写就没时间写 19 年的了 (

果然立 flag 就是用来倒的.

话说这套题单看正解, 还挺考验思维的?

其实写不写都不重要了.

「AHOI / HNOI2018」寻宝游戏

挺有意思的一道题.

题目链接

解题思路

先祭上官方题解: http://matthew99.blog.uoj.ac/blog/3488.

着重解释一下什么是 “容易证明, 第 $i$ 位的结果为 $1$, 当且仅当 $x<b_i$.”

首先根据 myy 的题解, 构造出长度为 $n$ 的串 $x$, 以及 $m$ 个长度为 $n$ 的串 $b_i$.

对于二进制下某一位的值, 此时对这一位 | 0 或者 & 1, 并不会对原来的该位上的值造成影响. 那么, 如果第 $i$ 位为 1, 那么在一次形如 & 0 的操作后, 一定存在操作 & 1.

也就是说, 如果把左边看作低位, 那么 $x$ 形如 ...1...0..., $b_i$ 形如 ...0...1.... 换句话说, $x < b_i$.

大体思路就是这样了, 也不知道考场 AC 的 “逆推” 做法是什么样的. 还有一些值得注意的细节, 也在代码里了.

由于使用了基数排序, 时间复杂度 $O(nm + mq)$.

代码实现

> 点击显示 / 隐藏 
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
// LOJ #2494
// DeP
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1e3 + 5, MAXM = 5e5 + 5, P = 1e9 + 7;

int n, m, q;
char S[MAXM];
int idx[MAXM], pos[MAXM], A[MAXM];
int pow2[MAXN], val[MAXM], Ans[MAXM];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d%d%d", &n, &m, &q);
    // solve
    pow2[0] = 1;
    for (int i = 1; i <= n; ++i) pow2[i] = 2LL * pow2[i-1] % P;
    for (int i = 1; i <= m; ++i) A[i] = i;
    for (int i = 1; i <= n; ++i) {
        static int c[2];
        scanf("%s", S+1);
        // 字符集为 2 的基数排序相当清爽啊
        c[0] = 0, c[1] = m;
        for (int j = 1; j <= m; ++j)
            if (S[j] == '1') val[j] = (val[j] + pow2[i - 1]) % P; else ++c[0];
        for (int j = m; j; --j) idx[c[S[A[j]] - '0']--] = A[j];
        memcpy(A, idx, (m + 1) * sizeof (int));
    }
    for (int i = 1; i <= m; ++i) Ans[i] = val[A[i]];
    Ans[m + 1] = pow2[n];
    // output
    while (q--) {
        scanf("%s", S+1);
        int L = 0, R = m + 1;
        for (int i = m; i >= 1; --i) if (S[A[i]] == '0') { L = i; break; }
        for (int i = 1; i <= m; ++i) if (S[A[i]] == '1') { R = i; break; }
        printf("%d\n", L < R? (Ans[R] - Ans[L] + P) % P: 0);
    }
    return 0;
}

「AHOI / HNOI2018」转盘

题目链接

解题思路

将选择物品这个过程的顺序倒过来, 也就是在某个时刻 $t$, 从位置 $i$ 开始先前移动, 每个物品在时刻 $T_j$ 消失, 需要在每个物品消失前到达该物品的位置.

此时容易看出, 选择好位置和时刻之后, 一刻不停地走才能得到当前状态下的最优解. 本题做法就此展开.

首先将出现时刻序列 $T_i$ 倍长, 记当前出发位置为 $i$ ($i \in [n, 2n)$), 当前时刻为 $t$, 则标记所有物品的限制可以表示为

即

记 $a_j = T_j - j$, 那么答案为

对 $i$ 进行一些变换, 得

考虑到 $i \le j < i + n$ 这个限制又臭又长, 因为 $a_i = T_i - i > a_{i + n} = T_{i + n} - (i + n) = T_i - i - n$, 所以此时的 $a_j$ 就是个后缀最大值, 即

考虑某一个位置 $j$, 令 $j$ 满足 $a_j$ 为后缀最大值, 那么从 $j-1$ 往前找到第一个满足 $a_i > a_j$ 的位置 $i$, 此时答案为 $a_j + i + 1$.

如果此时 $a_j$ 不是后缀最大值, 那么答案和后缀最大值的情况相同.

就此我们得到了一个单调栈做法, 即维护一个 $a_j$ 值从右到左单调上升的栈, 并设栈中元素为 $p_i$, 令 $p_0 = 0$, 答案即为

利用线段树维护这个单调栈即可. 还是由于 $a_i = T_i - i, a_{i + n} = T_{i + n} - i - n$, 此时只需要维护 $[1, n]$ 即可.

类似的技巧也在 Luogu P4198 楼房重建 中使用过.

时间复杂度 $O(n \log ^2 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
// LOJ #2495
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 1e5 + 5, INF = 0x3f3f3f3f;

int n, m, p;
int A[MAXN];

namespace SGT {
#define lc (nd<<1)
#define rc (nd<<1|1)
    int datMax[MAXN << 2], dat[MAXN << 2];

    int Qry(int nd, int L, int R, const int& k) {
        if (L == R) return datMax[nd] > k? k + L: INF;
        int Mid = (L + R) / 2;
        if (k < datMax[rc]) return min(dat[nd], Qry(rc, Mid+1, R, k));
        return Qry(lc, L, Mid, k);
    }

    inline void maintain(int nd, const int& L, const int& R) {
        int Mid = (L + R) / 2;
        datMax[nd] = max(datMax[lc], datMax[rc]);
        dat[nd] = Qry(lc, L, Mid, datMax[rc]);
        // 用右子树的最大值在左子树中查询, 以更新答案
    }

    void build(int nd, int L, int R) {
        if (L == R) return void( datMax[nd] = A[L] - L );
        int Mid = (L + R) / 2;
        build(lc, L, Mid), build(rc, Mid+1, R);
        maintain(nd, L, R);
    }

    void Mdy(int nd, int L, int R, const int& pos, const int& val) {
        if (L == R) return void( datMax[nd] = val - L );
        int Mid = (L + R) / 2;
        if (pos <= Mid) Mdy(lc, L, Mid, pos, val);
        else Mdy(rc, Mid+1, R, pos, val);
        maintain(nd, L, R);
    }
#undef lc
#undef rc
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m), read(p);
    for (int i = 1; i <= n; ++i) read(A[i]);
    // solve
    SGT::build(1, 1, n);
    // output
    int x, y, lstans = SGT::Qry(1, 1, n, SGT::datMax[1] - n) + n;
    printf("%d\n", lstans);
    while (m--) {
        read(x), read(y);
        x ^= p * lstans, y ^= p * lstans;
        SGT::Mdy(1, 1, n, x, y);
        printf("%d\n", lstans = SGT::Qry(1, 1, n, SGT::datMax[1] - n) + n);
    }
    return 0;
}

「AHOI / HNOI2018」毒瘤

毒瘤.

题目链接

解题思路

首先考虑树的情况下怎么做.

设 $f(i, j)$ 表示以节点 $i$ 为根的子树内, 第 $i$ 个点选 ($j = 1$) / 不选 ($j = 0$) 时的方案数, 容易得到转移

观察到 $n - 1 \le m \le n + 10$ 的限制, 可以得到一个 $O(n 2 ^ {m - n + 1})$, 即依次枚举非树边的选择情况, 以此为限制修改 DP 初始值, 每次都做一次整棵树的 DP.

此时仍有优化的余地, 考虑到非树边很少, 影响到的点很少, 可以对这些点建出虚树, 并在虚树上 DP.

具体地说, 考虑虚树上一条边 $(u, v)$, 其在树边上路径为 $k_1, k_2, \ldots, k_n$ (其中 $k_1 = u$, $k_n = v$), 此时 $v$ 对 $u$ 的答案有贡献. 即

手动展开之后式子有些复杂… 冷静一下可以发现, 其中的系数都是一样的, 直接按照定义预处理出来就好了.

记 $k(u, i, j)$ 表示节点 $u$, 由状态 $i$ 到达状态 $j$, DP 转移时的系数. 则虚树边上的转移可写作

还应注意到, 虚树上 DP 的初始值并不是 $1$ —- 而是原树上, 子树内不包含虚树上结点的 DP 值.

考虑为什么是这样. 如果原树某个节点, 其子树包含有虚数上节点, 那么此时原树上的答案已经在计算系数的过程中贡献到最终答案了. 因而只考虑子树内不包含虚树上节点的部分即可.

时间复杂度 $O(n + (m-n+1) 2 ^ {m - n + 1})$.

代码实现

实际为了缓存友好, DP 状态的顺序稍有改变.

> 点击显示 / 隐藏 
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
// LOJ #2496
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 1e5 + 114, P = 998244353;

int n, m;
int U[MAXN], V[MAXN], nE;

bool vis[MAXN];
int pre[MAXN], dfn[MAXN], A[MAXN], nA;
int f[2][MAXN], g[2][MAXN], K[2][2][MAXN];

struct Edge { int nxt, to; };
struct Graph {
    int head[MAXN], eidx;
    Edge edges[MAXN << 1];

    Graph() { init(); }
    inline void init() { memset(head, -1, sizeof head), eidx = 1; }

    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
    }
} G, T;

namespace HLD {
    int son[MAXN], depth[MAXN], size[MAXN], topfa[MAXN], dfs_clock;

    void dfs1(int u, int fa) {
        pre[u] = fa, size[u] = 1, son[u] = -1;
        dfn[u] = ++dfs_clock, depth[u] = depth[fa] + 1;
        for (int v, i = G.head[u]; ~i; i = G.edges[i].nxt) {
            if ((v = G.edges[i].to) == fa) continue;
            if (!dfn[v]) {
                dfs1(v, u), size[u] += size[v];
                if (son[u] == -1 || size[son[u]] < size[v]) son[u] = v;
            } else if (dfn[v] < dfn[u])
                U[++nE] = v, V[nE] = u, vis[u] = vis[v] = true;
        }
    }

    void dfs2(int u, int top) {
        topfa[u] = top;
        if (~son[u]) dfs2(son[u], top), vis[u] |= vis[son[u]];
        for (int v, i = G.head[u]; ~i; i = G.edges[i].nxt)
            if ((v = G.edges[i].to) != pre[u] && v != son[u])
                dfs2(v, v), vis[u] |= vis[v];
    }

    inline int LCA(int u, int v) {
        while (topfa[u] != topfa[v]) {
            if (depth[topfa[u]] < depth[topfa[v]]) swap(u, v);
            u = pre[topfa[u]];
        }
        return depth[u] > depth[v]? v: u;
    }

    inline void solve() {
        dfs1(1, 0), G.init();
        for (int i = 1; i <= n; ++i) if (pre[i]) G.AddEdge(pre[i], i);
        dfs2(1, 1);
    }
}

namespace VT {
    inline bool cmp(const int& a, const int& b) { return dfn[a] < dfn[b]; }

    void build() {
        static int stk[MAXN], top;
        for (int i = 1; i <= nE; ++i) A[++nA] = U[i], A[++nA] = V[i];
        sort(A+1, A+1+nA, cmp);
        stk[top = 1] = 1;
        for (int i = 1; i <= nA; ++i) if (A[i] != 1) {
            if (A[i] == stk[top]) continue;
            int lca = HLD::LCA(A[i], stk[top]);
            if (lca != stk[top]) {
                while (top > 1 && dfn[lca] < dfn[stk[top-1]])
                    T.AddEdge(stk[top-1], stk[top]), --top;
                if (top > 1 && dfn[lca] > dfn[stk[top-1]])
                    T.AddEdge(lca, stk[top]), stk[top] = lca;
                else T.AddEdge(lca, stk[top--]);
            }
            stk[++top] = A[i];
        }
        for (int i = 1; i < top; ++i) T.AddEdge(stk[i], stk[i + 1]);
    }

    // 在原树上 DP, 辅助计算系数
    void DP(int u, const int& ban) {
        f[0][u] = f[1][u] = 1;
        for (int v, i = G.head[u]; ~i; i = G.edges[i].nxt) {
            if ((v = G.edges[i].to) == ban || v == pre[u]) continue;
            DP(v, u);
            f[1][u] = 1LL * f[1][u] * f[0][v] % P;
            f[0][u] = 1LL * f[0][u] * (f[0][v] + f[1][v]) % P;
        }
    }

    // 计算 DP 初始值 g
    void DPinit(int u, int fa) {
        g[0][u] = g[1][u] = 1;
        for (int v, i = G.head[u]; ~i; i = G.edges[i].nxt) {
            if ((v = G.edges[i].to) == fa || vis[v]) continue;
            DPinit(v, u);
            g[1][u] = 1LL * g[1][u] * g[0][v] % P;
            g[0][u] = 1LL * g[0][u] * (g[0][v] + g[1][v]) % P;
        }
    }

    // 计算系数
    void Jump(int u, const int& fa) {
        K[0][0][u] = K[0][1][u] = K[1][0][u] = 1;
        for (int i = u; pre[i] != fa; i = pre[i]) {
            DP(pre[i], i);
            int ft = pre[i], k0 = K[0][0][u], k1 = K[0][1][u];
            K[0][0][u] = (1LL * f[0][ft] * k0 % P + 1LL * f[1][ft] * K[1][0][u] % P) % P;
            K[0][1][u] = (1LL * f[0][ft] * k1 % P + 1LL * f[1][ft] * K[1][1][u] % P) % P;
            K[1][1][u] = 1LL * f[0][ft] * k1 % P;
            K[1][0][u] = 1LL * f[0][ft] * k0 % P;
        }
    }

    // 在虚树上 DFS 以初始化
    void init(int u, int fa) {
        A[++nA] = u, DPinit(u, fa);
        if (fa && u != fa) Jump(u, fa);
        for (int v, i = T.head[u]; ~i; i = T.edges[i].nxt)
            if ((v = T.edges[i].to) != fa) init(v, u);
    }

    inline void solve() { build(), nA = 0, init(1, 0); }

    // 虚树上 DP
    void dfs(int u, int fa) {
        for (int v, i = T.head[u]; ~i; i = T.edges[i].nxt) {
            if ((v = T.edges[i].to) == fa) continue;
            dfs(v, u);
            f[0][u] = 1LL * f[0][u] *
                (1LL * K[0][0][v] * f[0][v] % P + 1LL * K[0][1][v] * f[1][v] % P) % P;
            f[1][u] = 1LL * f[1][u] *
                (1LL * K[1][0][v] * f[0][v] % P + 1LL * K[1][1][v] * f[1][v] % P) % P;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m);
    for (int u, v, i = 1; i <= m; ++i)
        read(u), read(v), G.AddEdge(u, v), G.AddEdge(v, u);
    // solve
    HLD::solve(), VT::solve();
    int ans = 0;
    for (int s = 0; s < (1 << nE); ++s) {
        for (int i = 1; i <= nA; ++i)
            f[0][A[i]] = g[0][A[i]], f[1][A[i]] = g[1][A[i]];
        for (int i = 1; i <= nE; ++i)
            if ((s >> (i-1)) & 1) f[0][U[i]] = f[1][V[i]] = 0; else f[1][U[i]] = 0;
        VT::dfs(1, 0), ans = (ans + (f[0][1] + f[1][1]) % P) % P;
    }
    // output
    printf("%d\n", ans);
    return 0;
}

「AHOI / HNOI2018」游戏

题目链接

解题思路

首先将房间按上锁的门分割, 处理出房间 $i$ 能到达的房间位置 $[L_i, R_i]$. 这样判断 $s$ 是否能到达 $t$, 只需要判断 $t$ 是否在区间 $[L_i, R_i]$ 就好了.

有一个显然的暴力, 对于每个位置向左右两个方向扩展, 并逐步更新 $L_i$ / $R_i$.

思考如何优化这个暴力. 考虑到对每个位置扩展时, 很多状态被计算了多次. 而题目中钥匙放置位置, 又存在这样的性质:

  1. 如果房间 $i$ 和房间 $i+1$ 存在锁, 且钥匙在房间 $i$ 左侧 (包含 $i$), 那么房间 $i+1$ 之后的位置一定不能越过这扇门.

  2. 如果房间 $i$ 和房间 $i+1$ 存在锁, 且钥匙在房间 $i+1$ 右侧 (包含 $i+1$), 那么房间 $i$ 之前的位置一定不能越过这扇门.

每次遇到一个锁时, 将一个位置向该位置不能到达的地方连边, 建完边后可以得到一个 DAG, 在拓扑排序时更新可到达位置区间即可.

实际实现时, 直接使用按锁分割后的编号, 也就是所谓 “缩点” 了.

虽然拓扑排序更新到达位置区间 $[L_i, R_i]$ 时的复杂度看起来很不对劲, 但其实均摊是线性的… 这也是建图方法所保证的.

时间复杂度 $O(n + m)$.

代码实现

> 点击显示 / 隐藏 
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
// LOJ #2508
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 1e6 + 5;

int n, m, q;
int L[MAXN], R[MAXN];
int Key[MAXN], Idx[MAXN], idx;

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXN];
    int head[MAXN], in[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
        ++in[to];
    }

    void Toposort() {
        static queue<int> Q;
        for (int i = 1; i <= idx; ++i) if (!in[i]) Q.push(i);
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            bool flag = true;
            while (flag) {
                flag = false;
                int p1 = Key[L[u] - 1], p2 = Key[R[u]];
                while (L[u] <= p1 && p1 <= R[u])
                    flag = true, L[u] = L[Idx[L[u] - 1]], p1 = Key[L[u] - 1];
                while (L[u] <= p2 && p2 <= R[u])
                    flag = true, R[u] = R[Idx[R[u] + 1]], p2 = Key[R[u]];
            }
            for (int v, i = head[u]; ~i; i = edges[i].nxt)
                if (!(--in[v = edges[i].to])) Q.push(v);
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init();
    // input
    read(n), read(m), read(q);
    for (int x, i = 1; i <= m; ++i) read(x), read(Key[x]);
    // solve
    L[1] = R[1] = idx = 1;
    for (int i = 2; i <= n; ++i) {
        if (Key[i - 1] != 0) {
            L[++idx] = i;
            if (Key[i - 1] <= i - 1) Graph::AddEdge(idx, idx - 1);
            else Graph::AddEdge(idx - 1, idx);
        }
        R[idx] = i;
    }
    // 记 Idx[i] 为实际房间标号 i, 对应按锁分割后块的编号
    for (int i = 1; i <= idx; ++i)
        for (int j = L[i]; j <= R[i]; ++j) Idx[j] = i;
    Graph::Toposort();
    // output
    while (q--) {
        static int s, t;
        read(s), read(t);
        puts((L[Idx[s]] <= t && t <= R[Idx[s]])? "YES": "NO");
    }
    return 0;
}

「AHOI / HNOI2018」排列

题目链接

解题思路

考虑题目中这个很奇怪的限制在说什么.

既然满足 “如果 $a_{p_j} = p_k$, 那么 $k < j$”, 换句话说, 如果增量构造出这个排列, 在选择 $j$ 时, 一定要先选 $a_j$.

此时将 $a_j$ 向 $j$ 连边, 如果形成环则一定无解, 否则就是一颗以 $0$ 为根的树.

考虑如何构造出最优解, 可以发现, 权值都是固定的, 要做的事就是在合法的范围内, 将尽量大的 $w_i$ 放在后面.

于是可以得到一个贪心策略. 首先找到当前权值最小的位置 $p$, 如果 $p$ 在树上没有父亲, 也就是 $a_p = 0$, 此时一定选择 $p$; 否则在选择 $a_p$ 后立刻选择 $p$.

因此可以将 $p$ 和 $a_p$ 合并, 具体而言, 每次取出最小值, 更新信息并利用并查集合并即可.

剩余的问题就是如何找到这个最小值了. 考虑到合并一些节点之后, 得到的就是一个序列. 假有两个序列 $a$, $b$, 记两个序列的权值分别为 $W_a$, $W_b$, 那么

考虑两序列拼接的两种方式, 即

若选择 $ab$ 的形式使得答案更大, 那么有 $W_{ab} > W_{ba}$, 即

于是万事大吉.

时间复杂度 $O(n \log n)$.

代码实现

如果考虑节点 $0$ 在计算答案时的影响, 则需要把 W[0] 设为 INF, 但是这个 INF 太大爆 long long (虽然不影响结果), 太小会 WA = =

那就直接不考虑吧 (

> 点击显示 / 隐藏 
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
// LOJ #2509
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 5e5 + 5;

struct Item {
    int u, s; LL w;
    Item(int _u, int _s, LL _w): u(_u), s(_s), w(_w) { }
    bool operator < (const Item& rhs) const {
        return w * rhs.s > rhs.w * s;
    }
};

int n;
int A[MAXN], size[MAXN];
LL W[MAXN];
priority_queue<Item> Q;

namespace DSU {
    int fa[MAXN];

    inline void init() {
        for (int i = 0; i <= n; ++i) fa[i] = i, size[i] = 1;
    }
    inline int findfa(int u) { return u == fa[u]? u: fa[u] = findfa(fa[u]); }
}

inline void NoAns() { puts("-1"), exit(0); }

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXN];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
    }

    int dfs(int u, int fa) {
        static bool vis[MAXN];
        int s = vis[u] = 1;
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            if ((v = edges[i].to) == fa) continue;
            if (vis[v]) NoAns();
            s += dfs(v, u);
        }
        return s;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init();
    // input
    read(n);
    for (int i = 1; i <= n; ++i) read(A[i]);
    for (int i = 1; i <= n; ++i) read(W[i]);
    // solve
    for (int i = 1; i <= n; ++i) Graph::AddEdge(A[i], i);
    if (Graph::dfs(0, -1) != n + 1) NoAns();
    DSU::init();
    for (int i = 1; i <= n; ++i) Q.push(Item(i, size[i], W[i]));
    LL ans = 0;
    while (!Q.empty()) {
        Item x = Q.top(); Q.pop();
        int u = DSU::findfa(x.u), fa = DSU::findfa(A[u]);
        if (size[u] != x.s) continue;
        ans += W[u] * size[fa];
        DSU::fa[u] = fa, W[fa] += W[u], size[fa] += size[u];
        if (fa) Q.push(Item(fa, size[fa], W[fa]));
    }
    // output
    printf("%lld\n", ans);
    return 0;
}

「AHOI / HNOI2018」道路

这是一道 NOIP 题…

题目链接

解题思路

观察式子

可以发现, 这个式子没有用.

题目给定的其实是一颗以 $1$ 为根, 共 $2n - 1$ 个节点的二叉树, 叶节点都是乡村. 并钦定连向左儿子的边为公路, 连向右儿子的边为铁路.

设 $f(u, i, j)$ 表示节点 $u$, 其到根节点共经过 $i$ 条公路, $j$ 条铁路. 则

对于叶子 $u$, 有

对于其他节点 $u$, 记 $u$ 左儿子为 $lc$, 右儿子为 $rc$, 有转移

答案即为 $f(1, 0, 0)$.

以及一个卡空间的方法. 考虑到每次计算 $f(u, i, j)$ 时, 只是利用了一条链, 不相交的链之间不会互相影响, 若记二叉树最大深度为 $h$, 第一维只需记录 $2h$ 位即可.

时间复杂度 $O(h ^ 2 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
// LOJ #2510
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 4e4 + 5, MAXH = 41;

int n;
int A[MAXN], B[MAXN], C[MAXN];
int ch[2][(MAXN >> 1) | 1], dfn[MAXN];
LL f[MAXH][MAXH][(MAXH << 1) | 1];

void dfs(int u, int clk, int x, int y) {
    int du = dfn[u] = clk;
    if (u >= n) {
        for (int i = 0; i <= x; ++i)
            for (int j = 0; j <= y; ++j)
                f[i][j][du] = 1LL * C[u] * (A[u] + i) * (B[u] + j);
        return;
    }
    // 假装自己在下传 DFS 序.png
    dfs(ch[0][u], clk + 1, x + 1, y), dfs(ch[1][u], clk + 2, x, y + 1);
    int d1 = dfn[ch[0][u]], d2 = dfn[ch[1][u]];
    for (int i = 0; i <= x; ++i)
        for (int j = 0; j <= y; ++j)
            f[i][j][du] = min(f[i + 1][j][d1] + f[i][j][d2], f[i][j][d1] + f[i][j + 1][d2]);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n);
    for (int u, v, i = 1; i < n; ++i) {
        read(u), read(v);
        ch[0][i] = u < 0? -u + n - 1: u, ch[1][i] = v < 0? -v + n - 1: v;
    }
    for (int i = n; i <= n + n-1; ++i) read(A[i]), read(B[i]), read(C[i]);
    // solve
    dfs(1, 1, 0, 0);
    // output
    printf("%lld\n", f[0][0][dfn[1]]);
    return 0;
}

后记

这周比上周少写了一整套 SDOI = =, 退役稳了.

© 2019-2023 DepletedPrism's Blog - Powered by Hexo - Theme Chan