Asusetic
0%

2021.04.20模拟赛

发表于 分类于 Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

很久之前的东西

2021.04.20 模拟赛

越来越菜

T1 越野赛车问题

题面

矩阵乘写挂也有五十()

虽然有线段树分治+并查集的解法，不过个人感觉DDP比较好想

其实题目就是说一个树每个边在 lil_i 出现 rir_i 消失，时刻 vv 的直径

DDP的话

设 dpx,1dp_{x,1} 表示 xx 的子树内直径长度，dpx,0dp_{x,0} 表示起点为 xx 的最长链

dpx,1=max⁡max⁡y∈son(x)dpy,1,max⁡y,z∈son(x)dpy,0+dpz,0dp_{x,1}=\max\\{\max\limits_{y\in son(x)}dp_{y,1},\max\limits_{y,z \in son(x)}dp_{y,0}+dp_{z,0}\\}

dpx,0=max⁡y∈son(x)dpy,0+1dp_{x,0}=\max\limits_{y\in son(x)}\\{dp_{y,0}\\}+1

DDP套路，设

gx,0=max⁡y∈light(x)dpy,0g_{x,0}=\max\limits_{y\in light(x)}dp_{y,0}
gx,1=max⁡max⁡y∈light(x)dpy,1,max⁡y,z∈light(x)dpy,0+dpz,0g_{x,1}=\max\\{\max\limits_{y\in light(x)}dp_{y,1},\max\limits_{y,z\in light(x)}dp_{y,0}+dp_{z,0}\\}

于是

dpx,0=max⁡gx,0+dpson,0+1dp_{x,0}=\max\\{g_{x,0}+dp_{son,0}\\}+1
dpx,1=max⁡dpson,1,gx,1,dpson,0+gx,0dp_{x,1}=\max\\{dp_{son,1},g_{x,1},dp_{son,0}+g_{x,0}\\}

转移为
[1−∞gx,0+1gx,00gx,1−∞−∞0][dpson,0dpson,10]=[dpx,0dpx,10]\begin{bmatrix}\begin{array}{c}1 & -\infty & g_{x,0}+1\\\\g_{x,0} & 0 &g_{x,1}\\\\-\infty & -\infty & 0\end{array}\end{bmatrix}\begin{bmatrix}\begin{array}{c}dp_{son,0}\\\\dp_{son,1}\\\\0\end{array}\end{bmatrix}=\begin{bmatrix}\begin{array}{c}dp_{x,0}\\\\dp_{x,1}\\\\0\end{array}\end{bmatrix}

对于 gx,0/1g_{x,0/1}的维护需要开两个可删堆

一个记录 dpx,0dp_{x,0} 一个 dpx,1dp_{x,1}，都只维护轻儿子

gx,0g_{x,0} 是第一个里最大的

gx,1g_{x,1} 是第二个最大的或者第一个前两个数

复杂度O(nlog⁡2n)O(n\log^2n) LCT可优化为 O(nlog⁡n)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
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
using namespace std;
const int N = 70005;
int n, m;
int x[N], y[N];
struct DelHeap {
    priority_queue<int> q, p;
    void clear() {
        while (!q.empty() && !p.empty() && q.top() == p.top())
            q.pop(), p.pop();
    }
    void push(int x) {
        q.push(x);
        clear();
    }
    void pop() {
        q.pop();
        clear();
    }
    void del(int x) {
        p.push(x), clear();
    }
    int top() {
        clear();
        return q.top();
    }
    bool empty() {
        clear();
        return q.empty();
    }
};
struct Edge {
    int v, l, r;
    int nxt;
} edge[N * 2];
int head[N], ecnt;
void add(int u, int v, int l, int r) {
    edge[++ecnt].v = v;
    edge[ecnt].l   = l;
    edge[ecnt].r   = r;
    edge[ecnt].nxt = head[u];
    head[u]        = ecnt;
}
namespace DDP {
DelHeap q1[N], q2[N];
int leaf[N];
int g0(int x) {
    if (q1[x].empty()) {
        return 0;
    } else {
        return q1[x].top();
    }
}
int g1(int x) {
    int ans = q2[x].empty() ? 0 : q2[x].top();
    int sum = 0, tmp;
    if (q1[x].empty()) {
        return ans;
    }
    sum = q1[x].top();
    q1[x].pop();
    tmp = sum;
    if (!q1[x].empty()) {
        sum += q1[x].top();
    }
    q1[x].push(tmp);
    return max(sum, ans);
}
int top[N], fa[N], dep[N], son[N], siz[N], id[N], pos[N], tim;
void dfs1(int x, int f) {
    dep[x] = dep[f] + 1;
    fa[x]  = f;
    siz[x] = 1;
    for (int i = head[x]; i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v == f) {
            continue;
        }
        dfs1(v, x);
        siz[x] += siz[v];
        if (siz[v] > siz[son[x]]) {
            son[x] = v;
        }
    }
}
void dfs2(int x, int topf) {
    top[x]   = topf;
    id[x]    = ++tim;
    pos[tim] = x;
    if (!son[x]) {
        leaf[x] = x;
        return;
    }
    dfs2(son[x], topf);
    leaf[x] = leaf[son[x]];
    for (int i = head[x]; i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v == fa[x] || v == son[x]) {
            continue;
        }
        dfs2(v, v);
    }
}
struct Matrix {
    int a[3][3];
    Matrix() {
        memset(a, 0, sizeof(a));
    }
    int *operator[](int x) {
        return a[x];
    }
    Matrix operator*(Matrix b) {
        Matrix res = Matrix();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                res[i][j] = -(1 << 31);
            }
        }
        for (int i = 0; i < 3; i++) {
            for (int k = 0; k < 3; k++) {
                for (int j = 0; j < 3; j++) {
                    res[i][j] = max(res[i][j], a[i][k] + b[k][j]);
                }
            }
        }
        return res;
    }
};
int w[N];
namespace SegmentTree {
const int INF = (1 << 30);
Matrix tr[N * 4];
void init(int rt, int x) {
    tr[rt].a[1][0] = g0(x);
    tr[rt].a[1][1] = 0;
    tr[rt].a[1][2] = g1(x);
    tr[rt].a[2][0] = -INF;
    tr[rt].a[2][1] = -INF;
    tr[rt].a[2][2] = 0;
}
void build(int rt, int l, int r) {
    if (l == r) {
        tr[rt][0][0] = -INF;
        tr[rt][0][1] = -INF;
        tr[rt][0][2] = 0;
        init(rt, pos[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(rt * 2, l, mid);
    build(rt * 2 + 1, mid + 1, r);
    tr[rt] = tr[rt * 2] * tr[rt * 2 + 1];
}
Matrix query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return tr[rt];
    }
    int mid = (l + r) / 2;
    if (R <= mid) {
        return query(rt * 2, l, mid, L, R);
    }
    if (L > mid) {
        return query(rt * 2 + 1, mid + 1, r, L, R);
    }
    return query(rt * 2, l, mid, L, R) * query(rt * 2 + 1, mid + 1, r, L, R);
}
void update(int rt, int l, int r, int x) {
    if (l == r) {
        if (w[pos[l]]) {
            tr[rt][0][0] = 1;
            tr[rt][0][1] = -INF;
            tr[rt][0][2] = g0(pos[l]) + 1;
        } else {
            tr[rt][0][0] = -INF;
            tr[rt][0][1] = -INF;
            tr[rt][0][2] = 0;
        }
        init(rt, pos[l]);
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        update(rt * 2, l, mid, x);
    } else {
        update(rt * 2 + 1, mid + 1, r, x);
    }
    tr[rt] = tr[rt * 2] * tr[rt * 2 + 1];
}
} // namespace SegmentTree
Matrix query(int x) {
    return SegmentTree::query(1, 1, n, id[x], id[leaf[x]]) * Matrix();
}
void update(int x, int k) {
    w[x] = k;
    while (top[x] != 1) {
        Matrix tmp1 = query(top[x]);
        SegmentTree::update(1, 1, n, id[x]);
        Matrix tmp2 = query(top[x]);
        x           = fa[top[x]];
        q1[x].del(tmp1[0][0]);
        q1[x].push(tmp2[0][0]);
        q2[x].del(tmp1[1][0]);
        q2[x].push(tmp2[1][0]);
    }
    SegmentTree::update(1, 1, n, id[x]);
}
vector<int> p[N];
int ans[N];
void solve() {
    dfs1(1, 0);
    dfs2(1, 1);
    SegmentTree::build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        for (int j = head[i]; j; j = edge[j].nxt) {
            int v = edge[j].v;
            if (fa[i] == v) {
                p[edge[j].l].push_back(i);
                p[edge[j].r].push_back(-i);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (auto x : p[i]) {
            if (x > 0) {
                update(x, 1);
            }
        }
        ans[i] = query(1)[1][0];
        for (auto x : p[i]) {
            if (x < 0) {
                update(-x, 0);
            }
        }
    }
    while (m--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", ans[x]);
    }
}
} // namespace DDP
int main() {
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v, l, r;
        scanf("%d%d%d%d", &u, &v, &l, &r);
        add(u, v, l, r);
        add(v, u, l, r);
    }
    DDP::solve();
}
// Asusetic eru quionours

T2 方舟系统

题面

考虑朴素 dp : dpi=min⁡i<j≤n+1dpj+∣ai−(j−i−1)∣dp_i = \min\limits_{i<j\le n+1}\\{dp_j+|a_i-(j-i-1)|\\}

绝对值很难看，拆开

dpi =min⁡i<j≤n+1{dpj−j+(ai+i+1)ai+i+1≥jdpj+j−(ai+i+1)ai+i+1<jdp_i\ =\min\limits_{i< j\le n+1}\begin{cases} dp_j-j+(a_i+i+1)&a_i+i+1\ge j\\ dp_j+j-(a_i+i+1)&a_i+i+1< j \end{cases}

分别用树状数组/线段树维护两个区间最小值

复杂度 O(nlog⁡n)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
51
52
53
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100010;
int n, a[N];
int dp[N];
struct BIT {
    int c[N];
    BIT() {
        memset(c, 0x3f, sizeof(c));
    }
    int lowbit(int x) {
        return x & (-x);
    }
    void update(int pos, int v) {
        if (pos <= 0) {
            return;
        }
        while (pos <= n) {
            c[pos] = min(c[pos], v);
            pos += lowbit(pos);
        }
    }
    int query(int pos) {
        if (pos <= 0) {
            return (1 << 30);
        }
        int res = (1 << 30);
        while (pos) {
            res = min(res, c[pos]);
            pos -= lowbit(pos);
        }
        return res;
    }
} d1, d2;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dp[1] = a[1];
    d1.update(n - a[1], a[1] + 1);
    d2.update(a[1] + 1, -a[1] - 1);
    for (int i = 2; i <= n; i++) {
        int minv1 = d1.query(n - i + 1), minv2 = d2.query(i);
        dp[i] = min(minv1 - i, minv2 + i);
        d1.update(n - a[i] - i + 1, dp[i - 1] + a[i] + i);
        d2.update(a[i] + i, dp[i - 1] - a[i] - i);
    }
    cout << dp[n];
    return 0;
}

T3 椅子

题面

[原题]([AT2645 ARC076D] Exhausted? - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

大力贪心

如果仅有 lil_i 的限制显然很好做，贪心扫一遍

加上 rir_i 后需要反悔，替换的时候必然是把 rir_i 最小的扔出去，因为他能坐的位置更多

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
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 2e5 + 5;
int n, m, ans, qp[N], cnt;
struct Data {
    int l, r;
} a[N];
bool cmp(const Data &A, const Data &B) {
    if (A.l != B.l) {
        return A.l < B.l;
    }
    return A.r > B.r;
}
priority_queue<int, vector<int>, greater<int>> q;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + n + 1, cmp);
    int h = 1, t = m;
    for (int i = 1; i <= n; i++) {
        q.push(a[i].r);
        if (h <= t && h <= a[i].l) {
            h++;
        } else {
            qp[++cnt] = q.top();
            q.pop();
        }
    }
    sort(qp + 1, qp + cnt + 1);
    for (int i = cnt; i >= 1; i--) {
        if (h <= t && qp[i] <= t) {
            t--;
        } else {
            ans++;
        }
    }
    cout << ans;
}