8-15暑期模拟赛

2022暑

---

期望分数：

T1	T2	T3	Sum
100	0	100	200

实际分数：

T1	T2	T3	Sum
100	0	0	100

T1 Range

思维难度：$B^-$ ，代码难度：$B$

1.题意

给定一个序列 $a$，初始全 $0$，每次操作可选定一个区间 $[l, r]$ 全体加一，求最小次数变为序列 $b$ 。

2.解析

法一：$\operatorname{set}$ 优化暴力

把操作倒过来，考虑减法。

考虑暴力的过程，每次找出一个最小的把当前区间分成两段，并且都减掉这个点剩余的权值。

那么找最小的这个过程考虑离线下来，难处理的就是划分这个区间。

考虑用 $set$ 把区间的所有端点存一下，每次用树状数组差分修改权值，就维护好了。

法二：差分

很多个区间减的操作，想到差分。

把原数组差分，那么区间的修改就变成了选两个单点，前减后加，由于要都变成 $0$

所以显然找前面的一个正的和后面的一个负的配对做操作。

那么双指针扫一遍就好了

给出法一代码：

//The Code Is From Dawn
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x; 
}
const int maxn = 1e5 + 5;
int n;
int a[maxn], C[maxn], tot;
pair <int, int> ls[maxn], Answer[maxn];
set < pair<int, int> > S;
inline int lowbit(int x) { return x & (-x); }
inline void Update(int x, int num) { while(x <= n) C[x] += num, x += lowbit(x); }
inline int Query(int x) {
    int res = 0;
    while(x) res += C[x], x -= lowbit(x);
    return res;
}
inline void Split(int Val, int Id) {
    set< pair<int, int> > :: iterator It = S.upper_bound(make_pair(Id, 0)); It--;
    int l = (*It).first; It++; int r = (*It).first, num = Val - Query(Id);
//  printf("%d %d %d %d %d\n", Val, Id, l, r, num); 
    if(num) {
        Update(l, num), Update(r + 1, -num);
        while(num--) Answer[++tot] = make_pair(l, r);
    }
    if(Id != l) S.insert(make_pair(Id - 1, 1));
    if(Id != r) S.insert(make_pair(Id + 1, 0));
}
int main() {
//  freopen("range.in", "r", stdin);
//  freopen("range.out", "w", stdout);
    n = read();
    for(register int i = 1; i <= n; ++i) a[i] = read(), ls[i].first = a[i], ls[i].second = i;
    sort(ls + 1, ls + n + 1);
    S.insert(make_pair(1, 0)), S.insert(make_pair(n, 1));
    for(register int i = 1; i <= n; ++i) Split(ls[i].first, ls[i].second);
    printf("%d\n", tot);
    for(register int i = 1; i <= tot; ++i) printf("%d %d\n", Answer[i].first, Answer[i].second);
    return 0;
}

3.总结

似乎跟大量区间加减有关，但又找不到解决方法的时候差分是很好的尝试。

T2 Count

思维难度：$A^+$，代码难度 $B^+$

1.题意

给定 $n$，求合法的 $(x_1,x_2,\ldots,x_{2m})$ 组数，满足：

• $\forall i \in [1,2m]:x_i\in Z^+, x_i \mid n$
• $\prod_{i = 1}^{2m}{x_i} \leq n^m$

2.解析

很妙的思维题。

显然 $\prod_{i = 1}^{2m}{x_i} \leq n^{2m}$ ，考虑容斥。

全集数量很好计算，考虑 $\prod_{i = 1}^{2m}{x_i} > n^{m}$ 的情况。

一个很妙的想法，由于 $x_i \mid n$，考虑将每个 $x$ 变成 $\frac{n}{x}$

那么柿子变成：$\prod_{i = 1}^{2m}{\frac{n}{x_i}} > n^{m}$

显然这个柿子和 $\prod_{i = 1}^{2m}{x_i} < n^m$ 等价

换句话说，小于 $n^m$ 的情况与大于 $n^m$ 的情况一一对应，方案数相同。

那么只要考虑 $\prod_{i = 1}^{2m}{x_i} = n^m$ 怎么求。

显然可以将 $n$ 分解为 $\prod_{i}{p_i^{w_i}}$，每个质因子相互独立。

对于每个质因子，就是要统计：$\sum_{i = 1}^{2m}{k_i} = w_i * m$

一开始觉得这个计数可以直接插板，但是忽略了 $k_i \leq w_i$ 的上界。

只能 DP，这个 DP 似乎比较简单，类似于背包选一下值就好了。

补充：后面那个可以插板，枚举钦定 $k$ 个数不满足上界，然后将总和加上 $k * (w + 1)$ 正常插板就好了，大概是个容斥？

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x; 
}
const int maxn = 1e5 + 5, maxm = 205, mod = 998244353;
int n, m, len;
struct node {
    int Val, Num;
}Prime[maxn];
int All, AnsM;
int f[maxm][maxn];
inline int Ksm(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}
inline void Get_Prime() {
    for(register int i = 2; i <= n; ++i) {
        if(n % i == 0) Prime[++len].Val = i, Prime[len].Num = 0;
        while(n % i == 0) Prime[len].Num++, n /= i;
    }
}
inline void Solve_All() {
    All = 1;
    for(register int i = 1; i <= len; ++i) All = All * (Prime[i].Num + 1) % mod;
    All = Ksm(All, m * 2);
}
inline void Calc(int Id) {
    f[0][0] = 1;
    for(register int i = 1; i <= (m << 1); ++i)
        for(register int j = 0; j <= Prime[Id].Num * m; ++j)
            for(register int k = 0; k <= min(j, Prime[Id].Num); ++k) f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
}
inline void Solve_M() {
    AnsM = 1;
    for(register int i = 1; i <= len; ++i) {
        memset(f, 0, sizeof(f));
        Calc(i);
        AnsM = (AnsM * f[m << 1][Prime[i].Num * m]) % mod;
    }
}
signed main() {
//  freopen("count.in", "r", stdin);
//  freopen("count.out", "w", stdout);
    n = read(), m = read();
    Get_Prime(), Solve_All(), Solve_M();
    printf("%lld\n", ((All - AnsM + mod) % mod * Ksm(2, mod - 2) % mod + AnsM) % mod);
    return 0;
}

3.总结

数论题还是做得不多，没有发现这一美妙的性质

T3 Tree

思维难度：$A$，代码难度： $A$

1.题意：

一颗 $n$ 个点的树，你将每次从某个节点等概率选择一条边走到相邻节点，$q$ 组询问，询问从起点 $u$ 到 $v$ 的期望步数。

2.解析：

好像是一类期望板子题？

一开始的时候一直把状态设成：$f[x]$ 表示 $x$ 到 $v$ 的期望步数。

显然最暴力的可以直接列方程组高消。

考虑优化，会发现如果走出了 $u \rightarrow v$ 的贡献是确定的，也就是说只有 $u \rightarrow v$ 上的东西比较重要。

推出了个似乎能树剖维护的东西，大概长这样：

$$f_i = \frac{1}{d_i} * f_{fa} + \frac{1}{d_i} * \sum_{j \in son}{f_j}$$

当然还有另一半柿子没推了。

后来听说一个比较好的状态：设 $f_i$ 表示 $i$ 往上走一步的期望，$g_i$ 为往下走一步到 $i$ 的期望。

这样的好处就是处理路径比较简单，并且转移也很好推，考虑走的这一步的情况就好了，经典期望推法，直接放柿子吧：

$$f_x = \frac{1 + \sum_{y \in son(x)}{f[y] + f[x] + 1}}{d_x}$$

$$g_x = \frac{1 + g_{fa} + g_x + 1 + \sum_{y \in son(fa), y \neq x}{f[y] +g[x] +1}}{d_{fa}}$$

把这两个柿子化简：

$$f_x = d_x + \sum_{y \in son(x)} f[y]$$

$$g_x = d_{fa} + g_{fa} + \sum_{y \in son(fa), y \neq x} f[y]$$

把 $g_x$ 后面那个求和优化掉：

$$g_x = g_{fa} + f_{fa} - f_x$$

然后直接把 $u \rightarrow v$ 拆成 $u \rightarrow \operatorname{lca}$ 用 $f$ 做树上前缀和，$\operatorname{lca} \rightarrow v$ 用 $g$ 做树上前缀和就行了。

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x; 
}
const int maxn = 1e6 + 5, mod = 1e9 + 7;
int n, q;
struct node {
    int v, nex;
}edge[maxn];
int head[maxn], len;
int Up[maxn], Siz[maxn], Down[maxn], Du[maxn], Dep[maxn], f[maxn][25];
inline void make_map(int u, int v) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    head[u] = len;
}
inline void Ready1(int x, int fa) {
    Up[x] = Du[x];
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        Ready1(y, x);
        Up[x] = (Up[x] + Up[y]) % mod;
    }
}
inline void Ready2(int x, int fa) {
    Down[x] = (Du[fa] + Down[fa]) % mod;
    if(x != 1) Down[x] = (Down[x] + Up[fa] - Up[x] + mod - Du[fa] + mod) % mod;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        Ready2(y, x);
    }
}   
inline void Deal_First(int x, int fa) {
    Dep[x] = Dep[fa] + 1, Up[x] = (Up[x] + Up[fa]) % mod, Down[x] = (Down[x] + Down[fa]) % mod;
    for(register int i = 1; i <= 20; ++i)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        f[y][0] = x;
        Deal_First(y, x);
    }
}
inline int Get_Lca(int x, int y) {
    if(Dep[x] < Dep[y]) swap(x, y);
    for(register int i = 20; i >= 0; --i) {
        if(Dep[f[x][i]] >= Dep[y]) x = f[x][i];
        if(x == y) return x;
    }
    for(register int i = 20; i >= 0; --i)
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
inline int Calc(int x, int y) {
    int Lca = Get_Lca(x, y);
    return (Up[x] + Down[y] - Up[Lca] + mod - Down[Lca] + mod) % mod;
}
signed main() {
//  freopen("tree.in", "r", stdin);
//  freopen("tree.out", "w", stdout);
    n = read(), q = read();
    for(register int i = 1; i < n; ++i) {
        int u = read(), v = read();
        make_map(u, v), make_map(v, u), Du[u]++, Du[v]++;
    }
    Ready1(1, 0), Ready2(1, 0), Deal_First(1, 0);
    while(q--) {
        int u = read(), v = read();
        printf("%lld\n", Calc(u, v));
    }
    return 0;
}

3.总结

考试时想到了，但是太晚了，主要是积累下这个状态设计。