20220701 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

斜率优化dp，莫队 + 线段树，权值线段树 + 线段树合并，数位dp

# A. 核酸检测

看了很久才发现是斜率优化……那么就是一个斜率优化板题。

先看暴力 $\text{dp}$ ，设 $f_i$ 表示计算到 $i$ 位置且在 $i$ 上放一名医护人员的最小花费，转移的时候枚举上一名医护人员的位置。

$f_i = \min\{f_j + \frac {(i - j) \times (i - j - 1)} 2 + a_i\}$

化简一下就可以斜率优化了（自己推吧，懒得打了QwQ）。

#include <bits/stdc++.h>
#define int long long
#define X(i) (i)
#define Y(i) (f[i] + i * (i + 1) / 2)

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 = 1e6 + 10;
int n, ans;
int a[N], f[N];
int q[N];

inline double slope(int i, int j){
    return (Y(i) - Y(j)) / (X(i) - X(j));
}

signed main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    int l = 1, r = 1;
    for(int i = 1; i <= n; ++i){
        while(l < r && slope(q[l], q[l + 1]) < i) l++;
        f[i] = f[q[l]] + (i - q[l]) * (i - q[l] - 1) / 2 + a[i];
        while(l < r && slope(q[r - 1], q[r]) > slope(q[r], i)) r--;
        q[++r] = i;
    }
    write(f[n]), puts("");
    return 0;
}

# B. 排列

这题也比较水。

开个值域线段树维护数字是否出现，这是个非常经典的东西，就维护 $maxl, maxr, maxzd$ 三个值就好。

外面再套一个莫队就可以做到 $O(n \sqrt n \log n)$ ，不是很卡。

是在不行的话莫队排序的时候加个奇偶优化即可。

#include <bits/stdc++.h>
#define fi first
#define se second
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)

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 = 5e4 + 10;
int n, m, B, tot;
int a[N], be[N], L[N], R[N];
int ans[N];
struct node{
    int l, r, id;
    inline bool operator < (const node &b) const{
        return be[l] != be[b.l] ? be[l] < be[b.l] : (be[l] & 1 ? r < b.r : r > b.r);
    }
}q[N];

struct Tree{
    int mxl, mxr, mx, len;
}t[N << 2];

inline void pushup(int rt){
    t[rt].mxl = t[ls].mxl, t[rt].mxr = t[rs].mxr;
    if(t[ls].mxl == t[ls].len) t[rt].mxl = t[ls].len + t[rs].mxl;
    if(t[rs].mxr == t[rs].len) t[rt].mxr = t[rs].len + t[ls].mxr;
    t[rt].mx = max(max(t[ls].mx, t[rs].mx), t[ls].mxr + t[rs].mxl);
}

inline void build(int l, int r, int rt){
    t[rt].len = r - l + 1;
    if(l == r) return;
    build(l, mid, ls), build(mid + 1, r, rs);
    pushup(rt);
}

inline void update(int x, int k, int l, int r, int rt){
    if(l == r) return t[rt].mx = t[rt].mxl = t[rt].mxr = k, void();
    if(x <= mid) update(x, k, l, mid, ls);
    else update(x, k, mid + 1, r, rs);
    pushup(rt);
}

inline void add(int x){
    update(a[x], 1, 1, n, 1);
}

inline void del(int x){
    update(a[x], 0, 1, n, 1);
}

signed main(){
    n = read(), m = read(), B = sqrt(n);
    for(int i = 1; i <= n; ++i) a[i] = read(), be[i] = (i - 1) / B + 1;
    for(int i = 1; i <= m; ++i)
        q[i] = (node){read(), read(), i};
    sort(q + 1, q + 1 + m);
    build(1, n, 1);
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++i){
        while(l > q[i].l) add(--l);
        while(r < q[i].r) add(++r);
        while(l < q[i].l) del(l++);
        while(r > q[i].r) del(r--);
        ans[q[i].id] = t[1].mx;
    }
    for(int i = 1; i <= m; ++i) write(ans[i]), puts("");
    return 0;
}

# C. ROT-Tree Rotations

建权值线段树，然后线段树合并。

合并时计算左右子树在前在后时分别的逆序对数，然后取较小的即可。

#include <bits/stdc++.h>
#define pb push_back
#define ll long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    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 = 2e5 + 10;
int n;
ll res1, res2, ans;
int tot;
int siz[N << 5], ls[N << 5], rs[N << 5];

inline int update(int k, int l, int r){
    int p = ++tot; siz[p]++;
    if(l == r) return p;
    int mid = (l + r) >> 1;
    if(k <= mid) ls[p] = update(k, l, mid);
    else rs[p] = update(k, mid + 1, r);
    return p;
}

inline int merge(int u, int v, int l, int r){
    if(!u || !v) return u | v;
    if(l == r) return siz[u] += siz[v], u;
    res1 += 1ll * siz[rs[u]] * siz[ls[v]];
    res2 += 1ll * siz[ls[u]] * siz[rs[v]];
    int mid = (l + r) >> 1;
    ls[u] = merge(ls[u], ls[v], l, mid);
    rs[u] = merge(rs[u], rs[v], mid + 1, r);
    siz[u] = siz[ls[u]] + siz[rs[u]];
    return u;
}

inline int dfs(){
    int k = read(), pos;
    if(!k){
        int ls = dfs(), rs = dfs(); res1 = res2 = 0;
        pos = merge(ls, rs, 1, n), ans += min(res1, res2);
    }else pos = update(k, 1, n);
    return pos;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read();
    dfs();
    write(ans), puts("");
    return 0;
}

# D. 计算

数位 $\text{dp}$ 。

先通过 $\text{kmp}$ 预处理出 $m$ 的 $nxt$ 数组，方便后面转移。

设 $f_{i, j}$ 表示计算到 $n$ 的第 $i$ 位，匹配到 $m$ 的第 $j$ 位时后面的答案。

转移时枚举第 $i$ 位为 $x$ ，那么贡献为： $f_{i + 1, j'} \times e^{\frac{x \times 10^t}n}$ 。

最后输出时要减去 $e^0$ ，即减 1。

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }

    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 = 15;
int n, m;
int b[N], lb, num[N], len;
int nxt[N], pw[N];
double dp[N][N];

inline void init(){
    for(int i = 0; i <= 13; ++i)
        for(int j = 0; j <= 13; ++j) dp[i][j] = -1;
    pw[0] = 1;
    for(int i = 1; i <= 10; ++i) pw[i] = pw[i - 1] * 10;

    int x = m;
    while(x) b[++lb] = x % 10, x /= 10;
    reverse(b + 1, b + 1 + lb);
    x = n;
    while(x) num[++len] = x % 10, x /= 10;
    reverse(num + 1, num + 1 + len);

    for(int i = 2, j = 0; i <= lb; ++i){
        while(j && b[i] != b[j + 1]) j = nxt[j];
        if(b[i] == b[j + 1]) j++;
        nxt[i] = j;
    }
}

inline int get_nxt(int i, int j){
    while(j && i != b[j + 1]) j = nxt[j];
    if(i == b[j + 1]) j++;
    return j;
}

inline double dfs(int pos, int mat, bool lim){
    if(mat == lb) return 0;
    if(pos == len + 1) return 1;
    if(!lim && dp[pos][mat] != -1) return dp[pos][mat];
    double res = 0, up = lim ? num[pos] : 9;
    for(int i = 0; i <= up; ++i)
        res += dfs(pos + 1, get_nxt(i, mat), (lim & (i == up))) * exp(1.0 * i * pw[len - pos] / n);
    if(!lim) dp[pos][mat] = res;
    return res;
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read(), init();
    printf("%.3lf\n", dfs(1, 0, 1) - 1);
    return 0;
}

# A. 核酸检测

# B. 排列

# C. ROT-Tree Rotations

# D. 计算

2022重庆集训游记

20220705