首页 模拟赛

线段树分治 + 可撤销并查集动态维护直径，dp + 分块，贪心，dp + 树状数组

# A. 越野赛车问题

考虑对值域进行线段树分治，把在分治区间 [L,R][L, R] 的边连上，动态维护树的直径即可。

关于如何维护直径，就是把原来直径的两个端点和新加进来的边的两个端点组合一下，距离最远的两个点就是新的直径。

再开个可撤销并查集维护历史直径信息，就可以动态更新了。

直接贺板子，好耶。

codecode

#include <bits/stdc++.h>
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
#define fi first
#define se second
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 1e5 + 10;
int n, m;
struct node{
    int u, v;
}e[N];
vector <int> g[N], t[N << 2];
int fa[N], siz[N], son[N], dep[N];
inline void dfs1(int x, int f){
    fa[x] = f, siz[x] = 1, dep[x] = dep[f] + 1;
    for(auto y : g[x]){
        if(y == f) continue;
        dfs1(y, x), siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) son[x] = y;
    }
}
int top[N];
inline void dfs2(int x, int topfa){
    top[x] = topfa;
    if(son[x]) dfs2(son[x], topfa);
    for(auto y : g[x])
        if(y != fa[x] && y != son[x]) dfs2(y, y);
}
inline int lca(int x, int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[x];
    }
    return dep[x] < dep[y] ? x : y;
}
inline int dist(int x, int y){
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
struct Path{
    int p1, p2, dis;
    Path() {}
    Path(int _p1, int _p2) {p1 = _p1, p2 = _p2, dis = dist(p1, p2);}
    inline bool operator < (const Path &b) const {
        return dis < b.dis;
    }
    friend inline Path merge(Path x, Path y){
        Path p = max(x, y);
        p = max(p, max(Path(x.p1, y.p1), Path(x.p1, y.p2)));
        p = max(p, max(Path(x.p2, y.p1), Path(x.p2, y.p2)));
        return p;
    }
};
struct Dsu{
    Path p;
    int fa, siz;
}dsu[N];
struct Stack{
    int x, y;
    Path px, py;
    Stack() {}
    Stack(int _x, int _y, Path _px, Path _py){
        x = _x, y = _y, px = _px, py = _py;
    }
}stk[N];
int stop;
inline int find(int x){
    return dsu[x].fa == x ? x : find(dsu[x].fa);
}
inline int Union(int x, int y){
    x = find(x), y = find(y);
    if(dsu[x].siz < dsu[y].siz) swap(x, y);
    stk[++stop] = Stack(x, y, dsu[x].p, dsu[y].p);
    dsu[y].fa = x, dsu[x].siz += dsu[y].siz;
    dsu[x].p = merge(dsu[x].p, dsu[y].p);
    return dsu[x].p.dis;
}
inline void Delete(){
    Stack s = stk[stop--];
    int x = s.x, y = s.y;
    dsu[y].fa = y, dsu[x].siz -= dsu[y].siz;
    dsu[x].p = s.px, dsu[y].p = s.py;
}
int ans[N];
inline void update(int L, int R, int x, int l, int r, int rt){
    if(L > R || L > r || R < l) return;
    if(L <= l && r <= R) return t[rt].pb(x), void();
    update(L, R, x, l, mid, ls), update(L, R, x, mid + 1, r, rs);
}
inline void solve(int len, int l, int r, int rt){
    int now = stop;
    for(auto x : t[rt]) len = max(len, Union(e[x].u, e[x].v));
    if(l == r) ans[l] = ~ans[l] ? ans[l] : len;
    else solve(len, l, mid, ls), solve(len, mid + 1, r, rs);
    while(stop != now) Delete();
}
signed main(){
    n = read(), m = read();
    for(int i = 1; i < n; ++i){
        int u = read(), v = read(), l = read(), r = read();
        e[i] = (node){u, v}, update(l, r, i, 1, n, 1);
        g[u].pb(v), g[v].pb(u);
    }
    dfs1(1, 0), dfs2(1, 1);
    memset(ans, -1, sizeof(ans));
    for(int i = 1; i <= n; ++i) dsu[i] = (Dsu){Path(i, i), i, 1};
    solve(0, 1, n, 1);
    for(int i = 1; i <= m; ++i) write(ans[read()]), puts("");
    return 0;
}
# B. Native - DP II
CF101E Candies and Stones
非常显然的 dp\text{dp}，设 fi,jf_{i, j} 表示走到 i,ji, j 的最大收益，那么转移就是：
fi,j=max⁡{fi−1,j+fi,j−1+vali,j}f_{i, j} = \max\{f_{i - 1, j} + f_{i, j - 1} + val_{i, j} \}
但是这样空间复杂度是 O(nm)O(nm) 的，不知道比 43.95M\text{43.95M} 高了多少。
考虑如何优化空间。
我们把 n×mn \times m 的矩阵按行分块，即每处理 n\sqrt n 行存一下答案，记录 dp\text{dp} 值，以及路径。
最后再倒着枚举每一块跑一遍 dp\text{dp}，找路径。
codecode
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 2e4 + 10;
const int B = 150;
int n, m, mod, t, l = 1;
int x[N], y[N], f[B][N], g[B][N], df[B][N], dg[2][N];
int dir[2][N], dp[2][N];
stack <int> ans;
inline int add(int x) {return x >= mod ? x % mod : x;}
signed main(){
    n = read() - 1, m = read() - 1, mod = read(), t = max(sqrt(n), 1.0);
    for(int i = 0; i <= n; ++i) x[i] = read();
    for(int i = 0; i <= m; ++i) y[i] = read();
    for(int i = 0; i <= n; ++i, l ^= 1){
        memset(dir[l], 0, sizeof(dir[l]));
        memset(dp[l], 0, sizeof(dp[l]));
        for(int j = 0; j <= m; ++j){
            dp[l][j] = dp[l ^ 1][j] + add(x[i] + y[j]), dir[l][j] = 1;
            if(j && dp[l][j] < dp[l][j - 1] + add(x[i] + y[j]))
                dp[l][j] = dp[l][j - 1] + add(x[i] + y[j]), dir[l][j] = 0;
        }
        if(i % t == 0){
            memcpy(f[i / t], dp[l], sizeof(dp[l]));
            memcpy(g[i / t], dir[l], sizeof(dir[l]));
        }
    }
    int tx = n, ty = m;
    for(int i = n / t; i >= 0; --i){
        memcpy(df[0], f[i], sizeof(f[i]));
        memcpy(dg[0], g[i], sizeof(g[i]));
        for(int j = i * t + 1; j <= min(n, (i + 1) * t); ++j){
            for(int k = 0; k <= m; ++k){
                df[j - i * t][k] = df[j - i * t - 1][k] + add(x[j] + y[k]), dg[j - i * t][k] = 1;
                if(k && df[j - i * t][k] < df[j - i * t][k - 1] + add(x[j] + y[k]))
                    df[j - i * t][k] = df[j - i * t][k - 1] + add(x[j] + y[k]), dg[j - i * t][k] = 0;
            }
        }
        while(tx >= (i * t + 1)){
            ans.push(dg[tx - i * t][ty]);
            if(!dg[tx - i * t][ty]) ty--;
            else tx--;
        }
    }
    while(ty) ans.push(0), ty--;
    write(dp[l ^ 1][m]), puts("");
    while(!ans.empty()) putchar(ans.top() ? 'C' : 'S'), ans.pop();
    return 0;
}
# C. 椅子
AT2645 [ARC076D] Exhausted?
可以直接暴力最大流，能拿不少部分分。
然后考场上以为是线段树优化建图什么的，然而并不是。
本题大力贪心即可。
首先一个假贪心：
  • 按照 lil_i 从小到大排序，相同的按 rir_i 从小到大排序。
  • 对于每个人先在左边找，让他在 ≤li\leq l_i 的最右边的空位置坐下，如果左边没有位置了，让他去右边找，在 ≥ri\geq r_i 的最左边的空位置坐下，如果都没有就加一张椅子。
  • 这个贪心可以被以下数据 hack\text{hack}：
    3 4
1 3
2 5
2 5

如何避免这一情况呢？
重新考虑这一过程，还是和上面一样的操作。
我们考虑到了第 ii 个人，在 lil_i 左边找到了空位置，让 ii 坐下。
这时第 jj 个人来了，但是我们在 ljl_j 左边找不到空位置了，我们考虑是否让 ii 起来，去右边找位置，并让 jj 坐在 ii 坐的位置上（排过序了，所以 ii 坐的位置 jj 肯定能坐）。
如何维护这一 “反悔” 操作呢？
我们开一个小根堆，如果 ii 在 ≤li\leq l_i 找到了空位置，我们把 rjr_j 插入到小根堆中。
还是考虑如果 ii 在左边找不到位置，此时堆顶为 rjr_j，我们分两种情况讨论：
  • ri<rjr_i < r_j，那就直接让 ii 去右边找个空位置坐下就行。
  • ri≥rjr_i \geq r_j，我们让 ii 去坐 jj 的位置，然后让 jj 去 ≥rj\geq r_j 找空位置。
然后就 ok\text{ok} 了。
codecode
代码中找空位置坐下跟上面略有不同，自己看代码理解一下吧 QwQ
#include <bits/stdc++.h>
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 2e5 + 10;
int n, m;
struct node{
    int l, r;
    inline bool operator < (const node &b) const{
        return l != b.l ? l < b.l : r < b.r;
    }
}p[N];
priority_queue <int, vector<int>, greater<int> > q;
int pos = 1, ans, tot;
int R[N];
signed main(){
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) p[i] = (node){read(), read()};
    sort(p + 1, p + 1 + n);
    for(int i = 1; i <= n; ++i){
        q.push(p[i].r);
        if(pos > p[i].l || pos > m) R[++tot] = q.top(), q.pop();
        else pos++;
    }
    sort(R + 1, R + 1 + tot);
    for(int i = tot, j = m; i >= 1; --i){
        if(j >= pos && j >= R[i]) j--;
        else ans++;
    }
    write(ans), puts("");
    return 0;
}
# D. 方舟系统
本来是没这题的，但是 B\text{B} 题大家之前都做过，所以就加了道题 /kk
O(n2)O(n^2) 的暴力 dp\text{dp} 非常好想，设 fif_i 表示处理到了第 ii 个数，最少的代价。
转移方程：
fi=min⁡{fj−1+∣aj−(i−j)∣}f_i = \min\{f_{j- 1} + |a_j - (i - j)| \}
能得 60pts\text{60pts}，好耶。
那么如何优化呢？
我们转移过程中就取了个最小值，所以我们只要能够维护一手前缀最小值即可。
先把这个绝对值打开，即 aj−(i−j)a_j - (i - j) 或者 (i−j)−aj(i - j) - a_j。
ii 是定值，不用管它，所以就剩下了 aj+ja_j + j 和 −aj−j-a_j - j。
所以我们开两个树状数组，分别维护 fj−1+aj+jf_{j - 1} + a_j + j 和 fj−1−aj−jf_{j - 1} - a_j - j 的最小值。
不要忘记这两个值可不是想用就能用的，绝对值的符号是固定的，所以一个是前缀最小值，一个是后缀最小值，自己判断一下吧。
codecode
#include <bits/stdc++.h>
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 1e5 + 10;
const int inf = 1e9 + 1e5;
int n;
int a[N], f[N];
unordered_map <int, int> c1, c2;
inline void add1(int x, int y){
    for(; x; x -= x & (-x)) 
        c1[x] = c1.find(x) != c1.end() ? min(c1[x], y) : y;
}
inline int qry1(int x){
    int res = inf;
    for(; x <= inf; x += x & (-x))
        res = c1.find(x) != c1.end() ? min(res, c1[x]) : res;
    return res;
}
inline void add2(int x, int y){
    for(; x <= inf; x += x & (-x))
        c2[x] = c2.find(x) != c2.end() ? min(c2[x], y) : y;
}
inline int qry2(int x){
    int res = inf;
    for(; x; x -= x & (-x))
        res = c2.find(x) != c2.end() ? min(res, c2[x]) : res;
    return res;
}
signed main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i){
        int r1 = qry1(i), r2 = qry2(i);
        f[i] = min(r1 - i, r2 + i);
        add1(a[i] + i, f[i - 1] + a[i] + i), add2(a[i] + i, f[i - 1] - a[i] - i);
    }
    write(f[n]), puts("");
    return 0;
}
 更新于   阅读次数  次