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

贪心 + 枚举，枚举 + 按位考虑，期望dp + 树形dp + 换根，线段树

# A. 饥饿的小鸟（river）

对于一个位置 $i$ ，枚举 $i - L$ 到 $i - 1$ ，显然从越早的荷叶跳过来越优，开个指针记录一下枚举到的位置即可。

复杂度 $O(n)$

#include <bits/stdc++.h>
#define pb push_back
#define int 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 = 1e5 + 10;
const int inf = 1e17;
int n, L;
int a[N], f[N];

signed main(){
// #ifndef ONLINE_JUDGE
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
// #endif
    n = read(), L = read();
    for(int i = 1; i < n; ++i) a[i] = read();
    a[0] = inf, a[n] = inf;
    f[0] = inf;
    int p = 0;
    for(int i = 1, j; i <= n; ++i){
        if(i - L <= 0) {f[i] = a[i]; continue;}
        for(j = max(i - L, p); j < i; ++j){
            if(f[i] + f[j] <= a[i]) f[i] += f[j], f[j] = 0;
            else {f[j] -= (a[i] - f[i]), f[i] = a[i]; break;}
        }
        p = j;
    }
    write(f[n]), puts("");
    return 0;
}

# B. 进化序列（evolve）

非常水的题。

开个桶维护二进制下每一位出现次数，显然对于 $l$ 单调向右，最靠右合法的 $r$ 是单调递增的。

所以像莫队一样维护桶即可，复杂度 $O(n \log V)$ 。

#include <bits/stdc++.h>
#define pb push_back
#define int 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 = 1e5 + 10;
int n, m, ans, sum;
int a[N], buk[40];

inline void add(int x){
    int pos = 0;
    while(x){
        if(x & 1){
            if(!buk[pos]) sum += (1 << pos);
            buk[pos]++;
        }
        x >>= 1, pos++;
    }
}

inline void del(int x){
    int pos = 0;
    while(x){
        if(x & 1){
            buk[pos]--;
            if(!buk[pos]) sum -= (1 << pos);
        }
        x >>= 1, pos++;
    }
}

signed main(){
// #ifndef ONLINE_JUDGE
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
// #endif
    double st = clock();
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    int l = 1;
    for(int i = 1; i <= n; ++i){
        add(a[i]);
        while(l < i && sum >= m) del(a[l++]);
        ans += (i - l);
    }
    write(ans), puts("");
    double ed = clock();
    cerr << ed - st << endl;
    return 0;
}

# C. 旅行 travel

首先 $E(x^2) \neq E(x) \times E(x)$ ，因为事件不独立。

但是有 $E(x + x) = E(x) + E(x)$

所以推一下： $E((a + b)^2) = E(a^2 + b^2 + 2ab) = E(a^2) + E(b^2) + E(2ab)$

以下两个数组都是以 1 为根的情况下定义的。

我们设 $h_x$ 表示 $x$ 子树内的点的 $F$ 和的期望， $f_x$ 表示子树内 $F_y$ 和的平方的期望。

显然有：

$h_x = (1 - p) \times h_x + p \times (h_x + h_y) \\ f_x = (1 - p) \times f_x + p \times (f_x + f_y + 2h_xh_y)$

（注意要先转移 $f$ ，再转移 $h$ ）

设 $g_x$ 为以 1 为根的情况下 $x$ 子树外（不包括 $x$ ）的 $F$ 的和的期望， $ans_x$ 为答案，即 $x$ 连通块的 $F$ 的和的平方的期望。

接下来看如何换根。

一个比较无脑的思路是维护 $x$ 儿子的前缀后缀和，然后各种转移，这里给一个代码简洁很多的做法（当然要推式子）。

考虑根从 $u$ 换到 $v$ 。

$g_v = (1 - p) \times h_v + p \times (h_v + E_1)$

$E_1$ 为当前情况下 $v$ 以外的点 $F$ 的和的期望。那么 $E_1$ 怎么求呢？

观察到对于 $g_u$ 我们有这样的式子：

$g_u = (1 - p) \times E_1 + p \times (h_v + E_1)$

而这个时候 $g_u$ 是已知的，所以直接计算出 $E_1$ 再代回到刚才的式子中计算 $g_v$ 即可。

$ans$ 数组也是同理的，对于 $ans_v$ 有：

$ans_v = (1 - p) \times f_v + p \times (f_v + E_2 + 2h_vE_1)$

这就相当于 $E((a + b)^2) = E(a^2) + E(b^2) + E(2ab)$

同理， $ans_u$ 有：

$ans_u = (1 - p) \times E_2 + p \times (f_v + E_2 + 2h_vE_1)$

也是计算出 $E_2$ 再代回去算 $ans_v$ 即可。

代码还是有一定细节的，最重要的是不要忘记取模。

#include <bits/stdc++.h>
#define pb push_back
#define db double
#define p(i) edge[i].w

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;
const int mod = 998244353;
int n, m;
int a[N], d[N];
struct node{
    int v, w, nxt;
}edge[N << 1];
int head[N], tot;

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

inline void add(int x, int y, int z){
    edge[++tot] = (node){y, z, head[x]};
    head[x] = tot;
}

int fa[N][20], dep[N];

inline void dfs(int x, int f){
    fa[x][0] = f, dep[x] = dep[f] + 1;
    for(int i = 1; i <= 18; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(int i = head[x], y; i; i = edge[i].nxt)
        if((y = edge[i].v) != f) dfs(y, x);
}

inline int get_fa(int x, int k){
    for(int i = 18; i >= 0; --i)
        if(k >= (1 << i)) x = fa[x][i], k -= (1 << i);
    return x;
}

int F[N], f1[N], f2[N], g[N], ans[N];

inline void calc_F(int x){
    for(int i = head[x], y; i; i = edge[i].nxt){
        if((y = edge[i].v) == fa[x][0]) continue;
        calc_F(y), F[x] = add(F[x] + F[y]);
    }
}

inline void calc_E(int x){
    f1[x] = F[x], f2[x] = mul(F[x], F[x]);
    for(int i = head[x], y; i; i = edge[i].nxt){
        if((y = edge[i].v) == fa[x][0]) continue;
        calc_E(y);
        f2[x] = add(f2[x] + mul(p(i), add(f2[y] + 1ll * 2 * f1[x] * f1[y] % mod)));
        f1[x] = add(f1[x] + mul(p(i), f1[y]));
    }
}

inline void calc_ans(int x){
    for(int i = head[x], y; i; i = edge[i].nxt){
        if((y = edge[i].v) == fa[x][0]) continue;
        int E1 = sub(g[x] - mul(p(i), f1[y])), K = mul(mul(2, E1), f1[y]);
        g[y] = add(f1[y] + mul(p(i), E1));
        int E2 = sub(ans[x] - mul(p(i), add(f2[y] + K)));
        ans[y] = add(f2[y] + mul(p(i), add(E2 + K)));
        calc_ans(y);
    }
}

signed main(){
// #ifndef ONLINE_JUDGE
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
// #endif
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read(), d[i] = read();
    for(int i = 1; i < n; ++i){
        int x = read(), v = read(), w = read();
        add(x, v, w), add(v, x, w);
    }
    dfs(1, 0), F[1] = a[1];
    for(int i = 2; i <= n; ++i){
        int p = get_fa(i, d[i] + 1);
        F[i] += a[i], F[p] = sub(F[p] - a[i]);
    }
    calc_F(1), calc_E(1);
    g[1] = f1[1], ans[1] = f2[1];
    calc_ans(1);
    m = read();
    while(m--) write(ans[read()]), puts("");
    return 0;
}

# D. 平衡树 splay

考场上一眼是个 $\text{LCT}$ 裸题，但是没想到 $rotate$ 之后中序遍历不变实在是降智了。

~~不难发现~~，旋转之后树的中序遍历不变。

所以我们对中序遍历维护一个线段树，每次旋转就相当于单点修改了两个数的值。

然后维护区间乘积即可。

代码也是十分的板子， $rotate$ 不要写挂了就好/kk

#include <bits/stdc++.h>
#define pb push_back
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define int 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;
const int mod = 1e9 + 7;
int n, m;
int w[N], ch[N][2], sum[N << 2], val[N << 2], fa[N];
int in[N], out[N];

inline int add(int x) {return x >= mod ? x - mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}

int dfn[N], tim, id[N];

inline void upd(int x){
    sum[x] = add(w[x] + add(sum[ls(x)] + sum[rs(x)]));
    in[x] = ls(x) ? in[ls(x)] : dfn[x];
    out[x] = rs(x) ? out[rs(x)] : dfn[x];
}

inline void dfs(int x){
    if(ls(x)) dfs(ls(x));
    dfn[x] = ++tim, id[tim] = x;
    if(rs(x)) dfs(rs(x));
    upd(x);
}

#define lc rt << 1
#define rc rt << 1 | 1
#define mid ((l + r) >> 1)

inline void pushup(int rt){
    val[rt] = mul(val[lc], val[rc]);
}

inline void build(int l, int r, int rt){
    if(l == r) return val[rt] = sum[id[l]], void();
    build(l, mid, lc), build(mid + 1, r, rc);
    pushup(rt);
}

inline void update(int x, int k, int l, int r, int rt){
    if(l == r) return val[rt] = k, void();
    if(x <= mid) update(x, k, l, mid, lc);
    else update(x, k, mid + 1, r, rc);
    pushup(rt);
}

inline int query(int L, int R, int l, int r, int rt){
    if(L > r || R < l) return 1;
    if(L <= l && r <= R) return val[rt];
    return mul(query(L, R, l, mid, lc), query(L, R, mid + 1, r, rc));
}

inline void rotate(int x){
    if(!x) return;
    int y = fa[x], z = fa[y];
    int k = (rs(y) == x);
    ch[z][(rs(z) == y)] = x;
    fa[x] = z;
    ch[y][k] = ch[x][k ^ 1];
    fa[ch[x][k ^ 1]] = y;
    ch[x][k ^ 1] = y, fa[y] = x;
    upd(y), update(dfn[y], sum[y], 1, n, 1);
    upd(x), update(dfn[x], sum[x], 1, n, 1);
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = read(), m = read();
    for(int i = 1; i <= n; ++i){
        w[i] = read(), ch[i][0] = read(), ch[i][1] = read();
        fa[ls(i)] = fa[rs(i)] = i;
    }
    dfs(1), build(1, n, 1);
    while(m--){
        int op = read(), x = read();
        if(op == 0) rotate(ls(x));
        if(op == 1) rotate(rs(x));
        if(op == 2) write(query(in[x], out[x], 1, n, 1)), puts("");
    }
    return 0;
}

# A. 饥饿的小鸟（river）

# B. 进化序列（evolve）

# C. 旅行 travel

# D. 平衡树 splay

20220705

Siunaus 计数专题