右左错题解

2024-11-11 青年杯,题解 12 2

题意关键点：

每次操作必须以一个 'L' 开头，以一个 'R' 结尾；
区间内的分数是所有 $a_i$ 的和；
选中的区间一旦使用，就无法再用；
目标是通过合理选择区间获得最大分数。

所以我们选择的区间不能重叠，但是我们可以先选择一个内区间，再选择一个外区间又因为数组中全是正数，因此我们要尽可能选择更大的区间，这对于答案的贡献是最大的，即从第一个 "L "到最后一个 "R"。选择了这个区间，我们就只能在其中选择区间。只要可能，我们就可以在刚刚选择的区间中继续寻找这样的尽可能大的区间

题目中涉及到计算区间和，那么前缀和再适合不过

我们可以使用双指针从最外层开始来找出所有尽可能大的区间

代码如下：

#include <bits/stdc++.h>
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
// #pragma GCC optimize(2,"Ofast","inline")
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
const char nl = '\n';
const int N = 2e5 + 10;
int a[N];
char c[N];
LL s[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];//构造前缀和
    }
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    int l = 1, r = n;
    LL ans = 0;
    while (l < r)
    {
        if (c[l] == 'L' && c[r] == 'R')//计算每个区间和
        {
            ans += s[r] - s[l - 1];
            l++, r--;
        }
        else if (c[l] != 'L' && c[r] == 'R')
            l++;
        else if (c[l] == 'L' && c[r] != 'R')
            r--;
        else
            l++, r--;
    }
    cout << ans << nl;
}
int main()
{
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

题解.md

LXX

我们的征途是星辰大海

青年杯

Warning: Undefined array key "HTTP_ACCEPT_LANGUAGE" in /usr/home/LXX123/domains/www.lxxblog.cfd/public_html/usr/themes/Farallon/comments.php on line 4 Deprecated: stripos(): Passing null to parameter #1 ($haystack) of type string is deprecated in /usr/home/LXX123/domains/www.lxxblog.cfd/public_html/usr/themes/Farallon/comments.php on line 4

右左错 - Lxx's Blog
2024-11-11 10:49

[...]22来源题目.mdcode.cpp题解[...]
青年杯出题 - Lxx's Blog
2024-11-11 10:50

[...]题目列表古代王国的正交拉丁方阵秘文破解石碑中的三阶秘阵二进制谜题：中位数的秘密右左错魔法师的非递减之旅位元守护者的试炼车的突击之路题解列表古代王国的正交拉丁方阵秘文题解破解石碑中的三阶秘阵题解二进制谜题：中位数的秘密题解右左错题解魔法师的非递减之旅题解[位元守护者的试炼题解][车的突击之路题解][...]

右 左 错题解

相关文章

右左错题解