D. Nene and the Mex Operator - dfs + 位运算枚举

本文主要是介绍D. Nene and the Mex Operator - dfs + 位运算枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

分析

将一段区间[l, r]变成最大，可以遵循以下规则，先对第一个数进行操作，如果他是0，那么会变成1，所以不进行操作，如果不是0，就要进行操作，让它变成0，只有这样才能让他后面的元素得到更大的结果，所以以此类推，可以让整个区间变成0，1，2，3,…r - l，对这种区间再次进行操作，就可以变成r - l + 1, r - l + 1, …, r - l + 1。
可以枚举所有情况，去看哪种情况能够得到最大的和，然后可以对这种最大的方案进行操作模拟，得到最后的数组，可以通过dfs进行模拟过程，找出过程中需要进行操作的区间。

代码

#include <bits/stdc++.h>using namespace std;
using ll = long long;void solve() {int n;cin >> n;vector<int> a(n);for(int i = 0; i < n; i ++) cin >> a[i];ll maxn = 0;int x = 0;for(int i = 0; i < (1 << n); i ++) {ll sum = 0;for(int l = 0; l < n; l ++) {if((i >> l) & 1) {int r = l + 1;while(r < n && ((i >> r) & 1)) r ++;r --;sum += (r - l + 1) * (r - l + 1);l = r;}else sum += a[l];}if(maxn < sum) {maxn = sum;x = i;}}vector<pair<int, int>> ans;auto cal = [&](int l, int r) {map<int, int> cnt;ans.push_back({l + 1, r + 1});for(int i = l; i <= r; i ++) {cnt[a[i]] ++;}int mex = 0;while(cnt[mex]) mex ++;for(int i = l; i <= r; i ++) a[i] = mex;};auto build = [&](auto self, int l, int r) -> void {//cout << l << ' ' << r << '-' << endl;if(l == r) {if(a[r]) {cal(l, r);}return ;}self(self, l, r - 1);if(a[r] != r - l) {cal(l, r);self(self, l, r - 1);}};for(int l = 0; l < n; l ++) {if((x >> l) & 1) {int r = l + 1;while(r < n && ((x >> r) & 1)) r ++;r --;build(build, l, r);cal(l, r);l = r;}}cout << maxn << ' ' << ans.size() << "\n";for(auto j: ans) cout << j.first << ' ' << j.second << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;T = 1;//cin >> T;while(T --) {solve();}
}