Educational Codeforces Round 112 (Rated for Div. 2)

CodeForces - 1555D Say No to Palindromes

如果一个字符串中不包含长度2以上的回文子串，我们就说这个字符串是漂亮的，现在一个字符串只有a,b,c三个小写字母组成，每次操作可以修改任意一个字母为a,b,c,存在q次询问，每次询问给定区间\([l,r]\),你需要求出将这个区间子串变为漂亮字符串的最小操作数

题解：计数DP+思维（字符串循环节）

我们模拟后发现如果想要使得一个字符串漂亮，那么我们这个字符串的样子应该为：abcabcabc...那么这样的循环节一共有6种，我们只要对于每一种循环节求操作数即可，我们先预处理完后再回答询问即可

状态表示：\(f[i][j]\):对于第i个循环节，将字符串\([1,j]\)修改为漂亮字符串所需的操作数

状态属性：数量

状态转移：

当前字符和循环节上的字符不一样 \(str[i]!=s[i][pos]\),\(f[i][j] = f[i][j-1]+1\)

当前字符和循环节上的字符相同\(str[i]==s[i][pos]\),\(f[i][j] = f[i][j-1]\)

那么对于\([l,r]\)之间的最小操作数，我们只能选择一种循环节将它变成漂亮字符串，那么答案就是\(\sum _{i=1}^{6} {min(f[i][r]-f[i][l-1])}\)

#include <bits/stdc++.h>

#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)

#define debug(x) cerr << #x << '=' << x << endl

#define all(x) (x).begin(), (x).end()

#define rson id << 1 | 1

#define lson id << 1

#define int long long

#define mpk make_pair

#define endl '\n'

using namespace std;

typedef unsigned long long ULL;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

const double eps = 1e-9;

const int N = 2e5 + 10, M = 4e5 + 10;

string s[6] = {"#abc", "#acb", "#bac", "#bca", "#cab", "#cba"};

int f[6][N];

int n, q;

void solve()

{

    cin >> n >> q;

    string str;

    cin >> str;

    str = " " + str;

    for (int i = 0; i < 6; ++i)

    {

        for (int j = 1; j <= n; ++j)

        {

            int pos = j % 3;

            if (pos == 0)

                pos = 3;

            if (str[j] != s[i][pos])

                f[i][j] = f[i][j - 1] + 1;

            else

                f[i][j] = f[i][j - 1];

        }

    }

    while (q--)

    {

        int l, r;

        cin >> l >> r;

        int ans = INF;

        for (int i = 0; i < 6; ++i)

            ans = min(ans, f[i][r] - f[i][l - 1]);

        cout << ans << endl;

    }

}

signed main(void)

{

    Zeoy;

    int T = 1;

    // cin >> T;

    while (T--)

    {

        solve();

    }

    return 0;

}

CodeForces - 1555E Boring Segments

给定\(n\)个区间\([l,r]\)，每个区间都有权值\(w\),又给定\(m\)，求如果若干个区间能够覆盖\([1,m]\),那么成本就是这些区间中的最大权值和最小权值之差，现在保证一定能有区间能够覆盖\([1,m]\),求出覆盖\([1,m]\)成本的最小值

题解：双指针+线段树维护区间覆盖问题+贪心：好题目

我们先来说一说怎么快速计算出成本，并且能够在\(O(n)\)时间内遍历完所有能够覆盖[1,m]的若干线段

我们将区间按照权值升序排列，那么如果\([i,j]\)之间的区间能够覆盖[1,m]，那么它的成本就是\(w_j-w_i\)

我们往往可以使用双指针来解决极值问题，那么在这个问题中，我们发现随着\(j\)指针的后移，\(i\)指针存在单调性，所以我们可以使用双指针来解决问题

那么我们如何检查现在覆盖的区间是否覆盖\([1,m]\)，我们可以利用线段树维护区间最小值，对于每一个区间\([l,r]\)进行区间加1，如果[1,m]区间中的最小值<1,那就说明区间[1,m]没有被覆盖到，否则说明已经覆盖完了，所以我们只需要在进行双指针时进行区间修改即可，然后我们每次只要检查\(seg[1].val.minn\)即可

我们需要注意，在本题中，例如：[1,5],[6,m]这样是不算覆盖m的，只有区间重合才算，所以我们为了解决这个问题，对于[l,r]我们可以在每次修改的时候只修改\([l,r-1]\),那么最后我们建树建立的区间只需要建立\([1,m-1]\)即可

#include <bits/stdc++.h>

#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)

#define debug(x) cerr << #x << '=' << x << endl

#define all(x) (x).begin(), (x).end()

#define rson id << 1 | 1

#define lson id << 1

#define int long long

#define mpk make_pair

#define endl '\n'

using namespace std;

typedef unsigned long long ULL;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

const double eps = 1e-9;

const int N = 3e5 + 10, M = 1e6 + 10;

int n, m;

struct info

{

    int minn;

};

struct node

{

    int l, r, lazy;

    info val;

} seg[M << 2];

info operator+(const info &a, const info &b)

{

    info c;

    c.minn = min(a.minn, b.minn);

    return c;

}

void settag(int id, int tag)

{

    seg[id].val.minn += tag;

    seg[id].lazy += tag;

}

void up(int id)

{

    seg[id].val = seg[lson].val + seg[rson].val;

}

void down(int id)

{

    if (seg[id].lazy == 0)

        return;

    settag(lson, seg[id].lazy);

    settag(rson, seg[id].lazy);

    seg[id].lazy = 0;

}

void build(int id, int l, int r)

{

    seg[id].l = l, seg[id].r = r;

    int mid = l + r >> 1;

    if (l == r)

    {

        seg[id].val.minn = 0;

        return;

    }

    build(lson, l, mid);

    build(rson, mid + 1, r);

    up(id);

}

void modify(int id, int ql, int qr, int val)

{

    int l = seg[id].l, r = seg[id].r;

    if (ql <= l && r <= qr)

    {

        settag(id, val);

        return;

    }

    down(id);

    int mid = (l + r) >> 1;

    if (qr <= mid)

        modify(lson, ql, qr, val);

    else if (ql > mid)

        modify(rson, ql, qr, val);

    else

    {

        modify(lson, ql, qr, val);

        modify(rson, ql, qr, val);

    }

    up(id);

}

struct range

{

    int l, r, w;

    bool operator<(const range &t) const

    {

        return w < t.w;

    }

} a[N];

void solve()

{

    cin >> n >> m;

    build(1, 1, m - 1);

    for (int i = 1; i <= n; ++i)

        cin >> a[i].l >> a[i].r >> a[i].w;

    sort(a + 1, a + n + 1);

    int ans = INF;

    for (int i = 1, j = 1; j <= n; ++j)

    {

        modify(1, a[j].l, a[j].r - 1, 1);

        while (i <= j && seg[1].val.minn > 0)

        {

            ans = min(ans, a[j].w - a[i].w);

            modify(1, a[i].l, a[i].r - 1, -1);

            i++;

        }

    }

    cout << ans << endl;

}

signed main(void)

{

    Zeoy;

    int T = 1;

    // cin >> T;

    while (T--)

    {

        solve();

    }

    return 0;

}

巴特西

Educational Codeforces Round 112 (Rated for Div

Educational Codeforces Round 112 (Rated for Div. 2)

CodeForces - 1555D Say No to Palindromes

题解：计数DP+思维（字符串循环节）

CodeForces - 1555E Boring Segments

题解：双指针+线段树维护区间覆盖问题+贪心：好题目

最新文章

热门文章

巴特西

Educational Codeforces Round 112 (Rated for Div

Educational Codeforces Round 112 (Rated for Div. 2)

CodeForces - 1555D Say No to Palindromes

题解：计数DP+思维（字符串循环节）

CodeForces - 1555E Boring Segments

题解：双指针+线段树维护区间覆盖问题+贪心 ： 好题目

最新文章

热门文章

题解：双指针+线段树维护区间覆盖问题+贪心：好题目