A.膜法记录

题解：

观察到 $n$ 的数据范围很小，那么只要暴力枚举 $n$ 行的所有策略，最后判断是否存在一种策略使得行数小于等于 $n$ ，同时所需的列数小于等于 $m$ 即可 $cnt[p]$ 表示用 $p$ 这种行策略能够处理掉的列数， $m-cnt[p]$ 就表示用 $p$ 这种行策略下仍需要使用列的个数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
char s[25][maxn];
ll cnt[1100000];
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
    {
        ll n, m, a, b;
        scanf("%lld%lld%lld%lld", &n, &m, &a, &b);
        for (int i = 1; i <= n; i++)
            scanf("%s", s[i] + 1);
        for (int i = 0; i < (1 << n); i++)
            cnt[i] = 0;
        for (int j = 1; j <= m; j++)
        {
            ll p = 0;
            for (int i = 1; i <= n; i++)
                if (s[i][j] == '*')
                    p |= (1 << i - 1);
            cnt[p]++;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < (1 << n); j++)
                if ((j & (1 << i - 1)) == 0)
                    cnt[j | (1 << i - 1)] += cnt[j];
        bool flag = false;
        for (int i = 0; i < (1 << n); i++)
            if (__builtin_popcount(i) <= a && m - cnt[i] <= b)
            {
                flag = true;
                break;
            }
        puts(flag ? "yes" : "no");
    }
    return 0;
}

B.阶乘

题意：

给定一个正整数 ${p}$
求一个最小的正整数 ${n}$ ，使得 ${n!}$ 是 ${p}$ 的倍数

题解：

如果 $x$ 是 $y$ 的倍数，那么就需要 $y$ 分解质因数在 $x$ 中同样存在并且 $x$ 中的幂数大于等于 $y$ 中的幂数
将 $p$ 质因数分解，然后二分寻找最小的 $n$
其中计算 $n!$ 中质因子 $x$ 的数量：

ll cal(ll n, ll x) 
{
    ll num = 0;
    while (n)
    {
        num += n / x;
        n = n / x;
    }
    return num;
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
vector<pair<ll, ll>> V;
bool check(int x)
{
    for (auto i : V)
    {
        ll cnt = 0, t = x;
        while (t)
        {
            cnt += t / i.first;
            t /= i.first;
        }
        if (cnt < i.second)
            return false;
    }
    return true;
}
void solve()
{
    V.clear();
    ll p, l, r;
    scanf("%lld", &p);
    l = 1, r = p;
    for (ll i = 2; i * i <= p; i++)
    {
        if (p % i == 0)
        {
            ll x = 0;
            while (p % i == 0)
            {
                p /= i;
                x++;
            }
            V.push_back(make_pair(i, x));
        }
    }
    if (p > 1)
        V.push_back(make_pair(p, 1ll));
    while (l < r)
    {
        ll mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%lld\n", l);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.完全图

题意：

给定一个包含 ${n}$ 个顶点的完全图但是删掉最多 ${m}$ 条，请问删去边之后的图最多能有几个连通块？

题意：

这题标答写得挺好，就直接贴过来了
反过来想，一开始是 $n$ 个孤立节点，我要添加恰好 $C_{n}^{2}-m$ 条边，让他连通块尽量多。
第一条肯定会让连通块数减少1，第二条也只能让连通块减少1，现在形成了一条包含三个点的链，接下来一条把这链的两个端点连起来，这一步没有让连通块的个数变少，再接下来一条边只能让连通块个数减少1......重复这
样的过程：除非必须要把孤立点连进来，否则我就在大连通块内部连点。
形成 $n-1, n-2, n-3, \dots, n-i$ 个连通块能用完的最大边数依次为： $1,3,6,\dots,\frac{i(i+1)}{2}$
二分可以解决
观察到 $1≤n,m≤10^{18}$ , $C_{n}^{2}-m$ 可能超过long long的范围，所以用python会方便很多

for t in range(int(input())):
    n, m = map(int, input().split())
    add = max(0, n * (n - 1) // 2 - m)
    l, r = 0, n - 1
    while l < r:
        mid = l + r >> 1
        if (mid * (mid + 1) >> 1) >= add:
            r = mid
        else:
            l = mid + 1
    print(n - l)

D.病毒传染（组合数学+概率）

题解：

这道题求 $P(t)$ 的一部分我现在还没想明白，就只能贴下官方题解顺便加点我想懂的地方了。
注意这是个条件概率
先求全局条件下“有t个人参加party之前就被感染，且最后共k人感染”的概率，令 $e = \frac{n(n-1)}{2}$
$P(t)=C_{n}^{t}p^t(1-p)^{n-t}C_{n-t}^{k-t}\frac{\sum_{i=0}^{k-t}(-1)^iC_{k-t}^{i}C_{e-t(n-k+i)}^{m}}{C_{e}^{m}}$
其中 $\frac{\sum_{i=0}^{k-t}(-1)^iC_{k-t}^{i}C_{e-t(n-k+i)}^{m}}{C_{e}^{m}}$ 为用容斥原理算出 $k-t$ 个人在party上被感染的概率
对每个 $t$ ，假设用上式算出的概率是 $P(t)$
那么对于一个 $t$ ，所求的条件概率就是 $\frac{ P(t) }{ \sum_{i=1}^{k} P(i) }$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
ll inv[maxn], fact[maxn], _fact[maxn];
ll p[1005];
ll ksm(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
void init()
{
    inv[0] = inv[1] = 1;
    for (int i = 2; i < maxn; i++)
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    fact[0] = _fact[0] = 1;
    for (int i = 1; i < maxn; i++)
    {
        fact[i] = fact[i - 1] * i % mod;
        _fact[i] = _fact[i - 1] * inv[i] % mod;
    }
}
ll C(ll n, ll m)
{
    if (m < 0 || m > n || n < 0)
        return 0;
    return fact[n] * _fact[m] % mod * _fact[n - m] % mod;
}
int main()
{
    init();
    ll n, m, k, P, tot = 0;
    scanf("%lld%lld%lld%lld", &n, &m, &k, &P);
    for (int t = 1; t <= k; t++)
    {
        auto &ans = p[t];
        ans = C(n, t) * ksm(P, t) % mod * ksm(100 - P, n - t) % mod * C(n - t, k - t) % mod;
        ll tmp = 0;
        for (int i = 0; i <= k - t; i++)
        {
            if (i & 1)
                tmp = (tmp - C(k - t, i) * C(n * (n - 1) / 2 - t * (n - k + i), m)) % mod;
            else
                tmp = (tmp + C(k - t, i) * C(n * (n - 1) / 2 - t * (n - k + i), m)) % mod;
        }
        ans = ans * tmp % mod;
        tot = (tot + ans) % mod;
    }
    for (int i = 1; i <= k; i++)
    {
        ll ans = p[i] * ksm(tot, mod - 2) % mod;
        printf("%lld\n", (ans + mod) % mod);
    }
    return 0;
}

E.A+B问题（水题）

题意：

给定一个 $C$ ，求出所有 $A+B=C$ 的方案数总和，其中 $A$ , $B$ , $C$ 均在32位有符号整数能存储的范围内。

题解：

因为 $A$ , $B$ , $C$ 均在32位有符号整数能存储的范围内，所以在给定范围内任意给定一个 $A$ 都能找到一个在范围内的 $B$ ,使得 $A+B=C$ ，所以总方案数就是 $2^{32}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;

int main()
{
    puts("4294967296");
    return 0;
}

F.美丽的序列I

题解：

这道题官方题解写得很好，直接贴过来了
图片说明
用前缀积就可以做到 $O(1)$
但是要注意的是并不是全部都满足 $\sum_{j=l_i}^{min(r_i,r_{i-1})}{r_{i-1}-j}$ ,只有当 $l_{i-1}\leq l_i$ 的时候才满足，所以计算的时候要判断一下 $l_{i-1}>l_i$ 的情况，这种情况下 $l_i$ 到 $min(i_{i-1},r_i)$ 这一部分是取不到的，但是前面计算的时候加上了这一部分，所以要减去

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll l[maxn], r[maxn], sum[maxn], len[maxn];
ll ksm(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll getsum(ll n)
{
    n %= mod;
    return (n * (n + 1) >> 1) % mod;
}
int main()
{
    int n;
    scanf("%d", &n);
    ll tot = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &l[i], &r[i]);
        len[i] = (r[i] - l[i] + 1);
        tot = tot * len[i] % mod;
    }
    ll ans = tot;
    for (int i = 2; i <= n; i++)
    {
        ll a = l[i], b = min(r[i], r[i - 1]);
        if (a > b)
            continue;
        ll t = ((b - a + 1) * r[i - 1]) % mod;
        if (l[i - 1] > l[i])
        {
            ll c = min(l[i - 1] - 1, r[i]);
            t = (t - (l[i - 1] - 1) * (c - a + 1)) % mod;
            a = c + 1;
        }
        t = (t - (getsum(b) - getsum(a - 1))) % mod;
        t = t * tot % mod;
        t = (t * ksm(len[i - 1], mod - 2) % mod * ksm(len[i], mod - 2)) % mod;
        ans = (ans + t) % mod;
    }
    printf("%lld\n", (ans + mod) % mod);
    return 0;
}

G.树上求和（贪心）

题解：

很经典的题型了，算出每条边包含在多少条路径中，然后按出现次数降序排序，出现次数越多的给的权值越少即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n, head[maxn], cnt, tot;
ll sz[maxn], num[maxn];
struct Edge
{
    int to, nxt;
} e[maxn << 2];
void init()
{
    memset(head, -1, sizeof(head));
    cnt = tot = 0;
}
void addedge(int u, int v)
{
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt++;
}
void dfs1(int u, int fa)
{
    sz[u] = 1;
    for (int i = head[u]; ~i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == fa)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}
void dfs2(int u, int fa)
{
    for (int i = head[u]; ~i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == fa)
            continue;
        num[tot++] = sz[v] * (n - sz[v]);
        dfs2(v, u);
    }
}
int main()
{
    init();
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    sort(num, num + tot);
    ll ans = 0, idx = n - 1;
    for (int i = 0; i < tot; i++)
    {
        ans += idx * num[i];
        idx--;
    }
    printf("%lld\n", ans);
    return 0;
}

H.奇怪的背包问题增加了（贪心）

题意：

有一个容量为 $2^{30}$ 的背包，和 $m$ 件物品，第 $i$ 件物品的体积为 $c_i$ ，你需要从中选出若干件，使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性，那就是 $c_i = 2^{k_i}$ ，其中 $0 <k_i < 30$ ，即所有 $c_i$ 都是 $2$ 的幂。

题解：

如果 $\sum c_i \ge 2^{30}$ ，那肯定可以凑出 $2^{30}$ ，只需要把所有的数字从大到小排序，依次加入数字，肯定在某个时刻和就等于 $2^{30}$ 。
因为低位可以合并成高位，而高位不能分解成低位，所以从大到小排序，把大的先放了不够的就可以用小的数来凑

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
bool ans[maxn];
pll p[maxn];
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
    {
        int n;
        scanf("%d", &n);
        ll sum = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            p[i].first = 1 << x;
            p[i].second = i;
            sum += p[i].first;
        }
        if (sum < (1 << 30))
        {
            puts("impossible");
            continue;
        }
        sort(p + 1, p + n + 1, greater<pll>());
        for (int i = 1; i <= n; i++)
            ans[i] = 0;
        ll res = 1 << 30;
        for (int i = 1; i <= n; i++)
            if (p[i].first <= res)
            {
                res -= p[i].first;
                ans[p[i].second] = 1;
            }
        for (int i = 1; i <= n; i++)
            printf("%d", ans[i]);
        puts("");
    }
    return 0;
}

I.寻找字串（水题）

题意：

给定字符串 $s$ ，请你找出字典序最大的子串。

题解：

字典序最大的子串肯定是个后缀，直接在所有的后缀中取 $max$ 就可以

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;

int main()
{
    string s, ans;
    cin >> s;
    for (int i = 0; i < s.length(); i++)
        ans = max(ans, s.substr(i));
    cout << ans << endl;
    return 0;
}

J.最大的差（水题）

题意：

给定 $n$ 个数字，请你从中选出两个数字，使得这两个数字的差尽量大，输出这个最大的差。

题解：

找出最大值和最小值，最大值减最小值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;

int main()
{
    int n;
    scanf("%d", &n);
    int mx = -INF, mn = INF;
    for (int i = 0, x; i < n; i++)
    {
        scanf("%d", &x);
        mx = max(mx, x);
        mn = min(mn, x);
    }
    printf("%d\n", mx - mn);
    return 0;
}

牛客小白月赛23