Codeforces Round 980 div2 个人题解(A~D)

news/2024/10/21 4:22:22

Codeforces Round 980 div2 个人题解(A~D)

Dashboard - Codeforces Round 980 (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. Profitable Interest Rate

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

Alice 有 $a$ 个硬币。她可以开立一个名为“盈利”的银行存款，但开立此存款所需的最低金额为 $b$ 个硬币。

还有一个名为“无利可图”的存款，可以用任意数量的硬币开立。Alice 注意到，如果她用 $x$ 个硬币开立“无利可图”存款，则开立“盈利”存款所需的最低金额会减少 $2x$ 个硬币。但是，这些硬币以后不能存入“盈利”存款。

如果 Alice 首先将一定数量的硬币（可能是 0）存入“无利可图”存款，请帮助她确定她可以存入“盈利”存款的最大硬币数量。如果 Alice 永远无法开立“盈利”存款，则输出 0。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $t$ $(1 \leq t \leq 10^4)$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的一行包含两个整数 $a$ 和 $b$ $(1 \leq a, b \leq 10^9)$ — Alice 拥有的硬币数量以及开立“盈利”存款所需的初始最低金额。

输出

对于每个测试用例，输出一个整数 — Alice 可以存入“盈利”存款的最大硬币数量。如果 Alice 永远无法开立“盈利”存款，则输出 0。

示例

输入

输出

注意

在第一个测试案例中，$a \geq b$，因此 Alice 可以立即用所有 10 个硬币开立“盈利”存款。

在第二个测试案例中，Alice 可以用 2 个硬币开立“无盈利”存款。然后她将剩下 5 个硬币，但开立“盈利”存款所需的最低金额将减少 4 个硬币，使其等于 5 个硬币。因此，Alice 将能够用 5 个硬币开立“盈利”存款。

在第三个测试案例中，Alice 将无法开立“盈利”存款。

解题思路

根据题目要求列出公式$a-x=b-2x$，移项得$x=b-a$。再特判一下极端情况即可。

代码实现

void solve()
{ll a, b;cin >> a >> b;if (a >= b){cout << a << endl;return;}else if (a * 2 <= b){cout << 0 << endl;return;}int d = b - a;cout << a - d << endl;
}

B. Buying Lemonade

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

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

输入：标准输入

输出：标准输出

有一台出售柠檬水的自动售货机。这台机器共有 $n$ 个槽位。你知道最初，第 $i$ 个槽位包含 $a_i$ 罐柠檬水。机器上还有 $n$ 个按钮，每个按钮对应一个槽位，每个槽位对应一个按钮。不幸的是，按钮上的标签已经磨损，所以你不知道哪个按钮对应哪个槽位。

当你按下与第 $i$ 个槽位对应的按钮时，会发生以下两种情况之一：

如果第 $i$ 个槽位中有一罐柠檬水，它会掉出来，你会拿走它。此时，第 $i$ 个槽位中的罐子数量减少了 $1$。
如果第 $i$ 个槽位中没有剩余的柠檬水罐，则不会掉出任何东西。

按下按钮后，罐子会快速掉出，因此无法追踪它从哪个槽位掉落。槽位的内容隐藏在您的视野之外，因此您无法看到每个槽位中剩余的罐子数量。您唯一知道的是槽位中的初始罐子数量： $a_1, a_2, \ldots, a_n$。

确定需要按下的最少按钮次数，以保证您至少收到 $k$ 罐柠檬水。

请注意，您可以根据是否收到罐子来调整按钮按下时的策略。保证机器中总共至少有 $k$ 罐柠檬水。换句话说， $k \leq a_1 + a_2 + \ldots + a_n$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$) — 机器中的插槽数量和所需的柠檬水罐数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — 插槽中的罐子数量。

保证有 $k \leq a_1 + a_2 + \ldots + a_n$ ，这意味着机器中至少有 $k$ 罐柠檬水。

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

输出

对于每个测试用例，输出一个整数 — 保证您收到至少 $k$ 罐柠檬水所需的最少按钮按下次数。

示例

输入

5
2 1
1 1
2 2
1 2
3 4
2 1 3
10 50
1 1 3 8 8 9 12 13 27 27
2 1000000000
1000000000 500000000

输出

注意

在第一个测试用例中，我们可以简单地按下第一个按钮并收到一罐柠檬水。

在第二个测试用例中，我们可以按下每个按钮一次，确保我们收到 $2$ 罐柠檬水。请注意，如果我们只是按下一个按钮两次，我们可能不会幸运，那样的话按钮可能对应第一个槽位，在这种情况下我们只会收到 $1$ 罐柠檬水。

在第三个测试用例中，最优策略之一如下：

按下第一个按钮两次。第一次按下后，肯定会掉出一罐柠檬水。然后有两种选择：
1. 如果第二次按下后没有掉出柠檬水，我们知道这个按钮一定对应第二个槽位，因为 $a_2=1$ 且 $a_1, a_3 > 1$。然后我们可以按下第二个按钮两次，第三个按钮一次。由于 $a_1, a_3 \geq 2$，我们肯定会在这三次按下中收到三罐柠檬水。因此，在 $5$ 次按下后，我们将获得 $4$ 罐柠檬水。
2. 如果第二次按下后掉出了一罐柠檬水，我们可以按下第二个按钮一次，第三个按钮一次。在每次按下中，我们肯定会收到一罐柠檬水。因此，在 $4$ 次按下后，我们将获得 $4$ 罐柠檬水。

可以证明，仅用 $4$ 次按下是无法保证收到 $4$ 罐柠檬水的，因此答案是 $5$。

解题思路

对于任意一个按钮，如果我们按下之后它不再出水，那我们肯定不会再去按它。为了让我们按按钮的总次数尽量少，我们需要不去按下已经不出水的按钮。

一个显然的策略是一轮按下所有还出水的按钮即$a_i\gt now$，$now$为已经按下的次数。

为了方便维护$a_i>now$，我们可以将$a$升序排序，如果$a_i\le now$，我们可以把$i$往后挪直达$a_j>now$

观察到$a_i\le10^9$，不能一轮一轮模拟，需要使用除法加速。

代码实现

void solve()
{ll n, k;cin >> n >> k;vl a(n);for (int i = 0; i < n; i++){cin >> a[i];}sort(all(a)); // 将罐子数量排序ll len = n; // 剩余槽位数量ll ans = 0; // 按钮按下的总次数ll now = 0; // 当前获得的柠檬水数量int i = 0; // 当前槽位索引while (k){// 处理当前槽位while (a[i] <= now) // 如果当前槽位的罐子数量小于等于已获得的数量{i++;ans++; // 按下按钮len--; // 剩余槽位数量减少}// 计算当前槽位能提供的柠檬水if (k >= len) // 如果我们需要的数量大于或等于剩余槽位数量{ll t = k / len; // 每个槽位至少要按下 t 次ll cnt = min(t, a[i] - now); // 当前槽位能提供的数量ans += cnt * len; // 计算总的按钮按下次数now += cnt; // 更新已获得的数量k -= cnt * len; // 更新还需的数量}else // 如果需要的数量小于剩余槽位数量{ans += k; // 直接按下 k 次k = 0; // 更新还需的数量}}cout << ans << endl; // 输出结果
}

C. Concatenation of Arrays

时间限制：每个测试 2 秒

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

输入：标准输入

输出：标准输出

给定 $n$ 个数组 $a_1, \ldots, a_n$。每个数组的长度为 $2$，因此 $a_i = [a_{i,1}, a_{i,2}]$。您需要将这些数组连接成一个长度为 $2n$ 的数组，以使结果数组中的逆序对数量最小化。请注意，您不需要计算实际的逆序对数量。

更正式地说，您需要选择一个长度为 $n$ 的排列 $p$，以便数组 $b = [a_{p_1,1}, a_{p_1,2}, a_{p_2,1}, a_{p_2,2}, \ldots, a_{p_n,1}, a_{p_n,2}]$ 包含尽可能少的逆序对。

逆序对的定义是：数组 $c$ 中的逆序对数量是索引对 $i$ 和 $j$ 的数量，使得 $i < j$ 且 $c_i > c_j$。

一个长度为 $n$ 的排列是一个由 $n$ 个不同整数组成的数组，这些整数从 $1$ 到 $n$ 以任意顺序排列。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（$2$ 在数组中出现了两次）， $[1,3,4]$ 也不是排列（$n=3$ 但是数组中有 $4$）。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$) — 数组的数量。

接下来的每一行包含两个整数 $a_{i,1}$ 和 $a_{i,2}$ ($1 \leq a_{i,j} \leq 10^9$) — 第 $i$ 个数组的元素。

保证所有测试用例的 $n$ 的总和不超过 $10^5$。

输出

对于每个测试用例，输出 $2n$ 个整数 — 您获得的数组的元素。如果有多个解决方案，则输出其中任何一个。

示例

输入

输出

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

注意

在第一个测试用例中，我们以顺序 $2, 1$ 连接数组。考虑结果数组 $b = [2, 3, 1, 4]$ 中的逆序对：

$i=1, j=3$，因为 $b_1=2 > 1=b_3$；
$i=2, j=3$，因为 $b_2=3 > 1=b_3$。

因此，逆序对的数量是 $2$。可以证明这是可能的最小逆序对数量量。

在第二个测试用例中，我们以顺序 $3, 1, 2$ 连接数组。考虑结果数组 $b = [2, 1, 3, 2, 4, 3]$ 中的逆序对：

$i=1, j=2$，因为 $b_1=2 > 1=b_2$；
$i=3, j=4$，因为 $b_3=3 > 2=b_4$；
$i=5, j=6$，因为 $b_5=4 > 3=b_6$。

因此，逆序对的数量是 $3$。可以证明这是可能的最小逆序对数量量。

在第三个测试用例中，我们以顺序 $4, 2, 1, 5, 3$ 连接数组。

解题思路

为了确保连接后的数组尽可能减少逆序对数量，我们按以下规则进行排序。

最小值优先：首先根据每个数组的最小值进行排序，可以确保在连接数组时，较小的元素会出现在前面，从而减少后面元素大于前面元素的情况。
最大值次之：如果两个数组的最小值相同，则根据最大值进行排序。这是为了在最小值相同的情况下，进一步控制元素的相对顺序，确保较大的元素不会在较小元素之前出现。

考虑两个数组 $ a = [x_1, y_1] $ 和 $ b = [x_2, y_2] $，其中 $ x_1 \leq y_1 $ 和 $ x_2 \leq y_2 $。

排序依据：
- 如果 $ x_1 < x_2 $，那么在连接时 $ x_1 $ 会在 $ x_2 $ 之前，减少逆序对。
- 如果 $ x_1 = x_2 $，那么需要看 $ y_1 $ 和 $ y_2 $ 的大小：
  - 如果 $ y_1 < y_2 $，那么连接后 $ y_1 $ 会在 $ y_2 $ 之前，继续减少逆序对。
  - 如果 $ y_1 \geq y_2 $，则可能会增加逆序对，但由于最小值相同，造成的影响相对较小。

假设我们有以下数组：

$ a_1 = [1, 4] $
$ a_2 = [2, 3] $

如果我们不进行排序，直接连接可能得到 $ [1, 4, 2, 3] $，这里会有逆序对（例如 $ 4 > 2 $ 和 $ 4 > 3 $），逆序对数量较多。

如果我们按照最小值排序，得到的顺序是 $ a_2, a_1 $，连接后得到 $ [2, 3, 1, 4] $，这样逆序对数量明显减少。

代码实现

void solve()
{int n;cin >> n;vpii a(n);for (int i = 0; i < n; ++i){cin >> a[i].ft >> a[i].sd;}sort(all(a), [&](const pii &x, const pii &y){if(min(x.ft, x.sd) != min(y.ft, y.sd))return min(x.ft, x.sd) < min(y.ft, y.sd);return max(x.ft, x.sd) < max(y.ft, y.sd); });for (int i = 0; i < n; ++i){cout << a[i].ft << " " << a[i].sd << " \n"[i == n - 1];}
}

D. Skipping

时间限制：每个测试 2 秒

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

输入：标准输入

输出：标准输出

现在已经是3024年，题目的想法早已用尽，奥林匹克竞赛现在以经过修改的个人形式举行。奥林匹克竞赛由 $n$ 个问题组成，编号从 $1$ 到 $n$。第 $i$ 个问题有自己的分数 $a_i$ 和特定参数 $b_i$ ($1 \leq b_i \leq n$)。

最初，测试系统会给参与者第一个问题。当参与者得到第 $i$ 个问题时，他们有两个选择：

提交问题并获得 $a_i$ 分；
跳过这个问题，在这种情况下他们将永远无法提交它。

然后，测试系统从索引为 $j$ 的问题中为参与者选择下一个问题：

如果他提交了第 $i$ 个问题，则查看索引为 $j < i$ 的问题；
如果他跳过了第 $i$ 个问题，则查看索引为 $j \leq b_i$ 的问题。

在这些问题中，它选择索引为最大的问题，该问题以前没有给过参与者（他以前既没有提交过也没有跳过过）。如果没有这样的问题，则参与者的比赛结束，他们的结果等于所有提交问题的分数总和。特别是，如果参与者提交了第一个问题，则他们的比赛结束。请注意，参与者最多收到每个问题一次。

Prokhor 已经为奥林匹克竞赛做好了充分的准备，现在他可以提交任何问题。帮助他确定他可以获得的最高分数。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $t$ ($1 \leq t \leq 10^5$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 4 \cdot 10^5$) — 奥林匹克竞赛中的问题数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — 问题的分数。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq n$) — 问题的参数。

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

输出

对于每个测试用例，输出一个整数——Prokhor 可以获得的最大分数。

示例

输入

4
2
15 16
2 1
5
10 10 100 100 1000
3 4 1 1 1
3
100 49 50
3 2 2
4
100 200 300 1000
2 3 4 1

输出

注意

在第一个测试用例中，Prokhor 可以跳过第一个问题；然后他将收到索引为 $b_1=2$ 的问题。Prokhor 可以提交它并获得 $a_2=16$ 分。之后，比赛将结束，因为 Prokhor 已经收到所有问题。请注意，如果 Prokhor 提交第一个问题，他将获得 $a_1=15$ 分，但比赛会立即结束。

在第二个测试用例中，Prokhor 可以跳过第一个问题；然后他将收到索引为 $b_1=3$ 的问题。Prokhor 可以提交它并获得 $a_3=100$ 分。之后，Prokhor 将收到第二个问题，他可以跳过以接收索引为 $b_2=4$ 的问题。Prokhor 可以提交第四个问题并获得另一个 $a_4=100$ 分。之后，比赛结束，因为 Prokhor 已经收到所有索引不超过 $4$ 的问题。因此，Prokhor 将获得总共 $200$ 分。

在第三个测试用例中，Prokhor 可以提交第一个问题并获得 $100$ 分，之后比赛会立即结束。

解题思路

观察题目发现，我们最优的策略一定是经过一系列点$p_1,p_2,p_3\dots p_m$到达$p_m$后停下，然后在$p_m$跳转到所有$i\notin P,i<p_m$的点上获取它们的分数，且$\forall i\lt m,p_i\lt p_m$。如果$\exist p_j\gt p_m$那我们在$p_j$停下一定不劣于在$p_m$停下。

答案$\text{ans}=\text{min}( \text{prefix}_{p_m}-\sum^{m}_{i=1}a_{p_i}),1\le p_m\le n$

所以我们可以建图，然后跑最短路，算出到达每一个点的最小花费。

对于第一种操作，对$i\rightarrow i-1$建边，其边权为$0$

对于第二种操作，对$i\rightarrow b_i$建边，其边权为$a_i$

然后跑一遍dijkstra算出到达每一个点的最小代价

然后枚举所有可能的终点即可。

这题还有dp的做法，我有空补补。

代码实现

void solve()
{int n;cin >> n;vi a(n + 1);vl pre(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];pre[i] = pre[i - 1] + a[i];}vi b(n + 1);for (int i = 1; i <= n; i++){cin >> b[i];}vvi adj(n + 1);vvl w(n + 1);for (int i = 1; i <= n; i++){adj[i].pb(b[i]);w[i].pb(a[i]);if (i != 1){adj[i].pb(i - 1);w[i].pb(0);}}vl dis(n + 1, infll);vb vis(n + 1);dis[1] = 0;auto dijkstra = [&](){priority_queue<pll, vpll, greater<pll>> q;q.push({0, 1});while (!q.empty()){auto t = q.top();q.pop();ll d = t.ft;int u = t.sd;if (vis[u])continue;vis[u] = true;for (int i = 0; i < adj[u].size(); i++){int v = adj[u][i];ll cost = d + w[u][i];if (dis[v] > cost){dis[v] = cost;q.push({cost, v});}}}};dijkstra();ll ans = 0;for (int i = 1; i <= n; i++){ans = max(ans, pre[i] - dis[i]);}cout << ans << endl;
}

E不会写，看不懂一点，最近这几场掉大分，本来差12分上紫，结果狂掉270分，差点掉出蓝了，场场卡B和C,导致没时间写后面的了，人快麻了。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/74022.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！