CF1956D Nene and the Mex Operator 讲题综合版

· · 题解

题意：

操作方法：

Choose two integers l and r such that 1 \le l \le r \le n , compute x as \operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\}) , and simultaneously set a_l:=x, a_{l+1}:=x, \ldots, a_r:=x .

也就是说选一段 [l,r] 出来全都赋值为 \operatorname{MEX}[l,r]

Here, $ \operatorname{MEX} $ of a set of integers $ \{c_1, c_2, \ldots, c_k\} $ is defined as the smallest non-negative（非负） integer（整数） $ m $ which does not occur（出现） in the set $ c $ . --- ### Hint: > What is the answer when $a_i=0

根据 a_i=0 我们可以得出一些规律。

When a_i=0 , the sum can hit n^2 with making a_i=n at last. Construction:

//! a function which sets a_1 ... a_k into k.
function solve(k):
  if k is 1:
    operate [1,1]
    return
  end if
  solve(k-1);
  for i in [k-2, ..., 1]:
    operate [1,i] //! this sets a_1 ... a_i into 0
    solve(i)
    //! here, a should be [i, i, ..., i, i+1, i+2, ..., k-1, 0]
  end for
  //! here, a should be [1, 2, 3, ..., k-1, 0]
  operate [1,k]
  return

Here, solve(k) will take about 2^k operations.

根据如上信息，我们可以找到一些思路：

用 k 表示区间长度，对于区间 [l, r] 一旦操作，\sum _ {i = l} ^ r a_i 必定会小于等于 k^2，证明：

一个区间假设就算离散得很严重，但由于是找最小非负整数，这个最小非负整数一定会满足 x \leq k，但是若是长成 0,1,2,...k-1 那么每个数就会都变成 k，这时达到了最大 k^2 的总和。

现在面临 3 个问题：A.对于一个区间这个区间我执不执行操作。B.一个区间是否会被多次操作。C.怎么动态规划。

A.

一个区间一旦执行操作，就必须变成总和为 k^2 ,不然就亏了。或者我不操作，保留原来的样子可能还最大。

一个区间至少知道怎么算，也知道一定能把总和变成 k^2，那么操作就可以玩了，操作部分：那么就是如何变成 k^2？ 显然可以把所有数字先变成 0，再逐个变化，形如：

全都变成 0 后逐一先变出 k - 1，并保留最边上的，再变出 k - 2，保留最边上的......

link

B.

我们显然知道对于任意正整数 a+b=c，必定 a^2+b^2 \leq 2ab + a^2+b^2 = c^2 也就是 a^2+b^2<c^2。所以显然几个区间多次被变成 k^2（这里的 k 仍然是区间长度），最后合起来显然没有 [l,r] 一次性变化成 k^2（k 的意思同理）优秀。那么这样，我们就证明出来了一个非常好的性质：目标操作序列一定是不相互重合的，像是 [1,3] [5,7] [10,12]，而中间的 4,8,9（假设一共 12 个数，4,8,9 表示编号）不进行操作，因为本身的数字可能大于 n^2，比如样例：1 100 2 1 中 10 显然大于 n^2，就不进行任何操作。

C.

考虑区间 dp，dp_{l,r} 表示这段区间最大达到的长度。记 k 为中间的点。

dp_{l,r} = \operatorname{max}(dp_{l,r}, lenth_{左段}^2 + lenth_{右段}^2, dp_{l,k} + lenth_{右段}^2, lenth_{左段}^2 + dp_{k + 1, r}, dp_{l,k} + _{k + 1,r}))

那么就可以按照思路，写出求 sum 的 dp：

#include <bits/stdc++.h>
using namespace std;
int n;
int dp[20][20]; // 段 l, r 能达到的最大值。
int a[20];

int MAX__(int a, int b, int c, int d) {
    return max(max(a, b), max(c, d));
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i][i] = max(a[i], 1);
    }
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l <= n && l + len - 1 <= n; l++) { // 分段起点 
            int r = l + len - 1; // 分段终点
            dp[l][r] = len * len;
            for (int k = l; k <= r - 1; k++) { // 中断点。
                int lenl = k - l + 1; // 左边区间的长度；
                int lenr = len - lenl; // 右边区间的长度。 
                dp[l][r] = max(dp[l][r], MAX__(lenl * lenl + lenr * lenr, dp[l][k] + lenr * lenr, lenl * lenl + dp[k + 1][r], dp[l][k] + dp[k + 1][r])); 

            }

        }
    }
    cout << dp[1][n] << "\n"; // sum_max
    return 0;
}

只要合成操作就行了。

亿点点代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int dp[20][20]; // 段 l, r 能达到的最大值。
int a[20];

struct Node{
    queue<int> l;
    queue<int> r; // 操作序列 
} __opertor__[20][20];

int MAX__(int a, int b, int c, int d) {
    return max(max(a, b), max(c, d));
}

vector <int> lans;
vector <int> rans;

int op[20];
void solve(int l, int r) { // 将 l, r 区间操作成 k^2。 [l,r] 都变成 k 
    int k = (r - l + 1);
    if (k == 1) {
        if (op[l] != 0) {
            lans.push_back(l);
            rans.push_back(l);  
            op[l] = 0;
            lans.push_back(l);
            rans.push_back(l);  
            op[l] = 1;
        } else {
            lans.push_back(l);
            rans.push_back(l);  
            op[l] = 1;
        }

        return ;
    }
    //solve(l + 1, r)
    if (op[l] != 0) {
        lans.push_back(l);
        rans.push_back(l);
        op[l] = 0;  
    }
    for (int i = l + 1; i <= r; i++) {
        //cout << i << " " << r << "==\n";
        solve(i, r);
    }
    for (int i = 1; i <= r; i++) {
        op[i] = k;
    }
    lans.push_back(l);
    rans.push_back(r);
    return ;
    /*
    for (int i = 1, u = l; i <= k; i++, u++) {
        op[i] = a[u];
    }
    for (int i = k - 1, start = 1; k >= 1; k--, start++) { // 目标数：i，操作位置：[start,k]
        for (int j = start; j <= k; j++) {
            if (op[i] != 0) {
                op[i] = 0;
                lans.push_back(j + l - 1);
                rans.push_back(j + l - 1);
            }
        }

    }
    */
    //return ;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i][i] = max(a[i], 1);
        if (a[i] == 0) {
            __opertor__[i][i].l.push(i);
            __opertor__[i][i].r.push(i);
        }
    }
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l <= n && l + len - 1 <= n; l++) { // 分段起点 
            int r = l + len - 1; // 分段终点
            dp[l][r] = len * len;
            __opertor__[l][r].l.push(l);
            __opertor__[l][r].r.push(r);

            for (int k = l; k <= r - 1; k++) { // 中断点。
                int lenl = k - l + 1; // 左边区间的长度；
                int lenr = len - lenl; // 右边区间的长度。 
                dp[l][r] = max(dp[l][r], MAX__(lenl * lenl + lenr * lenr, dp[l][k] + lenr * lenr, lenl * lenl + dp[k + 1][r], dp[l][k] + dp[k + 1][r])); 
                if (dp[l][r] == lenl * lenl + lenr * lenr) {
                    while (!__opertor__[l][r].l.empty()) { /////////////////////////1
                        __opertor__[l][r].l.pop();
                        __opertor__[l][r].r.pop();
                    }
                    __opertor__[l][r].l.push(l);
                    __opertor__[l][r].l.push(k);
                    __opertor__[l][r].l.push(k + 1);
                    __opertor__[l][r].l.push(k);
                } else if (dp[l][r] == dp[l][k] + lenr * lenr) { ///////////////////2
                    while (!__opertor__[l][r].l.empty()) {
                        __opertor__[l][r].l.pop();
                        __opertor__[l][r].r.pop();
                    }

                    queue<int> ok1, ok2;
                    while (!ok1.empty()) {ok1.pop();} while (!ok2.empty()) {ok2.pop();}

                    while (!__opertor__[l][k].l.empty()) {
                        __opertor__[l][r].l.push(__opertor__[l][k].l.front());
                        __opertor__[l][r].r.push(__opertor__[l][k].r.front());
                        ok1.push(__opertor__[l][k].l.front());
                        ok2.push(__opertor__[l][k].r.front());

                        __opertor__[l][k].l.pop();
                        __opertor__[l][k].r.pop();
                    }
                    while (!ok1.empty()) {
                        __opertor__[l][k].l.push(ok1.front());
                        __opertor__[l][k].r.push(ok2.front());
                        ok1.pop();
                        ok2.pop();
                    }

                    __opertor__[l][r].l.push(k + 1);
                    __opertor__[l][r].r.push(r);

                } else if (dp[l][r] == lenl * lenl + dp[k + 1][r]) { /////////////////////3
                    while (!__opertor__[l][r].l.empty()) {
                        __opertor__[l][r].l.pop();
                        __opertor__[l][r].r.pop();
                    }

                    queue<int> ok1, ok2;
                    while (!ok1.empty()) {ok1.pop();} while (!ok2.empty()) {ok2.pop();}

                    while (!__opertor__[k + 1][r].l.empty()) {
                        __opertor__[l][r].l.push(__opertor__[k + 1][r].l.front());
                        __opertor__[l][r].r.push(__opertor__[k + 1][r].r.front());
                        ok1.push(__opertor__[k + 1][r].l.front());
                        ok2.push(__opertor__[k + 1][r].r.front());

                        __opertor__[k + 1][r].l.pop();
                        __opertor__[k + 1][r].r.pop();
                    }
                    while (!ok1.empty()) {
                        __opertor__[k + 1][r].l.push(ok1.front());
                        __opertor__[k + 1][r].r.push(ok2.front());
                        ok1.pop();
                        ok2.pop();
                    }

                    __opertor__[l][r].l.push(l);
                    __opertor__[l][r].r.push(k);

                } else if (dp[l][r] == dp[l][k] + dp[k + 1][r]) { /////////////////4
                    while (!__opertor__[l][r].l.empty()) {
                        __opertor__[l][r].l.pop();
                        __opertor__[l][r].r.pop();
                    }

                    queue<int> ok1, ok2;
                    while (!ok1.empty()) {ok1.pop();} while (!ok2.empty()) {ok2.pop();}

                    while (!__opertor__[l][k].l.empty()) {
                        __opertor__[l][r].l.push(__opertor__[l][k].l.front());
                        __opertor__[l][r].r.push(__opertor__[l][k].r.front());
                        ok1.push(__opertor__[l][k].l.front());
                        ok2.push(__opertor__[l][k].r.front());

                        __opertor__[l][k].l.pop();
                        __opertor__[l][k].r.pop();
                    }
                    while (!ok1.empty()) {
                        __opertor__[l][k].l.push(ok1.front());
                        __opertor__[l][k].r.push(ok2.front());
                        ok1.pop();
                        ok2.pop();
                    }
                    //--------
                    while (!ok1.empty()) {ok1.pop();} while (!ok2.empty()) {ok2.pop();}

                    while (!__opertor__[k + 1][r].l.empty()) {
                        __opertor__[l][r].l.push(__opertor__[k + 1][r].l.front());
                        __opertor__[l][r].r.push(__opertor__[k + 1][r].r.front());
                        ok1.push(__opertor__[k + 1][r].l.front());
                        ok2.push(__opertor__[k + 1][r].r.front());

                        __opertor__[k + 1][r].l.pop();
                        __opertor__[k + 1][r].r.pop();
                    }
                    while (!ok1.empty()) {
                        __opertor__[k + 1][r].l.push(ok1.front());
                        __opertor__[k + 1][r].r.push(ok2.front());
                        ok1.pop();
                        ok2.pop();
                    }

                }

            }

        }
    }

    /*
    while (!__opertor__[1][n].l.empty()) {
        cout << __opertor__[1][n].l.front() << " " << __opertor__[1][n].r.front() << "\n";
        __opertor__[1][n].l.pop();
        __opertor__[1][n].r.pop();
    }
    */
    while (!__opertor__[1][n].l.empty()) {
        //cout << __opertor__[1][n].l.front() << " - " << __opertor__[1][n].r.front() << "\n";
        for (int i = 1; i <= n; i++) {
            op[i] = a[i];
        }
        solve(__opertor__[1][n].l.front(), __opertor__[1][n].r.front()); // 万能公式。 
        __opertor__[1][n].l.pop();
        __opertor__[1][n].r.pop();
    }   

    cout << dp[1][n] << " "; // sum_max
    cout << lans.size() << "\n";
    for (int i = 0; i < lans.size(); i++) {
        cout << lans[i] << " " << rans[i] << "\n";
    }
    return 0;
}

性能：