链接：https://ac.nowcoder.com/acm/contest/120561

题目按照通过人数降序排序。

L – Need Zero

算法：

模拟。

思路：

分类讨论即可。

关键代码：

void miyan()
{
    string s;
    cin >> s;

    if (s.back() == '0')
        cout << 1 << endl;
    else if (s.back() == '1' || s.back() == '3' || s.back() == '7' || s.back() == '9')
        cout << 10 << endl;
    else if (s.back() == '5')
        cout << 2 << endl;
    else
        cout << 5 << endl;
}

K – Constructive

算法：

贪心，构造。

思路：

容易想到只有 \(n = 1\) 或者 \(n = 3\) 时可以构造出满足要求的序列，其余情况全为无解。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    if (n == 1 || n == 3)
    {
        cout << "YES" << endl;

        for (int i = 1; i <= n; ++i)
            cout << i << ' ';
        cout << endl;
        return;
    }

    cout << "NO" << endl;
}

C – Array Covering

算法：

贪心。

思路：

观察到赋值区间为开区间，那么肯定有一些位置是被赋值不到的。

设最大值位置为 \(pos\)，显然选择区间 \((1, pos)\) 和 \((pos, n)\) 是最优解，可得数组开头与结尾赋值不到，因此答案为 \(a[pos] * (n – 2) + a[1] + a[n]\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;

    ll maxx = ranges::max(a);

    cout << maxx * (n - 2) + a[0] + a[n - 1] << endl;
}

E – Block Gam

算法：

模拟。

思路：

手玩样例可以发现，题目实际是一个长度为 \(n + 1\) 的数组执行循环右移，\(k\) 就为 \(a[n + 1] (1 – based)\)，最终答案为相邻两个元素的最大值。

具体实现看代码。

关键代码：

void miyan()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n + 2, k);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    ll ans = LLONG_MIN;
    for (int i = n + 1; i >= 1; --i)
        ans = max(ans, a[i] + a[i - 1]);

    cout << ans << endl;
}

B – Card Game

算法：

贪心，数学。

思路：

小苯的数字可以分为两部分：

• 可以获得分数（\(A\) 部分），既大于小红的一些数字；
• 不可以获得分数（\(B\) 部分），既小于小红的所有数字。

容易想到最优策略就是使 \(A\) 部分的数字都在对局过程中移走，手玩样例模拟发现只要是 \(A\) 部分的数字都可以被移走，那么就可以贪心的将 \(A\) 部分的数字全放开头，\(B\) 部分的数字全放结尾，那么答案就为 \(P(A_{cnt}, A_{cnt}) * P(B_{cnt}, B_{cnt})\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;

    ll minn = ranges::min(b);
    ll cnt = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] > minn)
            ++cnt;
    }

    ll ans = 1;
    for (int i = 1; i <= cnt; ++i)
        ans = ans * i % MOD;
    for (int i = 1; i <= n - cnt; ++i)
        ans = ans * i % MOD;

    cout << ans << endl;
}

A – A+B Problem

算法：

数学，概率论。

思路：

1. 先处理出显示器显示每个数字的概率。
2. 再处理出显示每个 \(4\) 位数字的概率。
3. 然后枚举数字 \(i\)，计算 \(p[i] * p[C – i]\) 的概率，累加到答案中即可。

关键代码：

ll qmi(ll a, ll b, ll p)
{
    ll ans = 1 % p;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }

    return ans;
}

ll inv(ll q, ll mod)
{
    return qmi(q, mod - 2, mod);
}

vector<string> s;
void init()
{
    s.push_back("1110111");
    s.push_back("0010010");
    s.push_back("1011101");
    s.push_back("1011011");
    s.push_back("0111010");
    s.push_back("1101011");
    s.push_back("1101111");
    s.push_back("1010010");
    s.push_back("1111111");
    s.push_back("1111011");
}

void miyan()
{
    ll C;
    cin >> C;

    vector<ll> p(7);
    for (auto &x : p)
        cin >> x;

    ll inv100 = inv(100, MOD);

    vector<ll> q(10);
    for (int i = 0; i <= 9; ++i)
    {
        string now = s[i];
        ll cnt = 1;
        for (int j = 0; j < 7; ++j)
        {
            if (now[j] - '0')
                cnt = cnt * p[j] % MOD * inv100 % MOD;
            else
                cnt = cnt * (100ll - p[j]) % MOD * inv100 % MOD;
        }

        q[i] = cnt;
    }

    vector<ll> num(10000);
    for (int i = 0; i < 10; ++i)
    {
        if (q[i] == 0)
            continue;

        for (int j = 0; j < 10; ++j)
        {
            if (q[j] == 0)
                continue;

            for (int l = 0; l < 10; ++l)
            {
                if (q[l] == 0)
                    continue;

                for (int r = 0; r < 10; ++r)
                {
                    if (q[r] == 0)
                        continue;

                    int x = i * 1000 + j * 100 + l * 10 + r;
                    num[x] = q[i] * q[j] % MOD * q[l] % MOD * q[r] % MOD;
                }
            }
        }
    }

    ll ans = 0;
    for (int i = 0; i <= C; ++i)
    {
        ll x = i, y = C - i;

        if (num[x] == 0 || num[y] == 0)
            continue;

        ans = (ans + num[x] * num[y] % MOD) % MOD;
    }

    cout << ans << endl;
}

G – Digital Folding

算法：

贪心，分类讨论。

思路：

此类数位题目，一般都是考虑让开头尽可能是 \(9\)。

不难想到（\(k\) 为 \(r\) 的数字位数 \(– 1\)）：

• 当 \(l = r\) 时，区间范围内就一个数字，显然答案就为 \(l\)；
• 当 \(r = 10^k\) 且 \(l != r\) 时，此时 \(r – 1\) 就可以最大化 \(9\) 的数量，容易想到答案就为 \(r – 1\)；
• 当 \(r != 10 ^ k\) 且 \(l\) 与 \(r\) 的位数不相同时，答案的位数必然与 \(r\) 的位数相等，此时可以将 \(l\) 赋值为 \(10 ^ k\)。

通过以上处理后，已经得到答案或者 \(l\) 与 \(r\) 的位数已经相等，此时问题就转换为了一个经典逐位贪心。

贪心策略（逐位贪心）：

• 如果 \(l_i = r_i\)，答案这一位就为 \(l_i\)；
• 否者，
  • 如果这是最后一位，答案这一位为 \(r_i\)；
  • 如果 \(r_i\) 及后面的所有位都是 \(9\)，答案就为 \(r\) 的这些位；
  • 如果 \(r_i\) 后面的位都是 \(9\)，答案就为 \(r_i\) 以及后面的 \(9\)；
  • 否者，答案的这一位为 \(r_i – 1\)，后面全为 \(9\)。

关键代码：

vector<ll> p(18);
void init()
{
    p[0] = 1;
    for (int i = 1; i < 18; ++i)
        p[i] = p[i - 1] * 10;
}

void miyan()
{
    ll l, r;
    cin >> l >> r;

    string L = to_string(l);
    string R = to_string(r);

    if (L.size() < R.size() && r > p[R.size() - 1])
    {
        l = p[R.size() - 1];
        L = to_string(l);
    }

    if (L.size() != R.size() && r == p[R.size() - 1] && r != l)
    {
        cout << r - 1 << endl;
        return;
    }

    if (r == p[R.size()] - 1)
    {
        cout << r << endl;
        return;
    }

    string ans;
    for (int i = 0; i < R.size(); ++i)
    {
        if (L[i] == R[i])
        {
            ans.push_back(L[i]);
            continue;
        }

        if (r % p[R.size() - i] == p[R.size() - i] - 1)
            ans += string(R.size() - i, '9');
        else
        {
            if (i == R.size() - 1 || r % p[R.size() - i - 1] == p[R.size() - i - 1] - 1)
                ans.push_back(R[i]);
            else
                ans.push_back(R[i] - 1);

            ans += string(R.size() - i - 1, '9');
        }
        break;
    }

    while (ans.back() == '0')
        ans.pop_back();

    ranges::reverse(ans);

    cout << ans << endl;
}

H – Blackboard

算法：

\(dp\)，前缀和优化，位运算优化。

思路：

发现前缀 \([1, i – 1]\) 表达式的值，不受 \(a_i\) 影响，考虑 \(dp\)。

定义 \(dp[i]\) 为考虑前缀 \([1, i]\) 其合法的替换方案。

状态转移：

• 我们向前找满足的 \(j\)，使得 \([j + 1, i]\) 这一段区间的数字和等于或，此时的方案就是以 \(i\) 结尾，擦除 \([j + 1, i]\)，令 \(j\) 与 \(j + 1\) 之间的运算符为 \(+\) 的方案，因此可以由 \(dp[j]\) 转移而来，既执行 \(dp[i] += dp[j]\)；
• 在转移时，想让 \([j + 1, i]\) 这段区间的数字和等于或，需要二进制加法中没有进位，既这段区间中二进制没有相同的位都是 \(1\)，那么只需判断这段区间进行按位与运算是不是等于 \(0\)，如果等于 \(0\)，说明没有相同位，否者存在相同位；
• 此时就容易写出 \(O(n ^ 2)\) 转移，既对于每个 \(i\) 都向前找 \(j\)，使得 \([j + 1, i]\) 按位与运算值为 \(0\)；
• 注：转移时枚举的 \(j\)，是让 \([j + 1, i]\) 这段区间的运算符都为或，其可以直接通过 \(dp[j]\) 转移而来。

\(O(n ^ 2)\) 转移过程：

vector<ll> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; ++i)
{
    ll x = 0;
    for (int j = i; j >= 1; --j)
    {
        if ((x & a[j]) != 0)
            break;

        x |= a[j];
        dp[i] = (dp[i] + dp[j - 1]) % MOD;
    }
}

\(O(n ^ 2)\) 不足以通过题目，考虑优化：

• 首先容易想到，在找 \(i\) 的前缀 \(j\) 时，要使 \([j + 1, i]\) 这段区间没有二进制相同的位都是 \(1\)，就说明这段区间长度必然不会太长，因为 \(a_i\) 的范围是 \(10^9\)，其二进制只有 \(31\) 位，根据鸽笼原理如果区间长度超过 \(31\)，那么必然有相同的二进制 \(1\)，又因为 \(a_i\) 可以取到 \(0\)，可能往前找半天都是找的 \(0\)，题目可以在这里卡我们，因此需要在这里做一些处理，既 \(pre[p]\) 代表下标 \(p\) 前面最近的一个非 \(0\) 值下标，这样就不用盲目走到 \(0\) 上；
• 考虑怎么快速计算 \(dp[i]\) 的值，在进行转移时 \([j + 1, i]\) 这段区间数字和等于或，那么 \([j + 2, i]\) 的数字和也等于或，此时必然存在距离 \(i\) 最远的 \(pos\)，使得 \([pos + 1, i]\) 数字和等于或，\(dp[i]\) 可以通过这段区间中的每个转移而来，因此可以维护前缀和数组优化 \(dp\)，直接使 \(dp[i]\) 累加 \([pos, i – 1]\) 这一段区间的 \(dp\) 值。

关键代码：

void miyan()
{
    ll n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector<int> pre(n + 1);
    int last = 0;
    for (int i = 1; i <= n; ++i)
    {
        pre[i] = last;

        if (a[i])
            last = i;
    }

    vector<ll> dp(n + 1, 0);
    vector<ll> s(n + 1, 0);
    dp[0] = 1, s[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        int x = 0, j = i;
        while (j >= 1 && (x & a[j]) == 0)
        {
            x |= a[j];
            j = pre[j];
        }

        if (j == 0)
            dp[i] = s[i - 1];
        else
            dp[i] = (s[i - 1] - s[j - 1] + MOD) % MOD;

        s[i] = (s[i - 1] + dp[i]) % MOD;
    }

    cout << dp[n] << endl;
}