【CF】Day8——Codeforces Round 917 (Div. 2)BC + Codeforces Round 932 (Div. 2) BC

KyollBM

970人浏览 · 2025-03-16 11:14:25

KyollBM · 2025-03-16 11:14:25 发布

B. Erase First or Second Letter

题目：

思路：

思维题

如果我们要删除的话，只能删除第一个和第二个，那我们来分析一下操作后会发生什么

如果删除的是第一个，那么就是字符串的首字母换成第下一个了

如果删除的是第二个，那么就是首字母后的字符串发生了改变

我们可以假定首字母为c，那么以c为首字母的奉献就是n - pos[c]，其中pos[c]为字符c在字符串中的位置

那么我们只需要储存每个字符在字符串中的位置即可

特别的，如果字符串中有个字符有多个位置，我们只需储存最前的位置即可，因为对于同一个首字母，位置前的所有字串肯定包括位置后的所有子串

如：p......pabc

只需要删除到第二个p的位置，那么当前串就变成了pabc，这和以第二个p开头的情况是一样的

代码：

#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;
    int ans = 0;
    vector<int> dp(26,n);
    for (int i = 0; i < n; i++)
    {
        dp[s[i] - 'a'] = min(i, dp[s[i] - 'a']);
    }
    for (int i = 0; i < 26; i++)
    {
        ans += n - dp[i];
    }
    cout << ans << '\n';
}

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

C. Watering an Array

题目：

思路：

好题，差点一遍过

对于这道题，我们可以先分情况讨论：

①.没执行操作二

在没执行操作二前，我们每次都是选前b[i]个元素加一，显然我们可以暴力枚举，求得一个最优的情况

②.执行操作二后

在执行操作二后我们数组全都变为0，那么我们可以观察到，由于每次都是将 1~b[i] 加一，那么我们如何操作才能最优呢？

显然是执行一次操作一后直接执行操作二，因为每次加一都会使前b[i]个元素的值加一，那么每次加完后，原来符合的就会变成不符合，所以无论我们加多少次，最后的奉献最多肯定是1

故只要我们执行过一次操作二后，我们之后能获得的最大奉献就是 [d/2] 其中d是剩下的天数

所以接下来我们枚举执行多少次操作一即可，但是直接暴力枚举肯定不行，因为d太大了，那么重点来了，我们观察一下，第一次最多只能得到n的奉献，那么我们可以转化一下，如果执行操作二加操作一，那么需要多少次才能得到n的奉献呢，显然是2*n次，所以我们最多就执行2*n次操作一即可，如果再执行的话，还不如直接一直操作二+操作一

代码：

#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, k, d;
    cin >> n >> k >> d;
    vector<int> a(n+1),v(k+1,0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> v[i];
    }
    int ans = 0;
    for (int i = 0; i <= min(2 * n, d - 1); i++)
    {
        int temp = 0;
        for (int j = 1; j <= n; j++)
        {
            temp += (a[j] == j);
        }
        int tempans = temp + (d - 1 - i) / 2;
        ans = max(ans, tempans);
        for (int j = 1; j <= v[i % k + 1]; j++)
        {
            a[j]++;
        }
    }
    cout << ans << endl;
}

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

B. Informatics in MAC

题目：

思路：

思维题，代码实现要细节一点

首先题目让我们分成k个子段，且每段的mex都相同，那么要注意到，如果两段的mex相等，肯定可以将两段合并，因为其中都没有mex，最大也只是mex-1，所以这道题其实就是让我们找两个子区间满足mex相等即可

那么注意到了这个性质这道题的难点就解决了，接下来我们只需要枚举分界点i，使得左右两段的区间的mex相同即可

代码的mex处理有点细，可以细品

代码：

#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> a(n),cnt(n+1),cnt2(n+1);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        cnt2[a[i]]++;
    }
    //前i个的mex，后n-i个的mex
    int mex1 = 0, mex2 = 0;
    while (cnt2[mex2])
    {
        mex2++;
    }
    for (int i = 0; i < n-1; i++)
    {
        cnt[a[i]]++;
        cnt2[a[i]]--;
        if (cnt2[a[i]] == 0 && mex2 > a[i])
        {
            mex2 = a[i];
        }
        while (mex2 && !cnt2[mex2-1])
        {
            mex2--;
        }
        while (cnt[mex1])
        {
            mex1++;
        }
        if (mex1 == mex2)
        {
            cout << 2 << endl;
            cout << 1 << " " << i + 1 << endl;
            cout << i + 2 << " " << n << endl;
            return;
        }
    }
    cout << "-1\n";
}

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

C. Messenger in MAC

题目：

思路：

思维题

由于时间是关于a和b的，而a是直接相加，无法改变其奉献，那我们就要考虑如何才能使得b的奉献最小，可以注意到，如果b是如下排列 b1 <= b2 <= b3 <= b4 ... <= bn 的话，那么最后的奉献就是bn-b1，可以肯定，这是最小的奉献，因为相邻的b的差值都是最小的

那么接下来我们就可以枚举 bl 和 br ，即b的左边界和右边界，那么确定好区间后只需要保证区间内的a的和小于 L - (br - bl)，即 $\sum a \leq L - (Br - Bl)$

那么如果总时间超出L我们该如何操作呢？根据贪心的思想，肯定是不选a最大的，即将a最大的那一条删除，因为我们 b 的奉献只和 br 和 bl 有关

这里为了优化寻找已选a的最大值，我们可以用multiset优化

代码：

#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"

struct MyStruct
{
    int a, b;
};



void solve()
{
    int n, L;
    cin >> n >> L;
    vector<MyStruct> news(n);
    for (int i = 0; i < n; i++)
    {
        cin >> news[i].a >> news[i].b;
    }
    sort(news.begin(), news.end(), [](MyStruct a, MyStruct b) {return a.b < b.b; });
    int ans = 0;
    for (int l = 0; l < n; l++)
    {
        multiset<int> s;
        int cur = 0;
        for (int r = l; r < n; r++)
        {
            s.insert(news[r].a);
            cur += news[r].a;
            while (!s.empty() && news[r].b - news[l].b + cur > L)
            {
                int max_value = *s.rbegin();
                cur -= max_value;
                int elementToExtract = max_value;
                auto it = s.find(elementToExtract);
                if (it != s.end())
                {
                    s.erase(it);
                }
            }
            ans = max(ans, (int)s.size());
        }
    }
    cout << ans << endl;
}

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