原博客题解地址：https://zhuanlan.zhihu.com/p/690875770

不得不说，最有节目效果的一场：

忘记放题目，延迟20min，但是居然忘记推后20min（乐

A题

根据题意模拟即可，将指定下标的值相加即可。

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

void solve()
{
    cin >> n >> m;
    vector<int> a(n);
    lop(i, 0, n)
    {
        cin >> a[i];
    }
    LL ans = 0;
    int x;
    lop(i, 0, m)
    {
        cin >> x;
        x --;
        ans += a[x];
    }
    cout << ans << el;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

B题

设 A 赢得的次数为 $a$ ， B 赢得次数为 $b$ ，平局次数为 $c$ 。

于是有：

$3a c=X$

$3b c=Y$

相减可以得到：

3(a-b)=X-Y

容易发现，当 $X-Y$ 含有 $3$ 这个因子则必然有解。

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

void solve()
{
    LL x, y;
    cin >> x >> y;
    LL ans = abs(x - y);
    if(ans % 3 == 0)
    {
        cout << "Yes" << el;
    }
    else {
        cout << "No" << el;
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    int T;
    cin >> T;
    while(T --)
    {
        solve();
    }
}

C题

不难看出每一位都是独立的，如果这一位是 $1$ 则标记为 $0$ ，否则赋值为 $1$ 。

因为需要的正整数，所以如果数据是若干个连续的 $1$ 的时候，我们需要特判输出 $2$ 。

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

void solve()
{
    string s;
    cin >> s;
    int len = s.size();
    vector<int> a(len);
    string ans = "";
    lop(i, 0, len)
    {
        a[i] = s[i] - '0';
        if (a[i] != 0)
        {
            ans += '0';
        }
        else
        {
            ans += '1';
        }
    }
    int d = 0;
    int i = 0;
    while (i < len)
    {
        int now = ans[i] - '0';
        d = d * 10 + now;
        i += 1;
        if(i == len)
        {
            if(d == 0)
            {
                if(a[i - 1] != 1)
                {
                    d = 1;
                }
                else {
                    d = 2;
                }
                
            }
        }
    }
    cout << d << el;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

D题

因为 $m\le 10$ ，不难想到枚举所有情况 $2^m$ ，然后判断一种方案是否合法。

每个坐标都需要检查，检查一次是 $O(m)$ 。

所以总时间复杂度是 $O(2^m\times nm)$ 。

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

#define l first
#define r second

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<PII> a(m);
    lop(i, 0, m)
    {
        cin >> a[i].l >> a[i].r;
        a[i].l --;
        a[i].r --;
    }
    int U = 1 << m;
    int ans = 0;
    lop(S, 1, U)
    {
        vector<bool> vis(m);
        lop(j, 0, m)
        {
            if(S >> j & 1)
                vis[j] = true;
        }
        bool flag = true;
        lop(j, 0, n)
        {
            int cnt = 0;
            lop(k, 0, m)
            {
                if(vis[k] and a[k].l <= j and j <= a[k].r)
                {
                    cnt ++;
                }
            }
            if(cnt < 2)
            {
                flag = false;
                break;
            }
        }
        if(flag)
        {
            ans += 1;
        }
    }
    cout << ans << el;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

E题

不难发现任意一种策略，都可以转化为，先全做 A 任务，然后再来做 B 任务，这样等价的策略。

假设我已经确定了，我要做到第 $i$ 个 A 任务，此时我需要做 $k$ 个 B 任务，我显然会选择最小的 $k$ 个来做。

计算 $a_i$ 的前缀和 $pre_i$ 。

不难发现，前 $j$ 个 $\{b_i\}$ 的最小的 $k$ 个数，与前 $j 1$ 个的最小的 $k$ 个数，至多有一个数不同。

于是我们可以维护一个大顶堆，用它来维护最小的 $k$ 个 $b_i$ ，顺便记录这些数实时的和 $now$ 。

此时 $pre_i now$ 即是此时的代价，取所有的 $\min$ 即可，时间复杂度为 $O(n\log k)$ 。

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;

constexpr int N = 2e6 + 10, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

void solve()
{
    cin >> n >> m;
    vector<int> a(n + 1), b(n + 1);
    vector<LL> pre(n + 1);
    lop(i, 0, n)
    {
        cin >> a[i];
    }
    pre[0] = a[0];
    lop(i, 1, n)
    {
        pre[i] = pre[i - 1] + a[i];
    }
    lop(i, 0, n)
    {
        cin >> b[i];
    }
    while (m--)
    {
        int k;
        cin >> k;
        priority_queue<int, vector<int>, less<int>> q;

        LL now = 0;
        LL ans;
        lop(i, 0, k)
        {
            now += b[i];
            q.push(b[i]);
        }
        ans = pre[k - 1] + now;

        lop(i, k, n)
        {
            if (b[i] < q.top())
            {
                now -= q.top();
                q.pop();
                q.push(b[i]);
                now += b[i];
                cmin(ans, now + pre[i]);
            }
        }
        cout << ans << el;
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

F题

不难发现 $m=200$ 这个范围，很 $O(m^3)$ （bushi

其实 $n$ 这个范围并没有什么用，你可以考虑将坐标点都离散化到，然后最多只有 $2\times m$ 个点。

所以完全可以当做只跟 $m$ 有关的题目来做，所以复杂度想到 $O(m^3)$ 也很合理。

有个很好想，但是又很关键的性质：

假设有某种方案，一段区间被覆盖了 $k\ge 1$ 次，那么显然这个区间的右端点，必然是题目中某个线段的右端点。

基于这种性质，我们进行状态定义：

$f[l][r]$ 表示 $[0,l]$ 这一段区间都被覆盖至少了 $2$ 次， $[l 1,r]$ 区间被覆盖了 $1$ 次。
- 当 $l=r$ 时，根据定义，表示覆盖 $1$ 次的区间是空集。
初始默认 $0$ 这个坐标被覆盖了两次，即 $f[0][0]=1$ 。
我们可以离散化，然后 $l,r$ 就只有 $O(m)$ ，如果不离散化，该数组也可以用 map<pair<int, int>, LL> 来存储。

考虑状态转移，前 $[1,i-1]$ 个线段的选择方案，得到了 $f[l][r]$ ，然后选择第 $i$ 个线段。

问题就来了，我们要如何排序呢？
因为 DP 需要无后效性的，根据我们的状态定义，就需要线段按照如下规则排序：
- 按照左端点 $l$ 升序
- $l$ 相同时，按照右端点 $r$ 升序/降序
我只需要确保每次加入新的线段时，之前那些“废掉的状态”不会起死回生
- 比如 $[a,b],[c,d]$ 是两倍区间，但是 $(b,c)$ 是一倍区间
- 我们的转移不能让这种情况，转移到合法的情况。
所以我只需要保证，插入新的线段，左端点始终单调递增即可，而它的右端点则无所谓。

然后就是进行分类讨论了：

考虑，已有方案对应的 $[l,r]$ ，以及新加入的线段 $[L,R]$
- 其中 $l,r$ 必然是之前线段的右端点
- 利用滚动数组，新的数组为 $g$ ，先拷贝一份 $g=f$
我们只需要考虑当前的 $f[l][r]$ 需要之后转移到（累加到）哪一个状态中，也就是刷表法
当 $L\le l$ 时
- 当 $R\le l$ 时
  - 转移到 $g[l][r]$
- 当 $l<R\le r$
  - 转移到 $g[R][r]$
- $r < R$
  - 转移到 $g[r][R]$
当 $L=l 1$ 时
- 当 $R \le r$ 时
  - 转移到 $g[R][r]$
- 当 $r<R$ 时
  - 转移到 $g[r][R]$
当 $L=r 1$ 时
- 转移到 $g[l][R]$
其余情况，则表示这条线段加不进去 $f[l][r]$ 这种状态

核心代码也是非常的清晰优雅：

其中的 Z 表示模数类

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<PII> a(m + 1);
    rep(i, 1, m)
    {
        cin >> a[i].l >> a[i].r;
    }
    
    sort(a.begin(), a.end(), [&](PII x, PII y)
    {
        if(x.l != y.l)
            return x.l < y.l;
        else
            return x.r > y.r; });
    
    map<PII, Z> f;
    f[{0, 0}] = 1;
    for(int _ = 1; _ <= m; _ ++)
    {
        auto g = f;
        auto [L, R] = a[_];
        for (auto [it, v] : f)
        {
            auto [l, r] = it;
            if (L <= l)
            {
                if (R <= l)
                { // 这条线段选或不选
                    g[{l, r}] += f[{l, r}];
                }
                else if (R <= r)
                {// L <= l < R <= r
                    g[{R, r}] += f[{l, r}];
                }
                else
                {// L <= l <= r < R
                    g[{r, R}] += f[{l, r}];
                }
            }
            else if (L == l + 1)
            { // l < L <= r
                if (R <= r)
                { // L <= l < R <= r
                    g[{R, r}] += f[{l, r}];
                }
                else
                { // l < L <= r < R
                    g[{r, R}] += f[{l, r}];
                }
            }
            else if (L == r + 1)
            {
                g[{l, R}] += f[{l, r}];
            }
        }
        f.swap(g);
    }
    Z ans = f[{n, n}];
    cout << ans << el;
}

当时我写的时候遇到一个小 bug，就是我dp数组的索引是原本线段的下标（因为担心map），但是我忘记不同的线段的右端点可能相同。

会导致一个对应相同的 $f[l][r]$ 出现很多遍，转移刷表也很多次，这样显然错了。

写到一半发现问题，改成 map。

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define x first
#define y second
#define db double

typedef long long LL;
typedef pair<int, int> PII;
#define l first
#define r second
constexpr int N = 203, md = 1e9 + 7;
constexpr int INF = 0x3f3f3f3f;

int n, m;

constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x)
{
    if (x < 0)
    {
        x += P;
    }
    if (x >= P)
    {
        x -= P;
    }
    return x;
}
template <class T>
T power(T a, int b)
{
    T res = 1;
    for (; b; b /= 2, a *= a)
    {
        if (b % 2)
        {
            res *= a;
        }
    }
    return res;
}
struct Z
{
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const
    {
        return x;
    }
    Z operator-() const
    {
        return Z(norm(P - x));
    }
    Z inv() const
    {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs)
    {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs)
    {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs)
    {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs)
    {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs)
    {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs)
    {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs)
    {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a)
    {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a)
    {
        return os << a.val();
    }
};

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<PII> a(m + 1);
    rep(i, 1, m)
    {
        cin >> a[i].l >> a[i].r;
    }
    sort(a.begin(), a.end(), [&](PII x, PII y)
    {
        if(x.l != y.l)
            return x.l < y.l;
        else
            return x.r > y.r; });
    map<PII, Z> f;
    f[{0, 0}] = 1;
    rep(_, 1, m)
    {
        auto g = f;
        auto [L, R] = a[_];
        for (auto [it, v] : f)
        {
            auto [l, r] = it;
            if (L <= l)
            {
                if (R <= l)
                { // 这条线段选或不选
                    g[{l, r}] += f[{l, r}];
                }
                else if (R <= r)
                {// L <= l < R <= r
                    g[{R, r}] += f[{l, r}];
                }
                else
                {// L <= l <= r < R
                    g[{r, R}] += f[{l, r}];
                }
            }
            else if (L == l + 1)
            { // l < L <= r
                if (R <= r)
                { // L <= l < R <= r
                    g[{R, r}] += f[{l, r}];
                }
                else
                { // l < L <= r < R
                    g[{r, R}] += f[{l, r}];
                }
            }
            else if (L == r + 1)
            {
                g[{l, R}] += f[{l, r}];
            }
        }
        f.swap(g);
    }
    Z ans = f[{n, n}];
    cout << ans << el;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    solve();
}

牛客小白90题解

A题

B题

C题

D题

E题

F题