Codeforces Round 939 (Div. 2) D. Nene and the Mex Operator 题解 二进制枚举+递归

本文主要是介绍Codeforces Round 939 (Div. 2) D. Nene and the Mex Operator 题解 二进制枚举+递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Nene and the Mex Operator

题目描述

Nene给了你一个长度为 $n$ 的整数数组 $a_1,a_2,\dots ,a_n$ 。

你可以执行以下操作不超过 $5\cdot 10^5$ 次（可能为零）：

• 选择两个整数 $l$ 和 $r$ ，使得 $1\le l\le r\le n$ ，计算 $x$ 为 MEX ⁡ ( { a l , a l + 1 , … , a r } ) \operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\}) MEX({al​,al+1​,…,ar​}) ，同时设置 $a_l=x,a_{l+1}=x,\dots ,a_r=x$ 。

这里，整数集合 { c 1 , c 2 , … , c k } \{c_1, c_2, \ldots, c_k\} {c1​,c2​,…,ck​} 中的 $\mathrm{MEX}$ 被定义为在集合 $c$ 中不出现的最小非负整数 $m$ 。

你的目标是最大化数组 $a$ 中元素的和。找出最大和，并构建一个操作序列来实现这个和。需要注意的是，你不需要最小化这个序列中的运算次数，你只需在解决方案中使用不超过 $5\cdot 10^5$ 的运算。

输入描述

第一行包含一个整数 $n$ （ $1\le n\le 18$ ）- 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ （ $0\le a_i\le 10^7$ ）。

输出描述

在第一行中，输出两个整数 $s$ 和 $m$ ( $0\le m\le 5\cdot 10^5$ ) - 数组 $a$ 元素的最大和以及解决方案中的操作数。

在下面 $m$ 行的 $i$ -th 中，输出两个整数 $l$ 和 $r$ ( $1\le l\le r\le n$ )，代表 $i$ -th 运算的参数。

可以证明，数组 $a$ 元素的最大和总是可以通过不超过 $5\cdot 10^5$ 次的运算得到。

样例输入1

2
0 1

样例输出1

4 1
1 2

样例输入2

3
1 3 9

样例输出2

13 0

样例输入3

4
1 100 2 1

样例输出3

105 2
3 3
3 4

样例输入4

1
0

样例输出4

1 1
1 1

原题

CF Round 939——传送门

思路

对于任意一段区间$[l,r]$，我们总能进行一系列操作，使该区间的和为 $(r-l+1)\ast (r-l+1)$。所以，由于数组的长度最大为$18$，我们可以通过二进制枚举所有对区间操作的方案数，找到使得和最大的其中一种方案。找到了使和最大的方案后，需要输出对于各个区间的操作。那么我们考虑任意一段区间$[l,r]$，先将其中所有元素置$0$，因为需要将该区间转化为 { r − l + 1 , r − l + 1 , … , r − l + 1 } \{r-l+1, r-l+1, \ldots, r-l+1\} {r−l+1,r−l+1,…,r−l+1}，所以先递归得到 { r − l , r − l , … , r − l , r − l , 0 } \{r-l, r-l, \ldots, r-l , r-l,0\} {r−l,r−l,…,r−l,r−l,0}，然后将$[l,r-2]$的部分置$0$，进行不断递归，直至区间转化为 { 1 , 2 , 3 , … , r − l , 0 } \{1, 2, 3, \ldots, r-l,0\} {1,2,3,…,r−l,0}，然后再对整个区间进行一次操作，即可得到 { r − l + 1 , r − l + 1 , … , r − l + 1 } \{r-l+1, r-l+1, \ldots, r-l+1\} {r−l+1,r−l+1,…,r−l+1}。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;void set_zero(int l, int r, vector<int> &a, vector<pair<int, int>> &ans)
{for (int i = l; i <= r; i++){if (a[i] != 0){ans.push_back({i, i});}}
}void set_max(int l, int r, vector<pair<int, int>> &ans)
{if (l == r){ans.push_back({l, r});return;}for (int k = r - 1; k >= l; k--){set_max(l, k, ans);if (k != l)ans.push_back({l, k - 1});}ans.push_back({l, r});
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 对于任意一段区间[l,r]，我们总能进行一系列操作，使该区间的和为 (r-l+1)*(r-l+1)// 所以，由于数组的长度最大为18，我们可以通过二进制枚举所有对区间操作的方案数，找到使得和最大的其中一种方案int n;cin >> n;vector<int> a(n);for (auto &x : a)cin >> x;vector<pair<int, int>> op;         // 记录和最大时需要操作的区间int max_sum = 0;                   // 记录最大和for (int i = 0; i < (1 << n); i++) // 二进制枚举所有区间操作方案，连续的一段1是需要进行区间操作的{ll sum = 0;                 // 当前方案的总和vector<pair<int, int>> tmp; // 当前方案需要操作的区间for (int j = 0; j < n;){if ((i >> j) & 1){int l = j;int r = j;r++;while (r < n && ((i >> r) & 1)) // 找到连续的一段1{r++;}tmp.push_back({l, r - 1});sum += (r - l) * (r - l); // 找到的区间为[l,r)j = r;}else{sum += a[j];j++;}}if (sum > max_sum){op = tmp;max_sum = sum;}}cout << max_sum << ' '; // 输出最大和// 那么下面的任务就是输出实现这种方案的所需操作vector<pair<int, int>> ans; // 记录所需操作// 先将区间元素全部置0for (int i = 0; i < op.size(); i++){set_zero(op[i].first, op[i].second, a, ans);}// 再将区间元素全部化为r-l+1for (int i = 0; i < op.size(); i++){set_max(op[i].first, op[i].second, ans);}// 输出操作cout << ans.size() << '\n';for (int i = 0; i < ans.size(); i++){cout << ans[i].first + 1 << ' ' << ans[i].second + 1 << '\n';}return 0;
}

这篇关于Codeforces Round 939 (Div. 2) D. Nene and the Mex Operator 题解 二进制枚举+递归的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---