内测人员，写个简易题解。

A.小苯吃糖果

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

struct Lemon {
    Lemon() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} lemon;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int mod = 7 + 1e9;
// const int mod = 998244353;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
#if LEMON
const int N = 3 + 111;
#else
const int N = 3 + 2e5;
#endif

int main() {
    array<int, 3> a;
    for (auto& i : a) {
        cin >> i;
    }
    sort(a.begin(), a.end());
    cout << max(a[2], a[0] + a[1]);
    return 0;
}

B. 小苯的排列构造

尝试构造： $n=2$ ，只有 $[2,1]$ 符合， $a=[3, 3]$ 。 $n=3$ ，发现 $[3,2,1]$ 符合， $a=[4,4,4]$ 。

于是发现规律：一大一小凑一对，构造出的 $a$ 数组是 $n$ 个 $n 1$ 。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

struct Lemon {
    Lemon() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} lemon;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int mod = 7 + 1e9;
// const int mod = 998244353;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
#if LEMON
const int N = 3 + 111;
#else
const int N = 3 + 1e6;
#endif

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cout << n - i + 1 << " ";
    }
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

C. 小苯的最小整数

总共最大才 $11$ 位数，枚举所有情况取min就好了。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

struct Lemon {
    Lemon() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} lemon;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int mod = 7 + 1e9;
// const int mod = 998244353;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
#if LEMON
const int N = 3 + 111;
#else
const int N = 3 + 2e5;
#endif

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        LL ans = stoll(s);
        for (int i = 0; i < s.size(); ++i) {
            s = s.substr(1) + s[0];
            ans = min(ans, stoll(s));
        }
        cout << ans << endl;
    }

    return 0;
}

D. 小苯的蓄水池（easy）

直接循环就好了。没写，直接写的hard。

E. 小苯的蓄水池（hard）

用一个set维护隔板。其中 $i$ 表示 $i$ 和 $i 1$ 之间的隔板。

①对于删除操作，循环过去把隔板从set删除就好了。

②对于查询操作，分别找到第 $p$ 个水池的前一个隔板和后一个隔板。通过set的lower_bound找到后一个隔板，--运算符移动迭代器找到前一个隔板。然后前缀和求出区间和。


#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

struct Lemon {
    Lemon() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} lemon;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int mod = 7 + 1e9;
// const int mod = 998244353;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
#if LEMON
const int N = 3 + 111;
#else
const int N = 3 + 2e5;
#endif

int a[N], n, m;
set<int> st;
LL pre[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        st.insert(i);
        pre[i] = pre[i - 1] + a[i];
    }
    while (m--) {
        int op, l, r, p;
        cin >> op;
        if (op == 1) {
            cin >> l >> r;
            auto p = st.lower_bound(l);
            while (*p < r) {
                p = st.erase(p);
            }
        } else {
            cin >> p;
            auto it = st.lower_bound(p);
            int r = *it;
            int l = 1;
            if (it != st.begin()) {
                --it;
                l = *it + 1;
            }
            cout << fixed << setprecision(8) << 1.0 * (pre[r] - pre[l - 1]) / (r - l + 1) << endl;
        }
    }

    return 0;
}

F. 小苯的字符提前

字典序肯定有传递性的。用sort对每一个位置，按照字典序排序。

比较字典序时，不能for过去比较，得想办法加速。

画图，如下，假设要比较位置 $x$ 和 $y$ 的字典序，假定 $x\lt y$ 。 alt

① $s_x$ 和 $s_y$ 移到最前面，如果不相等，直接根据 $s_x$ 和 $s_y$ 得到字典序大小。

② $s_x$ 前面的字符不需要比较，因为对应位置一样。

③根据上图，如果移动 $s_y$ 到前面，这一部分 $s_i(x\le i \lt y)$ 不移动；如果移动 $s_x$ 到前面，这一部分 $s_i(x\lt i \le y)$ 往前移动一个位置，从而和 $s_y$ 对应上。

用一个数组 $next\_not\_equal$ ， $next\_not\_equal_i$ 表示从 $i$ 开始，最小的 $j(j\ge i)$ ， $s_j$ 和 $s_{j 1}$ 不相同的。

⑤如果 $next\_not\_equal_y$ 大于等于 $y$ ，那么说明这段都相同。并且又因为后面没有移动，完全一样，那么说明 $x$ 和 $y$ 两个位置得到的字符串完全一样。

sort完之后，拿到第 $k$ 小的下标，按题目的定义输出就行了。

优化：内测群友说可以线性，nth，于是把代码中的

sort(p + 1, p + n + 1, [&](int x, int y) -> int {

替换成

nth_element(p + 1, p + k, p + n + 1, [&](int x, int y) -> int

从 $200ms$ 变成 $50ms$ 。这太有意思了。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

struct Lemon {
    Lemon() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} lemon;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int mod = 7 + 1e9;
// const int mod = 998244353;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
#if LEMON
const int N = 3 + 111;
#else
const int N = 3 + 1e6;
#endif

int n, k;
char s[N];
int next_not_equal[N];

int p[N];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    next_not_equal[n] = n;
    for (int i = n - 1; i >= 1; --i) {
        next_not_equal[i] = next_not_equal[i + 1];
        if (s[i] != s[i + 1]) {
            next_not_equal[i] = i;
        }
    }
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
    }
    sort(p + 1, p + n + 1, [&](int x, int y) -> int {
        if (s[x] != s[y]) {
            return s[x] < s[y];
        }
        if (x < y) {
            if (next_not_equal[x] >= y) {
                return 0;
            }
            return s[next_not_equal[x] + 1] < s[next_not_equal[x]];
        } else {
            if (next_not_equal[y] >= x) {
                return 0;
            }
            return s[next_not_equal[y]] < s[next_not_equal[y] + 1];
        }
    });

    int z = p[k];
    cout << s[z];
    for (int i = 1; i < z; ++i) {
        cout << s[i];
    }
    for (int i = z + 1; i <= n; ++i) {
        cout << s[i];
    }
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

G. 小苯的数位MEX

从大到小枚举mex，因为数字是 $0$ 到 $9$ ， $mex$ 从 $0$ 到 $10$ 。

根据题意给的操作， $x$ 能变成 $[x,x k]$ 这个区间的数据。用数位dp求 $[x,x k]$ 有多少个数字的 $mex$ 是枚举的mex。如果个数大于 $0$ ，说明找到了答案，输出这个枚举的mex和个数。

dp数组含义： $dp_{p,st}$ ，从高位起第 $1$ 到 $p$ 位，拥有的数字用 $st$ 这个集合表示。如果把这个状态的数字凑完整，会有 $dp_{p,st}$ 个数字的mex是枚举的mex。这个 $dp$ 值没有数字上限和前导零的限制。

内测小故事：原本题意是 $L$ 到 $R$ 的mex值的总和。但是现在要稍微计算一下 $L,R$ ，还要枚举mex，好没意思的改题方式。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

struct Lemon {
    Lemon() {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} lemon;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int mod = 7 + 1e9;
// const int mod = 998244353;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
#if LEMON
const int N = 3 + 111;
#else
const int N = 3 + 1e6;
#endif

int dp[12][1024];
int p, a[N];

int dfs(int p, int limit, int lead, int st, int m) {
    if (!p) {
        int mex = 0;
        while (st >> mex & 1) {
            ++mex;
        }
        return mex == m;
    }

    if (!limit && !lead && dp[p][st] != -1) {
        return dp[p][st];
    }
    int ans = 0;

    int up = limit ? a[p] : 9;

    for (int i = 0; i <= up; ++i) {
        if (lead && i == 0) {
            ans += dfs(p - 1, limit && i == up, lead && i == 0, st, m);
        } else {
            ans += dfs(p - 1, limit && i == up, lead && i == 0, st | (1 << i), m);
        }
    }
    if (!limit && !lead) {
        dp[p][st] = ans;
    }
    return ans;
}

int calc(int x, int m) {
    p = 0;
    do {
        a[++p] = x % 10;
        x /= 10;
    } while (x);
    memset(dp, -1, sizeof(dp));
    return dfs(p, 1, 1, 0, m);
}

void solve() {
    int L, K;
    cin >> L >> K;

    int l, r;
    l = L;
    r = L + K;
    for (int i = 10; i >= 0; --i) {
        int ans = calc(r, i) - calc(l - 1, i);
        if (ans) {
            cout << i << " " << ans << endl;
            break;
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}