首页 模拟赛

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

# A. 饥饿的小鸟（river）

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

复杂度 O(n)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）
非常水的题。
开个桶维护二进制下每一位出现次数，显然对于 ll 单调向右，最靠右合法的 rr 是单调递增的。
所以像莫队一样维护桶即可，复杂度 O(nlog⁡V)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(x2)≠E(x)×E(x)E(x^2) \neq E(x) \times E(x)，因为事件不独立。
但是有 E(x+x)=E(x)+E(x)E(x + x) = E(x) + E(x)
所以推一下：E((a+b)2)=E(a2+b2+2ab)=E(a2)+E(b2)+E(2ab)E((a + b)^2) = E(a^2 + b^2 + 2ab) = E(a^2) + E(b^2) + E(2ab)
以下两个数组都是以 1 为根的情况下定义的。
我们设 hxh_x 表示 xx 子树内的点的 FF 和的期望，fxf_x 表示子树内 FyF_y 和的平方的期望。
显然有：
hx=(1−p)×hx+p×(hx+hy)fx=(1−p)×fx+p×(fx+fy+2hxhy)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)
（注意要先转移 ff，再转移 hh）
设 gxg_x 为以 1 为根的情况下 xx 子树外（不包括 xx）的 FF 的和的期望，ansxans_x 为答案，即 xx 连通块的 FF 的和的平方的期望。
接下来看如何换根。
一个比较无脑的思路是维护 xx 儿子的前缀后缀和，然后各种转移，这里给一个代码简洁很多的做法（当然要推式子）。
考虑根从 uu 换到 vv。
gv=(1−p)×hv+p×(hv+E1)g_v = (1 - p) \times h_v + p \times (h_v + E_1)
E1E_1 为当前情况下 vv 以外的点 FF 的和的期望。那么 E1E_1 怎么求呢？
观察到对于 gug_u 我们有这样的式子：
gu=(1−p)×E1+p×(hv+E1)g_u = (1 - p) \times E_1 + p \times (h_v + E_1)
而这个时候 gug_u 是已知的，所以直接计算出 E1E_1 再代回到刚才的式子中计算 gvg_v 即可。
ansans 数组也是同理的，对于 ansvans_v 有：
ansv=(1−p)×fv+p×(fv+E2+2hvE1)ans_v = (1 - p) \times f_v + p \times (f_v + E_2 + 2h_vE_1)
这就相当于 E((a+b)2)=E(a2)+E(b2)+E(2ab)E((a + b)^2) = E(a^2) + E(b^2) + E(2ab)
同理，ansuans_u 有：
ansu=(1−p)×E2+p×(fv+E2+2hvE1)ans_u = (1 - p) \times E_2 + p \times (f_v + E_2 + 2h_vE_1)
也是计算出 E2E_2 再代回去算 ansvans_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
考场上一眼是个 LCT\text{LCT} 裸题，但是没想到 rotaterotate 之后中序遍历不变实在是降智了。
不难发现，旋转之后树的中序遍历不变。
所以我们对中序遍历维护一个线段树，每次旋转就相当于单点修改了两个数的值。
然后维护区间乘积即可。
代码也是十分的板子，rotaterotate 不要写挂了就好 /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;
}
 更新于   阅读次数  次