D. Nene and the Mex Operator
题意
给定一个长度为 n n n 的正整数数组 a a a,定义操作:
- 选定一个区间 [ l , r ] [l, r] [l,r],将区间内的数字替换成: m e x ( a l , a l + 1 , . . . , a r ) mex(a_l,a_{l+1},...,a_r) mex(al,al+1,...,ar)
要求在不超过 5 ⋅ 1 0 5 5\cdot 10^5 5⋅105 次操作下, 最大化数组的和
思路
首先需要注意到一个很关键的点:对于一个长度为 l e n len len 的区间 [ l , r ] [l,r] [l,r],不管怎样对这个区间操作,最终这个区间的每个数最大就是 l e n len len,排除掉 a i a_i ai 本身就比 l e n len len 大的情况
这是因为如果要产生 m e x = l e n mex = len mex=len,那么就需要 0 , 1 , . . . , l e n − 1 0,1,...,len - 1 0,1,...,len−1 共 l e n len len 个数,再大的 m e x mex mex 值区间长度就不够放了
因此我们可以大胆猜测(对构造题很重要):一个长度为 l e n len len 的区间可以构造出 l e n len len 个 a i = l e n a_i = len ai=len,也就是最后一次操作是 [ l , r ] [l,r] [l,r],且 m e x = l e n mex = len mex=len
如何操作?我们将区间移动到前缀 [ 1 , l e n ] [1,len] [1,len],就是对应代码 s o l v e ( k , p ) solve(k, p) solve(k,p) 函数, k = l e n k = len k=len, p = l p = l p=l,表示将前 k k k 个数变为全 k k k 需要的操作
注意在每次进入 s o l v e solve solve 之前,我们需要保证区间全零
具体原理就是: a k = 0 a_k = 0 ak=0 不动,先递归求解 s o l v e ( k − 1 ) solve(k - 1) solve(k−1),现在 [ 1 , k − 1 ] [1, k - 1] [1,k−1] 全为 k − 1 k - 1 k−1
然后我们将 [ 1 , k − 2 ] [1, k - 2] [1,k−2] 设置为全零,再递归求解 s o l v e ( k − 2 ) solve(k -2) solve(k−2),保持 a k − 1 = k − 1 a_{k - 1} = k - 1 ak−1=k−1 不变
一直循环下去,直到前缀为: 1 , 2 , 3 , . . . . , k − 1 , 0 1,2,3,...., k - 1,0 1,2,3,....,k−1,0,这时 m e x mex mex 就等于 k k k 了
这样子递归操作的次数大约为 O ( 2 n ) O(2 ^ n) O(2n)
这是因为: s o l v e ( k ) solve(k) solve(k) 要调用一次 s o l v e ( k − 1 ) solve(k - 1) solve(k−1),而后调用 s o l v e ( k − 2 ) → s o l v e ( 1 ) solve(k - 2) \rarr solve(1) solve(k−2)→solve(1),
而 s o l v e ( k − 1 ) solve(k -1) solve(k−1) 也会调用 s o l v e ( k − 2 ) → s o l v e ( 1 ) solve(k - 2) \rarr solve(1) solve(k−2)→solve(1),因此 s o l v e ( k ) solve(k) solve(k) 大于是 s o l v e ( k − 1 ) solve(k - 1) solve(k−1) 调用次数的 2 2 2 倍,也就是说,这是一个公比大约为 2 2 2 的等比数列
得出这个结论和构造方式后,我们就可以采用状压二进制枚举操作的区间,其余保留原值即可
// Problem: D. Nene and the Mex Operator
// Contest: Codeforces - Codeforces Round 939 (Div. 2)
// URL: https://codeforces.com/contest/1956/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
const int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;
typedef long long ll;
std::vector<std::pair<int, int>> opt;
void solve(int k, int p){
if(k == 1){
opt.push_back({p, p});
return;
}
solve(k - 1, p);
for(int i = k - 2; i > 0; --i){
opt.push_back({p, p + i - 1}); //turn [1, i] to 0
solve(i, p);
}
opt.push_back({p, p + k - 1});
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n);
fore(i, 0, n) std::cin >> a[i];
int ans = 0;
int sta = 0;
fore(S, 0, 1 << n){
std::vector<bool> v(n);
fore(j, 0, n) v[j] = (S >> j & 1);
int sum = 0;
int len = 0;
fore(i, 0, n){
if(!v[i]){
sum += len * len;
len = 0;
sum += a[i];
}
else ++len;
}
sum += len * len;
if(sum > ans){
ans = sum;
sta = S;
}
}
std::vector<std::pair<int, int>> vec;
int i = 0;
int l = -1;
while(i < n){
if(!(sta >> i & 1)){
if(l != -1) vec.push_back({l + 1, i});
l = -1;
}
else if(l == -1) l = i;
++i;
}
if(l != -1) vec.push_back({l + 1, n});
for(auto [l, r] : vec){
fore(p, l, r + 1)
if(a[p - 1])
opt.push_back({p, p}); //turn a[p] to 0
solve(r - l + 1, l);
}
std::cout << ans << ' ' << opt.size() << endl;
for(auto [l, r] : opt) std::cout << l << ' ' << r << endl;
return 0;
}