牛客周赛 Round 100 题解

A. 小红的双排列

签到，\(1-n\) 每个数输出两次即可。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using i128 = __int128; 
using PII = pair<int, int>;

i128 read(){i128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(i128 x){if (x < 0){putchar('-');x = -x;}if(x > 9) print(x / 10);putchar(x % 10 + '0');}

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

    for (int i = 1; i <= n; i++) cout << i << ' ' << i << ' ';
    cout << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

B. 小红的双排列拆分

先后进行两次 "从数组出取出 \(n\) 个互不相同的数" 的操作。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using i128 = __int128; 
using PII = pair<int, int>;

i128 read(){i128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(i128 x){if (x < 0){putchar('-');x = -x;}if(x > 9) print(x / 10);putchar(x % 10 + '0');}

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

    vector<int> a(n * 2);
    for (int i = 0; i < n * 2; i++) cin >> a[i];

    vector<int> st1(n + 1, 0), st2(n * 2, 0);
    for (int i = 0; i < n * 2; i++)
    {
        if (st1[a[i]]) continue;
        st1[a[i]] = st2[i] = 1;
        cout << a[i] << ' ';
    }
    cout << endl;
    for (int i = 0; i < n * 2; i++)
    {
        if (st2[i]) continue;
        cout << a[i] << ' ';
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

C.小红的双排列删除

每次以当前数组最左边的下标作为 \(l\)，如果无法找到对应的满足 \(a_l=a_r\) 的右边界 \(r\)，代表无法全部删除，输出 \(No\)。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using i128 = __int128; 
using PII = pair<int, int>;

i128 read(){i128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(i128 x){if (x < 0){putchar('-');x = -x;}if(x > 9) print(x / 10);putchar(x % 10 + '0');}

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

    vector<int> a(n * 2);
    for (int i = 0; i < n * 2; i++) cin >> a[i];

    int last = 0;
    for (int i = 1; i < n * 2; i++)
    {
        if (a[i] != a[last]) continue;
        last = ++i;
    }

    if (last != n * 2) cout << "No" << endl;
    else cout << "Yes" << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

D. 小红的双排列权值

首先预处理出初始数组的贡献 \(res\)。

通过模拟可以发现： * 当选择的两个下标 \(l,r\) 对应的两个区间相交时。交换不会使得贡献变大。 * 当选择的两个下标 \(l,r\) 对应的两个区间不相交时。设这两个区间分别为 \((l_1,r_1)\)，\((l_2,r_2)\)，此时 \(l，r\) 的组合有 \((l=l_1,r=l_2)\)，\((l=l_1,r=r_2)\)，\((l=l_2,r=l_1)\)，\((l=l_2,r=r_2)\)，四种情况。经过模拟，发现无论是哪种情况，交换 \(l,r\) 都会使得贡献增加 \((l_2-r_1) \times 2\)。

因此只需要找到所有区间中最左的右边界 \(R\)，以及最右的左边界 \(L\)，如果 \(L > R\)，使贡献加上 \((L - R) \times 2\)。

最后输出 \(res\) 即可。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using i128 = __int128; 
using PII = pair<int, int>;

i128 read(){i128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(i128 x){if (x < 0){putchar('-');x = -x;}if(x > 9) print(x / 10);putchar(x % 10 + '0');}

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

    vector<int> a(n * 2);
    vector<PII> st(n + 1, {-1, -1});
    for (int i = 0; i < n * 2; i++)
    {
        cin >> a[i];
        if (st[a[i]].x == -1) st[a[i]].x = i;
        else st[a[i]].y = i;
    }

    ll res = 0;
    for (int i = 1; i <= n; i++) res += st[i].y - st[i].x - 1;

    int L = -1, R = -1;
    for (int i = 0; i < n * 2; i++)
    {
        if (st[a[i]].y == i && R == -1) R = i;
        if (st[a[i]].x == i) L = i;
    }
    if (L > R) res += (L - R) * 2;

    cout << res << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

E. 小红的双排列删除得分

dp。

设 \(f_i\) 为对数组前 \(i\) 个元素进行删除，所能获得的最高分数，前 \(i\) 个数的元素和为 \(pre_i\), \(a_i\) 在数组中的下标分别为 \(\{st_{a_i}.x,st_{a_i}.y\}\)。

可以列出状态转移方程

\[ \begin{aligned} f[i] &= f[i - 1] \\ \text{if } st[a[i]].y = i,\quad &f[i] = \max\left(f[i],\ f[st[a[i]].x - 1] + \text{pre}[i] - \text{pre}[st[a[i]].x - 1]\right) \end{aligned} \]

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using i128 = __int128; 
using PII = pair<int, int>;

i128 read(){i128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(i128 x){if (x < 0){putchar('-');x = -x;}if(x > 9) print(x / 10);putchar(x % 10 + '0');}

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

    vector<int> a(n * 2 + 1, 0);
    vector<PII> st(n + 1, {-1, -1});
    for (int i = 1; i <= n * 2; i++) 
    {
        cin >> a[i];
        if (st[a[i]].x == -1) st[a[i]].x = i;
        else st[a[i]].y = i;
    }

    vector<ll> pre(n * 2 + 1, 0);
    for (int i = 1; i <= n * 2; i++) pre[i] = pre[i - 1] + a[i];

    vector<ll> f(n * 2 + 1, 0);
    for (int i = 1; i <= n * 2; i++)
    {
        f[i] = f[i - 1];
        if (st[a[i]].y == i) f[i] = max(f[i], f[st[a[i]].x - 1] + pre[i] - pre[st[a[i]].x - 1]);
    }

    cout << f[n * 2] << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

F. 小红的双排列期望（easy）

小红的最优策略一定是尽可能少的操作概率小的数，因此可以先对 \(b\) 数组从小到大进行排序，排序后对应的 \(a\) 数组应为 \(1,1,2,2,3,3,...,n,n\)。

接下来对于 \(a\) 数组中的每个数，考虑 \(dp\)。

假设要把当前的数操作成 \(x\)，每次操作成功的概率为 \(p\)，\(f_i\) 代表从 \(i\) 操作到 \(x\) 的期望步数，则可以列出状态转移方程

\[ \begin{aligned} f_i = p \times f_{i + 1} + (1 - p) \times f_i + 1 \end{aligned} \]

经过移项，最终变为

\[ \begin{aligned} f_i = f_{i + 1} + \frac{1}{p} \end{aligned} \]

最终可化简为

\[ \begin{aligned} f_i = \frac{x - i}{p} \end{aligned} \]

因此对于数组 \(a\) 中的每个元素，期望步数为 \(\frac{x_i}{p_i}\)，全部加起来，即为最终期望步数。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using i128 = __int128; 
using PII = pair<int, int>;

i128 read(){i128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(i128 x){if (x < 0){putchar('-');x = -x;}if(x > 9) print(x / 10);putchar(x % 10 + '0');}

constexpr int mod = 1e9 + 7;

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

    vector<int> a(n * 2);
    for (int i = 0; i < n * 2; i++) cin >> a[i];

    sort(a.begin(), a.end());

    auto qmi = [&](ll a, int b)
    {
        ll res = 1;
        while (b)
        {
            if (b & 1) res = res * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return res;
    };

    ll res = 0;
    for (int i = 0; i < n * 2; i++)
    {
        ll x = i / 2 + 1;
        ll p = (ll)a[i] * qmi(100, mod - 2) % mod; 
        res = (res + x * qmi(p, mod - 2) % mod) % mod;
    }

    cout << res << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

G. 小红的双排列期望（hard）

同样考虑 \(dp\)，状态转移方程为

\[ \begin{aligned} f_i = p \times f_{i + 1} + (1 - p) \times f_{i - 1} + 1 \end{aligned} \]

对于 \(f_0\)，需要另列公式

\[ \begin{aligned} f_0 = p \times f_{1} + (1 - p) \times f_{0} + 1 \\ \end{aligned} \]

\[ \begin{aligned} \Downarrow\\ \end{aligned} \]

\[ \begin{aligned} f_0 = f_1 + \frac{1}{p} \end{aligned} \]

再把 \(f_0\) 代入到 \(f_1\) 中可得

\[ \begin{aligned} f_1 = p \times f_{2} + (1 - p) \times (f_1 + \frac{1}{p}) + 1 \\ \end{aligned} \]

\[ \begin{aligned} \Downarrow \\ \end{aligned} \]

\[ \begin{aligned} f_1 = f_2 + \frac{1 - p}{p} + \frac{1}{p} \end{aligned} \]

多次代入归纳整理可得

\[ \begin{aligned} f_0 = \sum_{i=1}^n{\sum_{j=1}^i{\frac{(1-p)^{j-1}}{p^j}}} \\ \end{aligned} \]

预处理一下即可。

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define endl '\n'

using namespace std;

using ll = long long;
using i128 = __int128; 
using PII = pair<int, int>;

i128 read(){i128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
void print(i128 x){if (x < 0){putchar('-');x = -x;}if(x > 9) print(x / 10);putchar(x % 10 + '0');}

constexpr int mod = 1e9 + 7;

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

    vector<int> a(n * 2);
    for (int i = 0; i < n * 2; i++) cin >> a[i];

    sort(a.begin(), a.end());

    auto qmi = [&](ll a, int b)
    {
        ll res = 1;
        while (b)
        {
            if (b & 1) res = res * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return res;
    };

    vector f(101, vector<ll>(n + 1, 0));
    for (int i = 1; i <= 100; i++)
    {
        ll sum = 0;
        ll p = (ll)i * qmi(100, mod - 2) % mod;
        vector<ll> c(n + 1, 1);
        for (int j = 1; j <= n; j++) c[j] = c[j - 1] * p % mod;
        for (int j = 1; j <= n; j++)
        {
            sum = (sum + qmi(1 - p + mod, j - 1) * qmi(c[j], mod - 2) % mod) % mod;
            f[i][j] = (f[i][j - 1] + sum) % mod;
        }
    }

    ll res = 0;
    for (int i = 0; i < n * 2; i++)
        res = (res + f[a[i]][i / 2 + 1]) % mod;

    cout << res << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}