7.18暑期模拟赛

2022暑

---

T1 pellet

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

1.题意

$n$ 个相同物品放入 $m$ 个相同盒子中，盒子非空，求方案数（最小表示后不同即不同）。

$1\leq n,m\leq 5\times 10^3$。

2.解析

$$\sum_{i = 1}^{n}{i \times x_i} = n$$

考虑 DP。

考试的时候好像傻逼了，没推出来。

听说这个转移和第二类 $\operatorname{stirling}$ 很像。

$f[i][j]$ 表示 $i$ 个球，$j$ 个箱子的答案。

转移分两种，一种是全部都多放一个，一种是在最前面放一个 $1$

$$f[i][j] = f[i - j][j] + f[i - 1][j - 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 = 5005, mod = 998244353;
int n, k;
int f[maxn][maxn];
signed main() {
//  freopen("A.in", "r", stdin);
//  freopen("A.out", "w", stdout);
    n = read(), k = read();
    for(register int i = 1; i <= n; ++i) f[1][i] = 1;
    for(register int i = 2; i <= k; ++i)
        for(register int j = i; j <= n; ++j) {
            f[i][j] = (f[i - 1][j - 1] + f[i][j - i]) % mod;
        }
    printf("%lld\n", f[k][n] % mod);
    return 0;
}

3.总结

奇奇怪怪的转移分类，积累。

T2 Tree

思维难度：$B^{+}$ 代码难度：$S^{-}$

1.题意

$n$ 节点树，有边权，找到最小的长度 $k$ 满足 $S \leq k \leq E$ 的路径，输出长度。

$1\leq n\leq 10^5$。

2.解析

显然可以二分答案。

那确定了长度，就是一个淀粉质板子判定。

//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 = 2e5 + 5, INF = 1e9 + 7;
int n, L, R;
struct node {
    int v, nex;
    int w;
}edge[maxn << 1];
int head[maxn], len;
int Siz[maxn], Maxx[maxn], root, Sum, Answer;
int Vst[maxn];  
inline void make_map(int u, int v, int w) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    edge[len].w = w;
    head[u] = len;
}
inline void Get_Siz(int x, int fa) {
    Siz[x] = 1;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v, z = edge[i].w;
        if(y == fa) continue;
        Get_Siz(y, x), Siz[x] += Siz[y];
    }
}
inline int Get_Rt(int x, int fa) {
    int s = 1;  Maxx[x] = 0;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v, z = edge[i].w;
        if(y == fa || Vst[y]) continue;
        int nex = Get_Rt(y, x); s += nex;
        Maxx[x] = max(Maxx[x], nex);
    }
    Maxx[x] = max(Maxx[x], Sum - s);
    if(Maxx[x] < Maxx[root]) root = x;
    return s;
}
inline set<int> Calc(int x, int fa) {
    set<int> now; now.insert(0);
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v, z = edge[i].w;
        if(y == fa || Vst[y]) continue;
        set <int> Nex = Calc(y, x);
        for(auto j : Nex) now.insert(z + j);
    }
    return now;
}
inline void Solve(int x) {
    set<int> now; now.insert(0), Vst[x] = 1;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v, z = edge[i].w;;
        if(Vst[y]) continue;
        set <int> Nex = Calc(y, x); set <int> :: iterator It;
        for(auto j : Nex) {
            It = now.lower_bound(L - j - z);
            if(It != now.end()) Answer = min(Answer, *It + j + z);      
        }
        for(auto j : Nex) now.insert(j + z);
        Solve(y);
    }
}
int main() {
//  freopen("B.in", "r", stdin);
//  freopen("B.out", "w", stdout);
    n = read(), L = read(), R = read();
    for(register int i = 1; i < n; ++i) {
        int u = read(), v = read(), w = read();
        make_map(u, v, w), make_map(v, u, w);
    }
    Answer = INF, Solve(1);
    if(Answer > R) printf("-1\n");
    else printf("%d\n", Answer);
    return 0;
}

3.总结

寄在不会淀粉质。

T3 Gcd

思维难度：$S^{+}$，代码难度：$B$

1.题意

求满足 $1\leq a,b\leq n,\gcd(a,b)=a\oplus b$ 的无序数对 $(a,b)$ 的个数。

$1\leq n\leq 10^7$。

2.解析

异或可逆，所以 $b = a \oplus c$

那么有：$\gcd(a, a \oplus c) = c$