Codeforces Rund 977 div2 个人题解(A~E1)

Codeforces Rund 977 div2 个人题解(A,B,C1,C2,E1)

Dashboard - Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round) - 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. Meaning Mean

每个测试的时间限制：1秒

每个测试的内存限制：256兆字节

输入：标准输入

输出：标准输出

Pak Chanek 有一个长度为 n 的正整数数组 a。因为他正在学习如何计算两个数字的取整平均值，所以他想在他的数组 a 上练习这个技能。

当数组 a 至少有两个元素时，Pak Chanek 将执行以下三步操作：

1. 选择两个不同的索引 i 和 j （1 \leq i, j \leq |a|; i \neq j），注意 |a| 表示数组 a 的当前大小。

2. 将 \lfloor \frac{a_i + a_j}{2} \rfloor 添加到数组的末尾。

3. 从数组中移除元素 a_i 和 a_j，并连接剩下的部分。

例如，假设 a = [5, 4, 3, 2, 1, 1]。如果我们选择 i=1 和 j=5，则结果数组将是 a = [4, 3, 2, 1, 3]。如果我们选择 i=4 和 j=3，则结果数组将是 a = [5, 4, 1, 1, 2]。

在所有操作完成后，数组将只包含一个元素 x。如果 Pak Chanek 进行最佳操作，找出 x 的最大可能值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 t （1 \leq t \leq 5000）。每个测试用例的描述如下。

每个测试用例的第一行包含一个整数 n （2 \leq n \leq 50）——数组 a 的长度。

每个测试用例的第二行包含 n 个整数 a_1, a_2, \ldots, a_n （1 \leq a_i \leq 10^9）——数组 a 的元素。

请注意，所有测试用例的 n 的总和没有上限。

输出

对于每个测试用例，输出一个整数：所有数字被选出后 x 的最大可能值。

示例

输入

3
5
1 7 8 4 5
3
2 6 5
5
5 5 5 5 5

输出

6
4
5

注意

在第一个测试用例中，初始数组为 a=[1,7,8,4,5]。Pak Chanek 将执行以下操作：

1. 选择 i=1 和 j=2，然后 a=[8,4,5,4]。

2. 选择 i=3 和 j=2，然后 a=[8,4,4]。

3. 选择 i=2 和 j=3，然后 a=[8,4]。

4. 选择 i=1 和 j=2，然后 a=[6]。

在所有操作完成后，数组只包含一个元素 x=6。可以证明没有一系列操作会导致 x 超过 6。

解题思路

注意到，每一次操作都让之前所有加入的数对最后答案的贡献减半，第一次加入的数会减半n-1次，

第二次加入的数会减半n-2次，以此类推，越晚加入的数减半的次数越少。

所以我们只要对数组进行排序，从小到大进行操作即可。

代码实现

void solve()
{
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort_all(a);
    int now = a[0];
    for (int i = 1; i < n; i++)
    {
        now = (now + a[i]) / 2;
    }
    cout << now << endl;
}

---

B. Maximize Mex

每个测试的时间限制：1秒

每个测试的内存限制：256兆字节

输入：标准输入

输出：标准输出

你有一个长度为 n 的正整数数组 a 和一个整数 x。你可以进行以下两个步骤的操作任意（可能为零）次数：

1. 选择一个索引 i (1 \leq i \leq n)。

2. 将 a_i 增加 x，也就是说 a_i := a_i + x。

如果你优化地执行这些操作，求数组 a 的 \operatorname{MEX} 的最大值。

\operatorname{MEX}（最小缺失值）是数组中最小的非负整数且不在数组中的值。例如：

• [2,2,1] 的 \operatorname{MEX} 是 0，因为 0 不在数组中。

• [3,1,0,1] 的 \operatorname{MEX} 是 2，因为 0 和 1 都在数组中，但 2 不在。

• [0,3,1,2] 的 \operatorname{MEX} 是 4，因为 0, 1, 2 和 3 都在数组中，但 4 不在。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 t (1 \le t \le 5000)。每个测试用例的描述如下。

每个测试用例的第一行包含两个整数 n 和 x (1 \le n \le 2 \cdot 10^5; 1 \le x \le 10^9) — 数组的长度和用于操作的整数。

每个测试用例的第二行包含 n 个整数 a_1, a_2, \ldots, a_n (0 \le a_i \le 10^9) — 给定的数组。

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

输出

对于每个测试用例，输出一个整数：如果你优化地执行操作，数组 a 的 \operatorname{MEX} 的最大值。

示例

输入

3
6 3
0 3 2 1 5 2
6 2
1 3 4 1 0 2
4 5
2 5 10 3

输出

4
6
0

注意

在第一个测试用例中，数组 a 的 \operatorname{MEX} 是 4，无需执行任何操作，这是最大的可能值。

在第二个测试用例中，数组 a 的 \operatorname{MEX} 是 5，无需执行任何操作。如果我们执行两次操作，都选择 i=1，则数组将变为 a=[5,3,4,1,0,2]。然后，数组 a 的 \operatorname{MEX} 将变为 6，这是最大的可能值。

在第三个测试用例中，数组 a 的 \operatorname{MEX} 是 0，无需执行任何操作，这是最大的可能值。

解题思路

观察发现，对于每一个数字a_i而言，我们都只能将它变成k_i \cdot x+a_i\mod d,k_i \ge \frac{a_i}{x}的形式。所以我们可以对a_i按照a_i \mod x进行分类存进map中。

枚举mex，并计算k=\frac {mex}{x}和r=mex \mod x。查找map[r]中是否有至少k个数小于等于mex，是的话mex+1，否则不再枚举。

查找是否有k个数小于mex可以直接对map[r]中的数进行排序

时间复杂度为O(nlogn)

代码实现

void solve()
{
    ll n, x;
    cin >> n >> x;
    vl a(n);
    map<ll, vl> mp;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort_all(a);
    for (int i = 0; i < n; i++)
    {
        mp[a[i] % x].pb(a[i]);
    }
    ll mex = 0;
    while (true)
    {
        ll r = mex % x;
        ll k = mex / x;
​
        if (mp[r].size() > k && mp[r][k] <= r + k * x)
            mex++;
        else
            break;
    }
​
    cout << mex << "\n";
}

---

C1. Adjust The Presentation (Easy Version)

时间限制：每个测试 2 秒

内存限制：每个测试 256 兆字节

输入：标准输入

输出：标准输出

这是问题的简单版本。在两个版本中，q 的约束和时间限制不同。在此版本中，q=0。只有在解决了所有版本的问题后，您才能进行黑客攻击。

一个由 n 名成员组成的团队，编号从 1 到 n，准备在一个大型会议上展示幻灯片。幻灯片包含 m 张幻灯片。

有一个长度为 n 的数组 a。成员最初按顺序排列为 a_1, a_2, \ldots, a_n，从前到后。幻灯片展示将按顺序从幻灯片 1 到幻灯片 m 展示。每个部分将由队伍最前面的成员进行展示。在每张幻灯片展示后，您可以将最前面的成员移动到队伍中的任意位置（不改变其他成员的顺序）。例如，假设成员的队伍是 [\color{red}{3},1,2,4]。在成员 3 展示当前幻灯片后，您可以将队伍改为 [\color{red}{3},1,2,4]、[1,\color{red}{3},2,4]、[1,2,\color{red}{3},4] 或 [1,2,4,\color{red}{3}]。

还有一个长度为 m 的数组 b。如果可以在这些约束下使得成员 b_i 在所有 i 从 1 到 m 的情况下展示幻灯片，那么该幻灯片展示被认为是好的。

然而，您讨厌的老板希望对数组 b 进行 q 次更新。在第 i 次更新中，他将选择一张幻灯片 s_i 和一个成员 t_i，并设置 b_{s_i} := t_i。请注意，这些更新是持久的，即对数组 b 的更改将在处理未来的更新时生效。

对于数组 b 的每个状态（初始状态和每次 q 次更新之后），判断幻灯片展示是否良好。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 t (1 \le t \le 10^4)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 n, m 和 q (1 \le n, m \le 2 \cdot 10^5; q=0) — 成员的数量、部分的数量和更新的数量。

每个测试用例的第二行包含 n 个整数 a_1,a_2,\ldots,a_n (1 \le a_i \le n) — 从前到后的成员初始顺序。保证 1 到 n 的每个整数恰好出现一次在 a 中。

每个测试用例的第三行包含 m 个整数 b_1, b_2, \ldots, b_m (1 \le b_i \le n) — 每个部分应该展示的成员。

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

输出

对于每个测试用例，输出 q+1 行，对应于数组 b 的 q+1 个状态。如果幻灯片展示是好的，输出 "YA"，否则输出 "TIDAK"。

您可以以任意大小写输出答案（大写或小写）。例如，字符串 "yA"、"Ya"、"ya" 和 "YA" 都将被识别为正面响应。

示例

输入

3
4 2 0
1 2 3 4
1 1
3 6 0
1 2 3
1 1 2 3 3 2
4 6 0
3 1 4 2
3 1 1 2 3 4

输出

YA
YA
TIDAK

注意

在第一个测试用例中，您不需要移动成员，因为两张幻灯片都是由成员 1 展示的，他已经在队伍前面。

在第二个测试用例中，以下是可能的移动成员的方式，使得演示是好的：

1. [1,2,3]，不移动成员 1。

2. [1,2,3]，在成员 3 之后移动成员 1。

3. [2,3,1]，在成员 3 之后移动成员 2。

4. [3,2,1]，不移动成员 3。

5. [3,2,1]，在成员 1 之后移动成员 3。

6. [2,1,3]，不移动成员 2。

解题思路

对于初始顺序中的每一个成员，他在播放序列中第一次出现的位置一定会大于他的上一个成员在播放序列中的位置，所以我们只需要开一个位置数组，初始化为inf，然后遍历播放序列存储每一个成员第一次出现的位置，如果出现降序的数对，直接输出不可行即可。

代码实现

const string t1 = "YA";
const string t2 = "TIDAK";
void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
​
    vi a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    vi seq(m + 1);
    vi pos(n + 1, inf);
​
    for (int i = 1; i <= m; i++)
    {
        cin >> seq[i];
        if (pos[seq[i]] == inf)
            pos[seq[i]] = i;
    }
    for (int i = 2; i <= n; i++)
    {
        int cur = a[i];
        int pre = a[i - 1];
        if ((pos[cur] != inf && pos[pre] == inf) || pos[cur] < pos[pre])
        {
            cout << t2 << "\n";
            return;
        }
    }
    cout << t1 << "\n";
}

---

C2. Adjust The Presentation (Hard Version)

时间限制：每个测试 5 秒

内存限制：每个测试 256 兆字节

输入：标准输入

输出：标准输出

这是问题的困难版本。在两个版本中，q 的约束和时间限制不同。在此版本中，0 \leq q \leq 2 \cdot 10^5。只有在解决了所有版本的问题后，您才能进行黑客攻击。

一个由 n 名成员组成的团队，编号从 1 到 n，准备在一个大型会议上展示幻灯片。幻灯片包含 m 张幻灯片。

有一个长度为 n 的数组 a。成员最初按顺序排列为 a_1, a_2, \ldots, a_n，从前到后。幻灯片展示将按顺序从幻灯片 1 到幻灯片 m 展示。每个部分将由队伍最前面的成员进行展示。在每张幻灯片展示后，您可以将最前面的成员移动到队伍中的任意位置（不改变其他成员的顺序）。例如，假设成员的队伍是 [\color{red}{3},1,2,4]。在成员 3 展示当前幻灯片后，您可以将队伍改为 [\color{red}{3},1,2,4]、[1,\color{red}{3},2,4]、[1,2,\color{red}{3},4] 或 [1,2,4,\color{red}{3}]。

还有一个长度为 m 的数组 b。如果可以在这些约束下使得成员 b_i 在所有 i 从 1 到 m 的情况下展示幻灯片，那么该幻灯片展示被认为是好的。

然而，您讨厌的老板希望对数组 b 进行 q 次更新。在第 i 次更新中，他将选择一张幻灯片 s_i 和一个成员 t_i，并设置 b_{s_i} := t_i。请注意，这些更新是持久的，即对数组 b 的更改将在处理未来的更新时生效。

对于数组 b 的每个状态（初始状态和每次 q 次更新之后），判断幻灯片展示是否良好。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 t (1 \le t \le 10^4)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 n, m 和 q (1 \le n, m \le 2 \cdot 10^5; 0 \leq q \leq 2 \cdot 10^5) — 成员的数量、部分的数量和更新的数量。

每个测试用例的第二行包含 n 个整数 a_1,a_2,\ldots,a_n (1 \le a_i \le n) — 从前到后的成员初始顺序。保证 1 到 n 的每个整数恰好出现一次在 a 中。

每个测试用例的第三行包含 m 个整数 b_1, b_2, \ldots, b_m (1 \le b_i \le n) — 每个部分应该展示的成员。

接下来的 q 行，每行包含两个整数 s_i 和 t_i (1 \le s_i \le m, 1 \le t_i \le n) — 更新的参数。

保证所有测试用例中 n 的总和、m 的总和以及 q 的总和不超过 2 \cdot 10^5。

输出

对于每个测试用例，输出 q+1 行，对应于数组 b 的 q+1 个状态。如果幻灯片展示是好的，输出 "YA"，否则输出 "TIDAK"。

您可以以任意大小写输出答案（大写或小写）。例如，字符串 "yA"、"Ya"、"ya" 和 "YA" 都将被识别为正面响应。

示例

输入：

3
4 2 2
1 2 3 4
1 1
1 2
1 1
3 6 2
1 2 3
1 1 2 3 3 2
3 3
2 2
4 6 2
3 1 4 2
3 1 1 2 3 4
3 4
4 2

输出：

YA
TIDAK
YA
YA
TIDAK
YA
TIDAK
YA
YA

注意

在第一个测试用例中，您不需要移动成员，因为两张幻灯片都是由成员 1 展示的，他已经在队伍前面。之后设置 b_1 := 2，此时第 1 张幻灯片必须由成员 2 展示，但这是不可能的，因为成员 1 将首先展示幻灯片 1。然后设置 b_1 = 1，此时 b 和初始的 b 相同，使得演示可以顺利进行。

解题思路

与C1的思路一致，对于每一个成员，他在播放序列中第一次出现的位置一定会大于他的上一个成员在播放序列中的位置，所以我们只需要维护有存在多少对顺序是不合法顺序，每次操作后对其进行更新，当不合法对数为零的时候即为"YA"。

代码实现

const string t1 = "YA";
const string t2 = "TIDAK";
​
void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
​
    vi a(n + 1);
    vi pos_a(n + 1, 0); // pos_a[x] 存储成员x在队伍中的位置
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        pos_a[a[i]] = i;
    }
​
    vi b(m + 1);
    for (int i = 1; i <= m; ++i)
    {
        cin >> b[i];
    }
​
    // occ[x] 存储成员x在b数组中出现的所有幻灯片位置（有序）
    vector<set<int>> occ(n + 1, set<int>());
    for (int i = 1; i <= m; ++i)
    {
        occ[b[i]].insert(i);
    }
​
    // f[x] 存储成员x在b数组中第一次出现的位置，如果x不出现，则设为m+1
    vi f(n + 1, m + 1);
    for (int x = 1; x <= n; ++x)
    {
        if (!occ[x].empty())
            f[x] = *occ[x].begin();
    }
​
    // bad[i] 表示成员a[i]和a[i+1]的展示顺序是否不合法（即f[a[i]] > f[a[i+1]])
    vector<bool> bad(n, false);
    // 记录不合法的成员对数量
    int cnt = 0;
    for (int i = 1; i < n; ++i)
    {
        if (f[a[i]] > f[a[i + 1]])
        {
            bad[i] = true; // 标记第i对成员顺序不合法
            cnt++;         // 不合法对数量加1
        }
    }
​
    if (cnt == 0)
        cout << t1 << "\n"; // 如果没有不合法对，输出"YA"
    else
        cout << t2 << "\n"; // 否则，输出"TIDAK"
​
    // 处理每一次更新操作
    for (int i = 0; i < q; ++i)
    {
        int s, t;
        cin >> s >> t;
​
        int las = b[s]; // 记录更新前第s张幻灯片展示的成员
        int nex = t;    // 更新后要展示的成员
​
        if (las == nex)
        {
            // 如果更新前后成员相同，展示顺序不变
            if (cnt == 0)
                cout << t1 << "\n";
            else
                cout << t2 << "\n";
            continue;
        }
​
        // 从成员las的出现集合中移除位置s
        occ[las].erase(s);
        if (!occ[las].empty())
            f[las] = *occ[las].begin(); // 更新成员las的第一次出现位置
        else
            f[las] = m + 1; // 如果成员las不再出现在b中，设为m+1
​
        // 将位置s加入成员nex的出现集合
        occ[nex].insert(s);
        if (s < f[nex])
            f[nex] = s; // 如果s小于当前成员nex的第一次出现位置，更新f[nex]
        b[s] = nex;     // 更新b数组中第s张幻灯片展示的成员为nex
​
        // 获取成员las和nex在初始排列中的位置
        int pos_las = pos_a[las];
        int pos_nex = pos_a[nex];
​
        // temp集合存储需要检查的相邻成员对的位置
        set<int> temp;
        if (pos_las > 1)
            temp.insert(pos_las - 1); // 检查pos_las-1和pos_las的成员对
        if (pos_las < n)
            temp.insert(pos_las); // 检查pos_las和pos_las+1的成员对
        if (pos_nex > 1)
            temp.insert(pos_nex - 1); // 检查pos_nex-1和pos_nex的成员对
        if (pos_nex < n)
            temp.insert(pos_nex); // 检查pos_nex和pos_nex+1的成员对
​
        // 遍历所有需要检查的相邻成员对，更新不合法对的计数
        for (auto idx : temp)
        {
            int u = a[idx];            // 成员u在位置idx
            int v = a[idx + 1];        // 成员v在位置idx+1
            bool was_bad = bad[idx];   // 记录之前是否不合法
            bool is_bad = f[u] > f[v]; // 计算当前是否不合法
​
            if (was_bad != is_bad)
            {
                if (is_bad)
                    cnt++; // 如果现在变为不合法，对数加1
                else
                    cnt--;         // 如果现在变为合法，对数减1
                bad[idx] = is_bad; // 更新bad数组中的状态
            }
        }
​
        // 根据更新后的不合法对数量，输出结果
        if (cnt == 0)
            cout << t1 << "\n";
        else
            cout << t2 << "\n";
    }
}

---

D. Boss, Thirsty

时间限制：每个测试 2 秒

内存限制：每个测试 256 兆字节

输入：标准输入

输出：标准输出

Pak Chanek 的朋友在食堂经营饮料摊，计划在接下来的 n 天内售卖饮料。每一天，有 m 种不同类型的饮料售卖，并且第 i 天售卖第 j 种饮料的利润为 A_{i,j}。这个利润可能为负数，这意味着卖这种饮料可能会造成亏损。

为了帮助朋友最大化利润，Pak Chanek 每天必须选择售卖 至少一种 类型的饮料。售卖的饮料类型必须构成一个子数组，即每天选择一个区间 [i, j] 使得 1 \leq i \leq j \leq m，在这个区间内所有类型的饮料都会被售卖。

此外，为了保证每天的顾客持续回流，销售计划必须满足以下条件：

• 第 i 天（i > 1）售卖的饮料类型中，至少有一种类型在第 i-1 天也有售卖。

• 第 i 天售卖的饮料类型中，至少有一种类型在第 i-1 天没有售卖。

每天的利润是售卖饮料的总利润，目标是找到一个销售计划，使得在 n 天的销售计划中，总利润最大化。

输入

每个测试包含多组测试用例。

第一行是测试用例的数量 t (1 \leq t \leq 1000)。

每个测试用例的第一行包含两个整数 n 和 m (1 \leq n \leq 2 \cdot 10^5; 3 \leq m \leq 2 \cdot 10^5; 且 n \cdot m \leq 2 \cdot 10^5)，分别表示天数和饮料的种类数。

接下来的 n 行中，每行包含 m 个整数 A_{i,1}, A_{i,2}, \ldots, A_{i,m} (-10^9 \leq A_{i,j} \leq 10^9)，表示每种饮料在当天的预期利润。

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

输出

对于每个测试用例，输出一个整数，表示 Pak Chanek 可以获得的最大总利润。

示例

输入

1
3 6
79 20 49 5 -1000 500
-105 9 109 24 -98 -499
14 47 12 39 23 50

输出

475

解释

Note

对于给定的例子，Pak Chanek 的最佳销售计划是：

• 第 1 天售卖饮料类型 1 到 3，总利润为 79 + 20 + 49 = 148。

• 第 2 天售卖饮料类型 2 到 4，总利润为 9 + 109 + 24 = 142。

• 第 3 天售卖饮料类型 1 到 6，总利润为 185。

因此，总利润为 148 + 142 + 185 = 475。

解题思路

使用两个动态规划数组 dpl和 dpr，分别表示当前天选择的区间以某个位置结尾或开始时的最大利润。

对于第一天，直接计算每个可能区间的利润并初始化 dpl 和 dpr。

计算出前缀最小前缀和pmn和后缀最小后缀和smx，通过前一天的 dpl 和 dpr，结合当前天的 pre、pmn 和 smx，更新当前天的 dpl 和 dpr。

更新 dpl[j]

• 遍历从右到左，考虑如果当前天的区间以 j 结尾，可以从前一天的某个区间转移过来。

• 更新 ndpl[j] 为前一天的 dpr[j] + smx[j + 1] 与当前天的 pre[j] 之间的差值。

更新 dpr[j]

• 遍历从左到右，考虑如果当前天的区间以 j 开始，可以从前一天的某个区间转移过来。

• 更新 ndpr[j] 为前一天的 dpl[j] - pmn[j - 1] 与当前天的 pre[j + 1] 之间的和。

在处理完所有天数后，遍历最后一天的 dpl 和 dpr，找到其中的最大值，即为最大总利润。

看哥哥的提交看的思路，有空补吧

---

E1. Digital Village (Easy Version)

时间限制：每个测试 2 秒

内存限制：每个测试 256 兆字节

输入：标准输入

输出：标准输出

这是问题的简单版本。在三个版本中，n 和 m 的约束不同。只有在解决了所有版本的问题后，您才能进行黑客攻击。

Pak Chanek 正在为 Khuntien 村庄建立互联网连接。村庄可以表示为一个有 n 座房子和 m 条网络电缆的连接图，每条电缆连接房子 u_i 和房子 v_i，延迟为 w_i。

有 p 座房子需要互联网。Pak Chanek 可以在最多 k 座房子中安装服务器。需要互联网的房子将连接到其中一台服务器。但是，由于每条电缆都有其延迟，某个需要互联网的房子 s_i 体验到的延迟是其与所连接服务器之间的电缆的 最大 延迟。

对于每个 k = 1,2,\ldots,n，帮助 Pak Chanek 确定所有需要互联网的房子可以达到的最小 总 延迟。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 t (1 \le t \le 100)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 n, m, p (2 \le n \le 400; n-1 \le m \le 400; 1 \le p \le n) — 房子的数量、电缆的数量和需要互联网的房子的数量。

每个测试用例的第二行包含 p 个整数 s_1, s_2, \ldots, s_p (1 \le s_i \le n) — 需要互联网的房子。保证 s 中所有元素互不相同。

接下来每个测试用例的 m 行中的第 i 行包含三个整数 u_i, v_i 和 w_i (1 \le u_i < v_i \le n; 1 \le w_i \le 10^9) — 连接房子 u_i 和房子 v_i 的网络电缆，延迟为 w_i。保证给定的边形成一个连通的简单图。

保证所有测试用例中 n^3 和 m^3 的总和不超过 10^8。

输出

对于每个测试用例，输出 n 个整数：对于每个 k = 1,2,\ldots,n，所有需要互联网的房子可以达到的最小总延迟。

示例

输入

2
9 8 5
2 5 6 8 9
1 2 1
1 3 2
3 4 10
4 5 3
4 6 5
1 7 10
7 8 4
7 9 2
3 3 2
3 1
1 2 1
2 3 3
1 3 2

输出

34 19 9 4 0 0 0 0 0
2 0 0

解释

在第一个测试用例中，对于 k=3 时，可能的最优解决方案是在顶点 2、6 和 8 处安装服务器，得到以下延迟：

• \text{latency}(2) = 0

• \text{latency}(5) = \max(3, 5) = 5

• \text{latency}(6) = 0

• \text{latency}(8) = 0

• \text{latency}(9) = \max(2, 4) = 4

所以总延迟为 9。

解题思路

观察发现n\le400，可以使用n^3级别的算法，于是我们可以使用floyd先计算出所有房屋直接的最小延迟，这样我们就得到了所有需要联网的房屋与其它房屋之间的最小延迟。

由于n很小，我们可以暴力枚举每个还未放置服务器的位置，每次添加服务器选加了服务器之后总延迟最小的那个。

代码实现

void solve()
{
    int n, m, p;
    cin >> n >> m >> p;
    vi tag(p);
    for (int i = 0; i < p; i++)
    {
        cin >> tag[i];
        tag[i]--;
    }
​
    vvi dist(n, vi(n, inf));
    for (int i = 0; i < n; i++)
    {
        dist[i][i] = 0;
    }
​
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }
    // Floyd计算所有点对之间的最小延迟
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            if (dist[i][k] == inf)
                continue;
            for (int j = 0; j < n; j++)
            {
                if (dist[k][j] == inf)
                    continue;
                int d = max(dist[i][k], dist[k][j]);
                if (d < dist[i][j])
                    dist[i][j] = d;
            }
        }
    }
​
    // mn[i][j] 表示第i个需要联网的房子到第j个房子的最小最大延迟
    vvi mn(p, vi(n, inf));
    // 计算所有要联网的房子到其它房子的最小延迟
    for (int i = 0; i < p; i++)
    {
        int s = tag[i];
        for (int j = 0; j < n; j++)
        {
            mn[i][j] = dist[s][j];
        }
    }
​
    // 初始化每个需要联网的房子的当前延迟为无穷大
    vl cur(p, inf);
    // select[j] 表示是否选择了第j个房子作为服务器
    vector<bool> used(n, false);
    vl ans;
​
    // 对于k从1到n，选择k个服务器
    for (int k = 1; k <= n; k++)
    {
        ll sum = 0;   // 当前的总延迟
        int idx = -1; // 选择的服务器位置
​
        // 寻找未选择的房子中，选择一个能最大程度减少总延迟的房子作为服务器
        for (int j = 0; j < n; j++)
        {
            // 如果已经选择，跳过
            if (used[j])
                continue;
            // 计算当前服务器位置到所有需要联网的房子的最小延迟
            ll now = 0;
            for (int s = 0; s < p; s++)
            {
                // 每个需要联网的房子可以选择连接到当前服务器或者之前选择的服务器中的最小延迟
                now += min((int)cur[s], mn[s][j]);
            }
            // 选择能够使总延迟最小的服务器位置
            if (idx == -1 || now < sum)
            {
                sum = now;
                idx = j;
            }
        }
        used[idx] = true;
        // 更新每个需要联网的房子的当前延迟
        for (int s = 0; s < p; s++)
        {
            cur[s] = min((int)cur[s], mn[s][idx]);
        }
        // 计算当前k的总延迟
        sum = 0;
        for (int s = 0; s < p; s++)
        {
            sum += cur[s];
        }
        ans.push_back(sum);
        // 如果k >= p，后续的k只需要选择p个服务器，剩余选择不影响，总延迟不再变化
        if (k >= p)
        {
            // 填充剩余的k到n的结果
            while (ans.size() < n)
            {
                ans.push_back(0);
            }
            break;
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

---

E2. Digital Village (Hard Version)

困难版本中1\le t \le 2000,2 \le n \le 5000,n-1 \le m \le 5000。

解题思路

先跑一个Kruskalcg重构树，得到最小生成树，然后树进行树形dp即可

大体思路是这样，代码后面有时间补吧