Preface

我的评价是 💩，A 题上来就给我喂逆天找不同，F 题逆天卡线段树 $1\log$，I 题更是位运算构思，让我花钱赤石的。

A. A+B Problem

状态压缩 逆元 枚举 概率论

nmd，出题人你自己做过吗，连个 cv 都不给，caonima。调了一个小时发现是少了个灯管。

v[0] = {0, 1, 1, 1, 0, 1, 1, 1};
v[1] = {0, 0, 0, 1, 0, 0, 1, 0};
v[2] = {0, 1, 0, 1, 1, 1, 0, 1};
v[3] = {0, 1, 0, 1, 1, 0, 1, 1};
v[4] = {0, 0, 1, 1, 1, 0, 1, 0};
v[5] = {0, 1, 1, 0, 1, 0, 1, 1};
v[6] = {0, 1, 1, 0, 1, 1, 1, 1};
v[7] = {0, 1, 0, 1, 0, 0, 1, 0};
v[8] = {0, 1, 1, 1, 1, 1, 1, 1};
v[9] = {0, 1, 1, 1, 1, 0, 1, 1};

我要对着一个个找！！！！

这个题目的解法是，找到掩码计算这个数被拼出来的概率 $p$，唯一良心的地方就是教会了小登怎么求逆元。然后在拼的时候，注意添加前导 0。

A.cc

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 998244353;

ll binpow(ll a, ll b, ll p)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
ll inv(ll a, ll p) { return binpow(a, p - 2, p); }
ll get_p(vector<ll> &pi, string s)
{
    ll p = 1;
    for (ll i = 0; i < s.size(); i++)
    {
        p = p * pi[s[i] - '0'] % MOD;
    }
    return p;
}
ll light_p(vector<ll> &vi, vector<ll> &vir, vector<vector<ll>> &mask, ll num)
{
    ll p = 1;
    for (ll i = 1; i <= 7; i++)
    {
        auto maskget = mask[num];
        if (maskget[i])
            p = p * vi[i] % MOD;
        else
        {
            p = p * vir[i] % MOD;
        }
    }
    return p;
}
void sol()
{
    ll c;
    cin >> c;
    ll arr[10];
    vector<ll> p(8), pir(8), pis(8);
    vector<vector<ll>> v(10);
    vector<ll> p_val(10);
    v[0] = {0, 1, 1, 1, 0, 1, 1, 1};
    v[1] = {0, 0, 0, 1, 0, 0, 1, 0};
    v[2] = {0, 1, 0, 1, 1, 1, 0, 1};
    v[3] = {0, 1, 0, 1, 1, 0, 1, 1};
    v[4] = {0, 0, 1, 1, 1, 0, 1, 0};
    v[5] = {0, 1, 1, 0, 1, 0, 1, 1};
    v[6] = {0, 1, 1, 0, 1, 1, 1, 1};
    v[7] = {0, 1, 0, 1, 0, 0, 1, 0};
    v[8] = {0, 1, 1, 1, 1, 1, 1, 1};
    v[9] = {0, 1, 1, 1, 1, 0, 1, 1};
    for (ll i = 1; i <= 7; i++)
    {
        cin >> p[i];
    }
    for (ll i = 1; i <= 7; i++)
    {
        pis[i] = p[i] * inv(100, MOD) % MOD;
    }
    for (ll i = 1; i <= 7; i++)
    {
        pir[i] = (100 - p[i]) * inv(100, MOD) % MOD;
    }

    for (ll i = 0; i <= 9; i++)
    {
        p_val[i] = light_p(pis, pir, v, i);
    }
    ll finals = 0;
    for (ll i = 0; i <= c; i++)
    {
        stringstream ss;
        ss << setfill('0') << setw(4) << i;
        string s = ss.str();
        ll p1 = get_p(p_val, s);
        ss.str("");
        ss.clear();
        ss << setfill('0') << setw(4) << c - i;
        s = ss.str();
        ll p2 = get_p(p_val, s);
        ll tmp = p1 * p2 % MOD;
        finals = (finals + tmp) % MOD;
    }
    cout << finals << "\n";
}
int main()
{
    ll t;
    cin >> t;
    while (t--)
    {
        sol();
    }
    return 0;
}

复杂度 $O(C)$。

B. Card Game

贪心 思维 数学

这也是一个 💩，题面有种从 cf 硬是给我翻译成中文的美感。

为了获得更高的分数，$B$ 应当把最小的放在最前面，$A$ 通过这个最小的来刷分，设 $B$ 最小的点为 $min_b$，那么所有大于 $min_b$ 的肯定可以随意打乱，设长度为 $K$，而小于 $min_b$ 也可以随意打乱，长度为 $n-K$，毕竟肯定赢不了 $B$，根据乘法原则和全排列公式，最后结果为 $K!(n-K)! \bmod 998244353$

B.cc

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

constexpr ll MOD = 998244353;
ll fact(int n)
{
    ll res = 1;
    for (int i = 2; i <= n; i++)
    {
        res = (res * i) % MOD;
    }
    return res;
}
void sol()
{
    ll n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }
    int minb = 0x3f3f3f3f;
    for (int i = 0; i < n; i++)
    {
        minb = min(minb, b[i]);
    }
    int k = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] > minb)
        {
            k++;
        }
    }
    ll fack = fact(k);
    ll fact2 = fact(n - k);
    ll ans = (fact2 * fack) % MOD;
    cout << ans << "\n";
}
int main()
{
    ll t;
    cin >> t;
    while (t--)
        sol();
    return 0;
}

复杂度 $O(n)$。

C. Array Covering

贪心 ad-hoc

💩，没看到 $(\ell,r)$ 开区间爽吃 3 发罚时，设长度为 $n$ 的数组 $a$，一定可以把所有除了 $1,n$ 位置上的数变成最大值。最终的结果就是 $\max_{i=1}^n\{a_i\}\times (n-2)+a_1+a_n$

C.cc

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    ll t;
    cin >> t;
    vector<ll> vi(t);
    ll maxs = 0;
    for (ll i = 0; i < t; i++)
    {
        cin >> vi[i];
        maxs = max(maxs, vi[i]);
    }
    cout << maxs * (t - 2) + vi[0] + vi[t - 1] << "\n";
}
int main()
{
    ll t;
    cin >> t;
    while (t--)
        sol();
    return 0;
}

D. Sequence Coloring

贪心 二分答案

二分答案做法，因为输出最小的 $x$ 而染色具有一定单调性，对 $x\in [1,n]$ 如果在 $x$ 秒内完成了所有的染色，那么缩小范围就在 $[1,x-1]$ 区间内查找，否则就是在 $[x+1,n]$ 范围查找，直到找到 $n$ 都无法满足的时候，就输出 $-1$。

所以我们的目的就是设计 $\text{check}(x)$ 函数，并从 1 开始向后染色。设 $ans$ 表示主动染色的个数，$t$ 表示最右侧的红色染了 $t$ 秒，最后我们会将 $ans$ 对 $k$ 进行比较，若最终 $t=x$ 满足 $ans\leqslant k$ 时，说明这是合法的。

接下来就是处理每一秒染色到位置的时候下一秒会到哪，这里有一个 trick，就是预处理前缀 max 来帮助我们快速地查找下一次扩散的位置，例如数组是 $a=[6,1,1,1,1,1,1,1,1]$ 那么如果我们设计染色跳转就直接跳转到 $a_m=[6,6,6,6,6,6,6,7,8]$，设第 $i$ 项跳转的地点为 $n_i$，那么 $n_i=\max\{n_{i-1},a_i+i\}$ 这样就省去了很多不必要的计算。

在每次跳转到 $n_i$ 之后如果 $x=t$ 条件成立并且没有到达最右侧，那么我们就需要考虑多染一个方块，需要 $ans:=ans+1$，同时我们还要找下一个要主动染红的位置，这个位置不能是黑色，所以我们需要避开它们。最终如果只要最终手动染红的位置个数不超过 $k$，那就是合法的，就继续从更小的时间二分，否则选取更大的范围。

以及最终答案如果超过 $n$ 秒都不行，则说明无解输出 $-1$。

D.cc

// WIP

复杂度 $O(n\log n)$。

E. Block Game

贪心 枚举

这也是一个 💩，题面有种从 cf 硬是给我翻译成中文的美感，能不能好好说话？？

实际上就是一个 $k,a_1,a_2,a_3,\cdots,a_n$ 的环形数组，取相邻两个最大值即可。

E.cc

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

void sol()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> vi(1, k);
    for (ll i = 0; i < n; i++)
    {
        ll tmp;
        cin >> tmp;
        vi.push_back(tmp);
    }
    ll ans = -1e9;
    for (ll i = 1; i < vi.size(); i++)
    {
        ans = max(ans, vi[i - 1] + vi[i]);
    }
    ans = max(ans, vi[vi.size() - 1] + k);
    cout << ans << "\n";
}
int main()
{
    ll t;
    cin >> t;
    while (t--)
        sol();
    return 0;
}

复杂度 $O(n)$。

F. Block Game

组合数学 链式并查集

这也是一个 💩，硬是给我卡线段树卡 $1\log$，我真想问了这有什么意义？人家快读 + 循环 + 位运算积极优化卡常卡过去了你好意思吗？？？

不过能学到的还是有的，但是你也别这么恶心我啊？？

F.cc

// WIP

G. Digital Folding

贪心 枚举 分类讨论 数位dp

迷惑性很强，如果分类讨论的话，那这题就是妥妥的 💩，一是数位 dp 能过当然可以，不过我还是注意力惊人贪心贪上去了。

那么就是分两部分贪心：

1. 位数小于 $r$ 的位数：如果区间 $[\ell, r]$ 跨越了不同的位数（比如 $\ell=80, r=120$），那么在小于 $r$ 的位数中，我们一定能构造出类似 $9, 99, 999$ 这样的数。只要区间覆盖了某个 $k$ 位数的全集，那么该位数的最大翻转值必然是全由 $9$ 组成的数（如 $999$）。
2. 位数等于 $r$ 的位数：这是最核心的部分。我们需要在 $[\ell, r]$ 范围内找一个数，使其翻转后最大。
   • 贪心构造：我们从原数的低位开始往高位看。我们希望原数的个位是 $9$，十位是 $9$，百位是 $9$
   • 从 $r$ 递减：最简单的办法是从 $r$ 出发，尝试把末尾变多更多的 $9$。例如 $r = 1234$。尝试把个位变 $9$：变成 $1229$（如果 $1229 \geqslant \ell$）。尝试把后两位变 $9$：变成 $1199$（如果 $1199 \geqslant \ell$）。尝试把后三位变 $9$：变成 $0999$（即 $999$，如果 $999 \geqslant \ell$）。

G.cc

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll rev(ll n)
{
    if (n == 0)
        return 0;
    string s = to_string(n);
    reverse(s.begin(), s.end());
    return stoll(s);
}

void sol()
{
    ll l, r;
    cin >> l >> r;
    ll mval = 0;
    mval = max(mval, rev(l));
    mval = max(mval, rev(r));

    string s = to_string(r);
    int n = s.size();

    for (int i = 0; i < n; ++i)
    {
        if (s[i] > '0')
        {
            string t = s;
            t[i]--;
            for (int j = i + 1; j < n; ++j)
                t[j] = '9';

            ll val = stoll(t);
            if (val >= l)
            {
                mval = max(mval, rev(val));
            }
        }
    }

    if (n > 1)
    {
        string t(n - 1, '9');
        ll val = stoll(t);
        if (val >= l)
        {
            mval = max(mval, rev(val));
        }
    }

    cout << mval << "\n";
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        sol();
    return 0;
}

单组复杂度 $O(\log R)$

H. Blackboard

又是位运算构思。

WIP.

I. AND vs MEX

WIP.

J. MST Problem

WIP.

K. Constructive

签到 构造

很显然只有 1 与 1 2 3 成立，那就交上去。

K.cc

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

void sol()
{
    int n;
    cin >> n;
    if (n == 1)
    {
        cout << "YES\n";
        cout << 1 << "\n";
        return;
    }
    if (n == 3)
    {
        cout << "YES\n";
        cout << "1 2 3" << "\n";
        return;
    }
    cout << "NO\n";
}
int main()
{
    ll t;
    cin >> t;
    while (t--)
        sol();
    return 0;
}

L. Need Zero

签到

真签到。

贡献者

Timothy Starman

版权所有

版权归属：Timothy Starman

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

编辑此页

上一页CFR 1077 div1-2 题解

下一页牛客寒假训练营-2