C. Largest Subsequence

题目：

思路：

思维题，顺便考了下细节

首先我们题目让我们对这个字符串排序，那么显然只能按它的规矩老实去做，但是直接模拟的话肯定死翘翘，那我们就来观察一下有什么性质

首先题目让我们找到字典序最大的字串来操作，那么最大的字串从什么地方开始？

肯定是从第一个出现最大字符的地方开始，然后往后每次都选较大的

比如对于样例czddeneeeemigec，我们肯定是从z开始选，然后d+d，此时遇到e，由于e大于d，那么就把d全踢掉选e，也就从zdd变为ze，然后又遇到n，n又大于e，因此又要踢掉e，变成zn，以此类推....最后的最大字串就是znmigec了

那么接下来如何操作呢，由于每次操作都是将最后一个字符提到最前面，也就是说最小的到最前面了，那么下一次选最长字串肯定不会选这个字符了，那么这样一看，这不就相当于一个删除操作吗？因此操作部分就可以概括为：选一个字典序最大字串，每次将最后一个字符删除

那么接下来就看操作次数了，显然操作次数就是：最大字串的长度 - 最大字符的数量，因为删到最后只有最大字符了，显然此时子串升序，因此不需要操作了，如zzzdc，只需要操作两次即可

特别的，由于本体还可能无法正确排序，那我们还需要检查操作完是否真的能正确排序，因此模拟一下即可，我们可以将选入最大字串的地方标记，那么第一次操作的时候就是把最后一个字符放入第一个标记位上，后面以此类推放在第二个，第三个....

细节看代码

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    string temp = s;
    sort(temp.begin(), temp.end());
    string k;
    vector<bool> need(n,0);
    for (int i = n- 1; i >= 0; i--)
    {
        if (i == n-1 ||(!k.empty() && k[k.size() - 1] <= s[i]))
        {
            k.push_back(s[i]);
            need[i] = 1;
        }
    }
    int res = k.size();
    for (int i = 0; i < k.size(); i++)
    {
        if (k[i] == k[k.size() - 1])
            res--;
    }
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (need[i])
        {
            s[i] = k[j++];
        }
    }
    if (s == temp)
        cout << res << endl;
    else
        cout << "-1\n";
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

---

D. Cyclic MEX

题目：

思路：

好题，思路远大于实现

遇到这种最大成本我们可以先来考虑二分答案，但是显然无法实现，因为即使你知道答案，你也不知道如何check（构造），以此我们只好老实模拟，但是模拟肯定也不行，直接 n² 的复杂度了

因此我们就来想想如何找找特性，同时，对于这种求和的题，我们可以首先考虑奉献法，即找找每个位置或区间的奉献是多少

一个显然的特性，最后的那个数的奉献一定是n，因为到最后肯定所有数都被选过了

但是好像还是没法做....那我们来暴力一下看看有没有规律呢

我们以第一个样例为例

欸，好像有点东西，我们只看答案看看

 

 嗯，现在好像有点端倪了，我们发现这个0的数量是递减的，而且每次将一个数放到后面，都会新增一个新的数，那么这有什么规律吗？

显然是有的，对照上图我们发现，第二种情况中，0前的数都是0，5前的数都是5，而第三种情况也是0前都是0，但是5前不是5了，反而变成4了，即4前有两个4，这是为什么？

其实这就是规律了，用语言表达一下就是：

若一个数的mex是x，当我们将一个小于x的数y提到最后，那么这个数的mex就是变成更小的y了

那么看看到底是不是这样，可以看到，当3提到后面，4就变成3了，同样的，2到后面也变了，因此确实是这样的，我们还可以再看一个例子

欸！好像确实欸，比如0 0 0 0 1 4 5 8，由于5之前没有比他大的，所以直接增加即可，但是到下一步就变成 0 0 0 1 2 2 2 8了，因为 4 5 都比2小，所以我们的结论是正确的

那么做法知道了，该如何用代码表达呢？

我们可以使用一个优先队列，同时我们可以离散化，我们只需要一个数的奉献的个数就行了，所以可以用pair来表示，第一个元素代表当前奉献的数是多少，第二个元素代表他奉献的数量，那么就好写了

我们可以将数组变为以0结尾（如果你实力强其实也不需要），然后想刚刚说的那样模拟即可，如果队列中有数大于当前放入最后的数，那么就出栈，同时将本次放入的数的奉献数量加上这个出栈的数的数量

具体细节看代码

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"

void solve()
{
    int n;
    cin >> n;
    vector<int> b(n),a;
    int index = -1;
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        if (index != - 1)
            a.push_back(b[i]);
        if (!b[i])
            index = i;
    }
    for (int i = 0; i <= index; i++)
    {
        a.push_back(b[i]);
    }
    int ans = 0,mx = 0;
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < a.size(); i++)
    {
        int num = 1;
        while (!pq.empty() && pq.top().first > a[i])
        {
            num += pq.top().second;
            ans -= pq.top().first * pq.top().second;
            pq.pop();
        }
        ans += a[i] * num;
        pq.push(make_pair(a[i], num));
        mx = max(mx, ans);
    }
    cout << mx + n << endl;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}