首页 > 其他分享 >Codeforces Round 979 div2 个人题解(A~E)

Codeforces Round 979 div2 个人题解(A~E)

时间：2024-10-21 08:52:25浏览次数：7  
标签：typedef int 题解 Codeforces 979 leq 测试用例 n0 include

Codeforces Round 979 div2 个人题解(A~E)

Dashboard - Codeforces Round 979 (Div. 2) - Codeforces

火车头

#define _CRT_SECURE_NO_WARNINGS 1

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <chrono>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>

#define ft first
#define sd second

#define yes cout << "yes\n"
#define no cout << "no\n"

#define Yes cout << "Yes\n"
#define No cout << "No\n"

#define YES cout << "YES\n"
#define NO cout << "NO\n"

#define pb push_back
#define eb emplace_back

#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()
#define unq_all(x) x.erase(unique(all(x)), x.end())
#define unq_all1(x) x.erase(unique(all1(x)), x.end())
#define sort_all(x) sort(all(x))
#define sort1_all(x) sort(all1(x))
#define reverse_all(x) reverse(all(x))
#define reverse1_all(x) reverse(all1(x))

#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fLL

#define RED cout << "\033[91m"
#define GREEN cout << "\033[92m"
#define YELLOW cout << "\033[93m"
#define BLUE cout << "\033[94m"
#define MAGENTA cout << "\033[95m"
#define CYAN cout << "\033[96m"
#define RESET cout << "\033[0m"

// 红色
#define DEBUG1(x)                     \
    RED;                              \
    cout << #x << " : " << x << endl; \
    RESET;

// 绿色
#define DEBUG2(x)                     \
    GREEN;                            \
    cout << #x << " : " << x << endl; \
    RESET;

// 蓝色
#define DEBUG3(x)                     \
    BLUE;                             \
    cout << #x << " : " << x << endl; \
    RESET;

// 品红
#define DEBUG4(x)                     \
    MAGENTA;                          \
    cout << #x << " : " << x << endl; \
    RESET;

// 青色
#define DEBUG5(x)                     \
    CYAN;                             \
    cout << #x << " : " << x << endl; \
    RESET;

// 黄色
#define DEBUG6(x)                     \
    YELLOW;                           \
    cout << #x << " : " << x << endl; \
    RESET;

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t i128;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<ll, int> pli;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;

typedef tuple<int, int, int> ti3;
typedef tuple<ll, ll, ll> tl3;
typedef tuple<ld, ld, ld> tld3;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pli> vpli;
typedef vector<pss> vpss;
typedef vector<ti3> vti3;
typedef vector<tl3> vtl3;
typedef vector<tld3> vtld3;

typedef vector<vi> vvi;
typedef vector<vl> vvl;

typedef queue<int> qi;
typedef queue<ll> ql;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef queue<psi> qpsi;
typedef queue<psl> qpsl;

typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;
typedef priority_queue<pll> pqpll;
typedef priority_queue<psi> pqpsl;

typedef map<int, int> mii;
typedef map<int, bool> mib;
typedef map<ll, ll> mll;
typedef map<ll, bool> mlb;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<char, bool> mcb;
typedef map<string, int> msi;
typedef map<string, ll> msl;
typedef map<int, bool> mib;

typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

template <typename T>
inline T read()
{
    T x = 0;
    int y = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            y = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * y;
}

template <typename T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x >= 10)
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

/*#####################################BEGIN#####################################*/
void solve()
{
}

int main()
{
    ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int _ = 1;
    std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

/*######################################END######################################*/
// 链接：

A. A Gift From Orangutan

A. 来自猩猩的礼物
时间限制：每个测试1秒
内存限制：256兆字节

在丛林探险时，你遇到了一只戴着领结的稀有猩猩！你和猩猩握手，并给他一些食物和水。作为回报……

猩猩送给你一个长度为 \(n\) 的数组 \(a\)。使用 \(a\)，你将构建两个数组 \(b\) 和 \(c\)，它们都包含 \(n\) 个元素，方式如下：

每个 \(1 \leq i \leq n\) 对应 \(b_i = \min(a_1, a_2, \ldots, a_i)\)。
每个 \(1 \leq i \leq n\) 对应 \(c_i = \max(a_1, a_2, \ldots, a_i)\)。
将 \(a\) 的得分定义为 \(\sum_{i=1}^{n}(c_i - b_i)\)（即 \(c_i - b_i\) 与所有 \(1 \leq i \leq n\) 之和）。在计算得分之前，您可以随意打乱 \(a\) 的元素。

找出以最佳方式打乱 \(a\) 的元素时可以获得的最大得分。

输入
第一行包含 \(t\) (\(1 \leq t \leq 100\)) — 测试用例的数量。

每个测试用例的第一行包含一个整数 \(n\) (\(1 \leq n \leq 1000\)) — \(a\) 中的元素数量。

下一行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 1000\)) — 数组 \(a\) 的元素。

保证所有测试用例的 \(n\) 之和不超过 \(1000\)。

输出
对于每个测试用例，输出你能得到的最高分数。

示例
输入

3  
1  
69  
3  
7 6 5  
5  
1 1 1 2 2

输出

0  
4  
4

备注
在第一个测试用例中，没有其他方法可以重新排列 \(a\)。因此，\(b = [69]\) 和 \(c = [69]\)。唯一可能的得分是 \(69 - 69 = 0\)。

在第二个测试用例中，你可以将 \(a\) 重新排列为 \([7, 5, 6]\)。这里，\(b = [7, 5, 5]\) 和 \(c = [7, 7, 7]\)。在这种情况下的得分是 \((7 - 7) + (7 - 5) + (7 - 5) = 4\)。可以证明这是最大可能得分。

解题思路

我们可以获得的最大极差是最大值\(mx\)减最小值\(mn\)，所以只需要找出最大和最小值算出极差然后乘以\(n-1\)即可

代码实现

void solve()
{
    int n;
    cin >> n;
    int mx = 0;
    int mn = inf;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        mx = max(mx, x);
        mn = min(mn, x);
    }
    cout << 1ll * (n - 1) * (mx - mn) << endl;
}

B. Minimise Oneness

时间限制：每个测试1.5秒
内存限制：256兆字节

对于任意二进制字符串 \(t\)，令 \(f(t)\) 为 \(t\) 中仅包含 \(0\) 的非空子序列的数量，令 \(g(t)\) 为 \(t\) 中至少包含一个 \(1\) 的非空子序列的数量。

我们将二进制字符串 \(t\) 的一元性定义为 \(|f(t)−g(t)|\)，其中对于任意整数 \(z\)，\(|z|\) 表示 \(z\) 的绝对值。

给定一个正整数 \(n\)。查找长度为 \(n\) 的二进制字符串 \(s\)，使得其一性尽可能小。如果有多个字符串，则可以打印其中任何一个。

输入
第一行包含一个整数 \(t\) (\(1 \leq t \leq 10^4\)) — 测试用例的数量。

每个测试用例的唯一一行包含一个整数 \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) — \(s\) 的长度。

保证所有测试用例的 \(n\) 的总和不超过 \(2 \cdot 10^5\)。

输出
对于每个测试用例，在新行上输出 \(s\)。如果存在多个答案，则输出任意一个。

示例
输入

3  
1  
2  
3

输出

0  
01  
010

备注
在第一个测试用例中，输出示例中 \(f(t)=1\)，因为有一个仅包含 \(0\) 的子序列（\(0\)），而 \(g(t)=0\)，因为没有包含至少一个 \(1\) 的子序列。一元性为 \(|1−0|=1\)。输出 \(1\) 也是正确的，因为它的一元性为 \(|0−1|=1\)。

在第二个测试用例中，输出示例中 \(f(t)=1\)，因为有一个仅包含 \(0\) 的非空子序列，而 \(g(t)=2\)，因为有两个至少包含一个 \(1\) 的非空子序列（\(01\) 和 \(1\)）。因此一元性为 \(|1−2|=1\)。可以证明这是所有可能长度为 \(2\) 的二进制字符串中一元性的最小值。

解题思路

记字符串\(t\)中\(0\)的数量为\(n0\)，\(1\)的数量为\(n1\)，易得\(f(t)=2^{n0}-1\)，\(g(t)=2^{n0}\times(2^{n1}-1)\)。

\[|f(t) - g(t)| = |(2^{n0} - 1) - (2^{n0} \times (2^{n1} - 1))| \]

展开 $ g(t) $：

\[g(t) = 2^{n0} \times (2^{n1} - 1) = 2^{n0 + n1} - 2^{n0} \]

代入 $ g(t) $ 的表达式：

\[|f(t) - g(t)| = |(2^{n0} - 1) - (2^{n0 + n1} - 2^{n0})| \]

\[= |2^{n0} - 1 - 2^{n0 + n1} + 2^{n0}| \]

\[= |2 \cdot 2^{n0} - 1 - 2^{n0 + n1}| \]

\[= |2^{n0 + 1} - 2^{n0 + n1}-1| \]

这里我们可以考虑两种情况：

  • 如果 $ n1 = 0 $，则 $ g(t) = 0 $，此时 $ |f(t) - g(t)| = |2^{n0} - 1| $。

  • 如果 $ n1 > 0 $，则 $ 2^{n0 + n1} $ 会大于 $ 2^{n0 + 1} $，所以：

    \[|f(t) - g(t)| = 2^{n0 + n1} - 2^{n0 + 1} - 1 \]

最终结果为：

\[|f(t) - g(t)| = |2^{n0 + 1} - 2^{n0 + n1} - 1| \]

当\(n1=1\)时值最小

代码实现

void solve()
{
    int n;
    cin >> n;
    string s(n - 1, '0');
    s += "1";
    cout << s << endl;
}

C. A TRUE Battle

时间限制：每个测试2秒
内存限制：256兆字节

Alice 和 Bob 正在玩游戏。有一个包含 \(n\) 个布尔值的列表，每个布尔值要么为真，要么为假，以长度为 \(n\) 的二进制字符串给出（其中 \(1\) 表示真，而 \(0\) 表示假）。最初，布尔值之间没有运算符。

Alice 和 Bob 将轮流在布尔值之间放置 and 或 or，Alice 先走。因此，游戏将由 \(n−1\) 个回合组成，因为有 \(n\) 个布尔值。Alice 的目标是让最后一个语句的计算结果为真，而 Bob 的目标是让它的计算结果为假。给定布尔值列表，确定如果两个玩家都发挥最佳水平，Alice 是否会获胜。

要计算最终表达式的值，请重复执行以下步骤，直到语句由单个真或假组成：

如果语句包含 and 运算符，请选择任意一个并将其周围的子表达式替换为其计算值。
否则，语句包含 or 运算符。请选择任意一个并将其周围的子表达式替换为其计算值。

例如，表达式 true or false and false 的计算结果为 true or (false and false) = true or false = true。可以证明任何复合语句的结果都是唯一的。

输入
第一行包含 \(t\) (\(1 \leq t \leq 10^4\)) — 测试用例的数量。

每个测试用例的第一行包含一个整数 \(n\) (\(2 \leq n \leq 2 \cdot 10^5\)) — 字符串的长度。

第二行包含一个长度为 \(n\) 的二进制字符串，由字符 \(0\) 和 \(1\) — 布尔值列表组成。

保证所有测试用例的 \(n\) 的总和不超过 \(2 \cdot 10^5\)。

输出
对于每个测试用例，如果 Alice 获胜，则输出“YES”（不带引号），否则输出“NO”（不带引号）。

您可以在任何情况下输出“YES”和“NO”（例如，字符串“yES”、“yes”和“Yes”将被识别为肯定响应）。

示例
输入

5  
2  
11  
3  
010  
12  
101111111100  
10  
0111111011  
8  
01000010

输出

YES  
NO  
YES  
YES  
NO

备注
在第一个测试用例中，Alice 可以在两个布尔值之间放置 and。游戏结束，因为没有其他地方可以放置运算符，Alice 赢得比赛，因为 true and true 是 true。

在第二个测试用例中，Alice 可以在中间的 true 和左边的 false 之间放置 or。Bob 可以在中间的 true 和右边的 false 之间放置 and。语句 false or true and false 是 false。

注意，这些示例可能不是 Alice 或 Bob 的最佳策略。

解题思路

对于在最左边的1来说，如果我们在其右边插入一个or，那么无论右边最后算出来是什么结果，都无法改变它，对于最右边的1同理。

所以如果字符串首或尾有1则Yes。

对于子串"11"来说，我们一定可以构成"... or 1 ... 1 or ..."或"... 1 or 1 or ...."的形式使得1无法被消除，所以如果字符串存在“11”，则Yes

其它情况则No

代码实现

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (s.front() == '1' || s.back() == '1' || s.find("11") != string::npos)
        YES;
    else
        NO;
}

D. QED's Favorite Permutation

时间限制：每个测试2秒
内存限制：256兆字节

QED 被赋予一个长度为 \(n\) 的排列 \(p\)。他还有一个长度为 \(n\) 的字符串 \(s\)，其中仅包含字符 \(L\) 和 \(R\)。QED 只喜欢按非递减顺序排序的排列。要对 \(p\) 进行排序，他可以选择以下任何操作并执行任意次数：

选择一个索引 \(i\)，使得 \(s_i = L\)。然后，交换 \(p_i\) 和 \(p_{i-1}\)。保证 \(s_1 \neq L\)。
选择一个索引 \(i\)，使得 \(s_i = R\)。然后，交换 \(p_i\) 和 \(p_{i+1}\)。保证 \(s_n \neq R\)。

他还被给予 \(q\) 个查询。在每个查询中，他选择一个索引 \(i\)，并将 \(s_i\) 从 \(L\) 更改为 \(R\)（或从 \(R\) 更改为 \(L\)）。请注意，这些更改是持久的。

每次查询后，他都会询问您是否可以通过执行上述操作任意多次以非递减顺序对 \(p\) 进行排序。请注意，在回答每个查询之前，排列 \(p\) 会重置为其原始形式。

输入
第一行包含 \(t\) (\(1 \leq t \leq 10^4\)) — 测试用例的数量。

每个测试用例的第一行包含两个整数 \(n\) 和 \(q\) (\(3 \leq n \leq 2 \cdot 10^5\), \(1 \leq q \leq 2 \cdot 10^5\)) — 排列的长度和查询的数量。

下一行包含 \(n\) 个整数 \(p_1, p_2, \ldots, p_n\) (\(1 \leq p_i \leq n\), \(p\) 是排列)。

下一行包含 \(n\) 个字符 \(s_1 s_2 \ldots s_n\)。保证 \(s_i\) 为 \(L\) 或 \(R\)、\(s_1 = R\) 和 \(s_n = L\)。

以下 \(q\) 行包含一个整数 \(i\) (\(2 \leq i \leq n-1\))，表示 \(s_i\) 从 \(L\) 更改为 \(R\)（或从 \(R\) 更改为 \(L\)）。

保证所有测试用例的 \(n\) 和 \(q\) 之和不超过 \(2 \cdot 10^5\)。

输出
对于每个查询，如果可能则输出“YES”（不带引号），否则输出“NO”（不带引号）。

您可以在任何情况下输出“YES”和“NO”（例如，字符串“yES”、“yes”和“Yes”将被识别为肯定响应）。

示例
输入

3  
5 3  
1 4 2 5 3  
RLRLL  
2  
4  
3  
8 5  
1 5 2 4 8 3 6 7  
RRLLRRRL  
4  
3  
5  
3  
4  
6 2  
1 2 3 4 5 6  
RLRLRL  
4  
5

输出

YES  
YES  
NO  
NO  
YES  
NO  
NO  
NO  
YES  
YES

备注
在第一个测试用例中，第一个查询后的 \(s = RRRLL\)。QED 可以使用以下操作对 \(p\) 进行排序：

最初，\(p = [1, 4, 2, 5, 3]\)。
选择 \(i=2\) 并将 \(p_2\) 与 \(p_3\) 交换。现在，\(p = [1, 2, 4, 5, 3]\)。
选择 \(i=5\) 并将 \(p_5\) 与 \(p_4\) 交换。现在，\(p = [1, 2, 4, 3, 5]\)。
选择 \(i=4\) 并将 \(p_4\) 与 \(p_3\) 交换。现在，\(p = [1, 2, 3, 4, 5]\)，这是非递减顺序。

可以证明，第一个测试用例三次更新后，不可能对数组进行排序。

解题思路

观察题目可得两个性质

  1. 设\(R=0,L=1\)，对于任何非递减序的子段，我们可以任意重排里面的元素
  2. 对于任意子数组\(p_{l},p_{l+1},p_{l+2},\dots,p_{r}\)满足$l=min(p_i),l\le i\le r \(且\)r=max(p_i),l\le i\le r \(，我们需要重排\)p_i,l\le i\le r$

所以，我们可以根据性质2，对排列\(p\)进行分段，对每一段计算其逆序对数量。算出每段逆序对数总和。如果总和为零，说明可以重排。

每次更改计算一下对该段逆序对的影响，然后加到总和中。

计算逆序对可以使用树状树状或线段树。

时间复杂度为\(O(n\log(n))\)

其实维护LR数量就行了，不需要维护逆序对数量。赛时树状数组板子出问题了，写半天没找到bug在哪，一直wa2，还以为逆序对算错了，赛后才发现是板子有问题，人麻了

代码实现

struct seg
{
    int l, r;
    seg() : l(0), r(0) {}
    seg(int _l, int _r) : l(_l), r(_r) {}
    bool operator<(const seg &rhs) const
    {
        return l < rhs.l;
    }
};

template <typename T>
struct Fenwick
{
    int n;
    vector<T> a;

    Fenwick(int n_ = 0)
    {
        init(n_);
    }

    void init(int n_)
    {
        n = n_;
        a.assign(n + 1, T{});
    }

    void add(int x, const T &v)
    {
        for (int i = x; i <= n; i += i & -i)
        {
            a[i] = a[i] + v;
        }
    }

    T sum(int x)
    {
        T ans{};
        for (int i = x; i > 0; i -= i & -i)
        {
            ans = ans + a[i];
        }
        return ans;
    }

    T rangeSum(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }
};

void solve()
{
    int n, q;
    cin >> n >> q;
    vi a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    int mx = 0;       // 最大值
    int l = 1, r = 1; // 左右指针
    set<seg> st;      // 存储可排序的区间
    for (int i = 1; i <= n; i++, r++)
    {
        mx = max(mx, a[i]); // 更新最大值
        if (mx == r)
        {                      // 如果当前最大值等于右指针
            st.insert({l, r}); // 将区间[l, r]插入集合
            l = i + 1;         // 更新左指针
        }
    }

    string s;
    cin >> s;
    s = " " + s;
    Fenwick<int> cntR(n + 1); // 维护R的数量
    Fenwick<int> cntL(n + 1); // 维护L的数量
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == 'R')
            cntR.add(i, 1);
        else
            cntL.add(i, 1);
    }

    long long sum = 0; // 统计逆序对的总和
    for (auto it : st)
    {                           // 遍历可排序的区间
        int l = it.l, r = it.r; // 取出区间的左右端点
        for (int i = l; i <= r; i++)
        {
            if (s[i] == 'R')                // 如果当前是R
                sum += cntL.rangeSum(l, i); // 统计逆序对
        }
    }

    while (q--)
    {                                     // 处理每个查询
        int p;                            // 查询的索引
        cin >> p;                         // 输入查询索引
        auto it = st.upper_bound({p, p}); // 找到p的上界
        it = prev(it);                    // 获取p的前一个区间
        int l = it->l, r = it->r;         // 获取区间的左右端点
        if (s[p] == 'R')
        {                               // 如果当前是R
            sum -= cntL.rangeSum(l, p); // 减去当前逆序对
            cntL.add(p, 1);             // 更新L
            cntR.add(p, -1);            // 更新R
            s[p] = 'L';                 // 改变方向
            sum += cntR.rangeSum(p, r); // 加上新的逆序对
        }
        else
        {                               // 如果当前是L
            sum -= cntR.rangeSum(p, r); // 减去当前逆序对
            cntL.add(p, -1);            // 更新L
            cntR.add(p, 1);             // 更新R
            s[p] = 'R';                 // 改变方向
            sum += cntL.rangeSum(l, p); // 加上新的逆序对
        }
        if (sum == 0)        // 如果逆序对总数为0
            cout << "YES\n"; // 可以排序
        else
            cout << "NO\n"; // 不能排序
    }
}

E. MEXimize the Score

时间限制：每个测试2秒
内存限制：256兆字节

假设我们将数组 \(b\) 的元素划分为任意数量 \(k\) 的非空多集 \(S_1, S_2, \ldots, S_k\)，其中 \(k\) 为任意正整数。将 \(b\) 的得分定义为 \(b\) 的所有可能分区中任意整数 \(k\) 的最大值 \(MEX(S_1) + MEX(S_2) + \ldots + MEX(S_k)\)。

Envy 被赋予一个大小为 \(n\) 的数组 \(a\)。因为他知道计算 \(a\) 的分数对你来说太容易了，所以他要求你计算 \(a\) 的所有 \(2^{n}-1\) 个非空子序列的分数之和。由于这个答案可能很大，请输出它对 \(998244353\) 取模的结果。

整数集合 \(c_1, c_2, \ldots, c_k\) 中的 \(MEX\) 定义为集合 \(c\) 中未出现的最小非负整数 \(x\)。例如，\(MEX([0,1,2,2])=3\) 和 \(MEX([1,2,2])=0\)。

如果可以通过删除几个（可能是零个或全部）元素从 \(y\) 中获得 \(x\)，则序列 \(x\) 是序列 \(y\) 的子序列。

输入
第一行包含一个整数 \(t\) (\(1 \leq t \leq 10^4\)) — 测试用例的数量。

每个测试用例的第一行包含一个整数 \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) — \(a\) 的长度。

每个测试用例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i < n\)) — 数组 \(a\) 的元素。

保证所有测试用例的 \(n\) 之和不超过 \(2 \cdot 10^5\)。

输出
对于每个测试用例，输出答案，模数为 \(998244353\)。

示例
输入

4  
3  
0 0 1  
4  
0 0 1 1  
5  
0 0 1 2 2  
4  
1 1 1 1

输出

11  
26  
53  
0

备注
在第一个测试用例中，我们必须考虑七个子序列：

\([0]\)：得分为 \(1\)。
\([0]\)：得分为 \(1\)。
\([1]\)：得分为 \(0\)。
\([0,0]\)：得分为 \(2\)。
\([0,1]\)：得分为 \(2\)。
\([0,1]\)：得分为 \(2\)。
\([0,0,1]\)：得分为 \(3\)。

第一个测试用例的答案是 \(1 + 1 + 2 + 2 + 2 + 3 = 11\)。

在最后一个测试用例中，所有子序列的得分都是 \(0\)。

解题思路

观察发现分数 $ b $ 等价于 $cnt_0 + \min(cnt_0, cnt_1) + \ldots + \min(cnt_0, \ldots, cnt_{n-1}) $，其中 $ cnt_i $ 表示 \(i\)在$ b $的出现次数。

我们可以贪心地构造这 $ k $ 个分区，每次选择最小的 $ j $ 使得 $ cnt_j = 0 $ 且 $ \min(cnt_0, \ldots, cnt_{-1}) > 0 $，得到分区 $ [0, 1, \ldots, j-1] $。

这是最优的，因为我们添加的每个元素都会使 MEX 增加 $ 1 $，从而使分数增加 $ 1 $。如果我们添加 $ j $，MEX 不会增加。此外，当我们添加一个元素时，分数的增加不会超过 $ 1 $。添加少于 $ j $ 的元素无法增加未来数组的 MEX。

所以我们可以枚举分区数\(k\)，对\(k\)分区下的最大\(\text{mex}\)进行贡献计算

对于\(i\lt \text{mex}\)的方案选择总数的贡献为 \(f_i= \sum_{k=j}^{cnt_i} C _{cnt_i}^{k} \cdot f_{i-1}\)

对于\(i\gt mex\)的方案选择总数的贡献为\(2^{\sum_{j=mex}^{n}{cnt_j}}\)，我们可以使用后缀数组快速求出

最后把两者相乘加入答案

代码实现

void solve()
{
    int n;
    cin >> n;
    vector<int> cnt(n);
    // 统计数组 a 中每个值的出现频次
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        cnt[x]++;
    }

    vector<int> suf(n); // suf 数组用于存储从第 i 个位置开始，到数组末尾的后缀积
    suf[n - 1] = 1;     // 最后一个元素的后缀积设为 1，因为 suf 数组是为每个位置计算贡献做准备的

    // 逆序计算每个位置的后缀积， suf[i] 表示从位置 i 到末尾，每个 mex 值增加的贡献倍数
    for (int i = n - 2; i >= 0; i--)
    {
        suf[i] = suf[i + 1] * qmi(2, cnt[i + 1]) % mod;
    }

    ll ans = 0;            // 最终答案
    vector<ll> f(n);       // f 数组用于记录每个元素对当前 MEX 的贡献
    vector<int> num = cnt; // num 用来逐步减少每个元素的频次，以此来模拟分区过程
    int p = 0;             // 指针 p 用来追踪当前 MEX 的上限

    // 枚举分区数 k，k 从 n 开始逐步减少到 1
    for (int k = n; k >= 1; k--)
    {
        // 找到最大的满足 cnt[p] >= k 的 p 值，p 用于控制当前可以包含的 mex 最大值
        while (p < n && cnt[p] >= k)
        {
            p++; // p 逐步向右移动，直到找到第一个 cnt[p] < k 的元素
        }
        ll res = 1; // 当前分区中子序列贡献的乘积，初始为 1

        // 遍历 [0, p-1] 区间的元素，计算它们的贡献
        for (int i = 0; i < p; i++)
        {
            // num[i] 表示元素 i 还能使用的剩余次数，如果 num[i] >= k，说明该元素还能进入分区
            while (num[i] >= k)
            {
                // 使用组合数计算 cnt[i] 中取出 num[i] 次的方法数，并累加到 f[i] 中
                f[i] = (f[i] + C(cnt[i], num[i])) % mod;
                num[i]--; // 每次使用完 num[i]，它的频次就减少 1
            }
            // 将每个元素 i 的贡献乘以 res，更新 res
            res = res * f[i] % mod;
            // 将当前分区的贡献加到总答案中，同时乘以 suf[i] 表示后缀的贡献
            ans = (ans + res * suf[i] % mod) % mod;
        }
    }
    cout << ans << endl;
}

这场掉100多分，爆炸

标签：typedef,int,题解,Codeforces,979,leq,测试用例,n0,include
From： https://www.cnblogs.com/extractstars/p/18488257

相关文章

  • P11211 随机数生成器 题解
    前置知识：原根，exCRT。首先\(t=1\)是容易的，直接相邻的除一下即可。否则考虑询问除连续的\(5\)个数，分别为\(a_0,a_1,\cdots,a_4\)。首先特判掉存在\(a_i=0\)的情况，此时直接枚举\(s\)即可。我们先求出\(p\)的一个原根\(g\)，设离散对数\(\log(x)=y\)表示\(g^y\equiv......
  • 牛客周赛Round64-B题题解
    牛客周赛Round64-B题题解题目描述:小红拿到了一个正整数，请你帮小红将其表示为幂（a^b）的形式。输入描述:一个正整数2<=x<=10^5输出描述:`第一行输出x。接下来每一行输出一个幂的表达式。请按指数从小到大的顺序输出。示例1输入16输出16=16^1=4^2=2^4解题思路:......
  • 【秋招笔试-支持在线评测】10.19京东秋招(已改编)-三语言题解
    ......
  • 【秋招笔试-支持在线评测】10.19小米秋招(已改编)-研发岗题解
    ......
  • [20241024] T3 题解
    细节挺多的。题意有一个长度为\(n\)的数组\(a\)和一个长度为\(m\)的队列\(q\)，初始时\(q\)中的元素和为\(0\)。对\(x=1,2,\cdots,n\)进行如下操作：如果队首元素\(q_1<a_x\)，则\(q\)弹出队首，将\(a_x\)插入队尾。在操作结束后，定义数组\(a\)的权值为\(q\)......
  • Codeforces Round 979 (Div. 2) C. A TRUE Battle
    题目链接：题目大意：Alice和Bob先后轮流向一串01字符串中加入or或and，前者想让结果为1后者想让结果为0，问Alice能不能赢。思路：对于相同的两个布尔值，or和and都不能改变它们，而对于Alice，他倾向于向01之间加入or，Bob则想加入and。一开始我想比较1和0的多少不就行了吗，但是不对，当你......
  • Codeforces Round 979 (Div. 2) B. Minimise Oneness
    题目链接：题目大意：构造长度为nnn的01字符串，使得全为零的子序列和至少有一个1的子序列的数量之差的绝对值最小。思路：很明显，所有子序列中不是全为0就是至少有一个1，所以算......
  • Codeforces Round 980 (Div. 2)
    糖丸了，什么沟史比赛A.ProfitableInterestRate初始有\(a\)个硬币，可以花费硬币开通盈利账户与非盈利账户开通盈利账户需要至少花费\(b\)个金币开通非盈利账户没有限制每在非盈利账户花费\(x\)元，盈利账户的限制\(b\)就减少\(2x\)元求最大的在盈利账户上的花......
  • 2024 ICPC Asia Taiwan Online Programming Contest题解记录
    比赛链接：https://codeforces.com/gym/105383/problemA.AnimalFarm找个最大pig，然后所有比他小的其他种类生物一直加就好了#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllmod=1e9+7;llksm(llx,lly){ llans=1; while(y) { if(y&1)......
  • P10233 [yLCPC2024] A. dx 分计算 题解
    题目大意：题目传送门共\(T\)组测试数据，每组数据给定一个字符串\(s\)和\(Q\)次询问，按照特定的赋值方式，每次询问\(l\)到\(r\)间按这样的赋值方式的总和是多少。赋值方式如下：P可得3分p可得2分G可得1分其余字符不得分题目分析：前置知识：前缀和。（没有学过的可以先......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99