526互联

Educational Codeforces Round 65 (Rated for Div

发布时间 2023-03-29 19:52:36作者: Zeoy_kkk

D - Bicolored RBS

给定一个括号序列，现在你必须对每一个括号涂成蓝色或红色，要求使得涂完后的红色括号和蓝色括号序列都必须是合法的括号序列，设红色括号形成的的括号序列的深度为\(dep_1\),蓝色括号形成的括号序列的深度为\(dep_2\),答案为\(max(dep_1,dep_2)\),现在让你求出答案的最小值，即将答案最小化

题解：贪心

  • 引理：括号序列的深度\(dep\)即为其所有位置上左括号的前缀数量减去右括号前缀数量的最大值，或者说是我们将括号序列放入栈中时的最大深度

那么实际上我们对于给定的括号序列，在未涂色前我们可以将其深度\(dep\)求出，那么我们只要试着将该深度平分给红色括号序列和蓝色括号序列即可：

  1. 如果\(dep\)是偶数，那么\(dep_1=dep/2,dep_2=dep/2\)
  2. 如果\(dep\)是奇数，那么\(dep_1=dep/2+1,dep_2=dep/2\)或者\(dep_1=dep/2,dep_2=dep/2+1\)

那么实际上我们发现我们只要维护两个栈（一个栈代表红色括号序列，一个栈代表蓝色括号序列）

  1. 如果当前入栈的元素是左括号，我们只要看哪一个栈的深度小我们就放哪一个栈
  2. 如果当前入栈的元素时右括号，我们只要看哪一个栈的深度大我们就放哪一个栈

这样就能贪心的使得两个栈深度的最大值最小化

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

int n;
int stk1[N], stk2[N], tt1, tt2;

void solve()
{
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    string ans = s;
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == '(')
        {
            if (tt1 <= tt2)
            {
                stk1[++tt1] = i;
                ans[i] = '0';
            }
            else
            {
                stk2[++tt2] = i;
                ans[i] = '1';
            }
        }
        else
        {
            if (tt1 <= tt2 && tt2)
            {
                tt2--;
                ans[i] = '1';
            }
            else if (tt1 > tt2 && tt1)
            {
                tt1--;
                ans[i] = '0';
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        cout << ans[i];
    cout << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

E - Range Deleting

给定长度为\(n\)的数组\(a\)，其中\(a_i<=m,(1<=n,m<=1e6)\),定义\(f(l,r)\)为删除数组\(a\)中数值在\([l,r]\)范围内的元素后剩余的数组\((1<=l<=r<=m)\)，请你求出\(f(l,r)\)是单调不递减序列的数量

题解：双指针 ： 好题目

首先我们可以发现：

​ 如果\(f(l,r)\)是合法的单调不递减序列，那么对于\(1<=l'<l,r<r'<=m\),\(f(l',r')\)一定也是合法的单调不递减序列，那么说明随着左端点\(l\)变化，右端点\(r\)的变化具有单调性，即对于一个合法的左端点\(l\)我们在求出其右边第一个合法的右端点\(r\)（对于\(l\)来说是合法的），那么对于所有\([r,m]\)的右端点都是合法的右端点，那么我们再向右找到该合法左端点的下一个合法左端点\(l'\)，显然根据我们上面的分析一定存在\(r'>=r\)是合法的右端点，所以我们可以利用双指针解决该问题

那么我们在利用双指针处理时需要预处理以下几个问题：

  1. 对于\(f(l,r)\)来说，位于区间\([1,l-1]\)和\([r+1,m]\)中的所有元素在序列中一定是单调不递减，也就是说位于区间\([1,l-1]\)和\([r+1,m]\)中的所有元素之间不会形成逆序对，所以我们需要预处理出所有合法的左端点\(l\)，使得在区间\([1,l]\)中不存在逆序对，同时预处理出所有合法的右端点\(r\)，使得\([r,m]\)中不会存在逆序对

  2. 我们首先需要预处理出所有合法的左端点\(l\)，即属于\([1,l]\)的元素形成的序列不会形成逆序对，同时我们发现所有合法的左端点\(l\)一定是连续的，也就说合法的左端点是一段区间\([1,ql]\)，在这个区间中所有的点都是合法的左端点，那么我们的左指针\(i\)就可以在这段区间中移动，但是现在的关键是我们怎么预处理出这段合法的区间？

  3. 首先我们一定能够预处理出所有元素在序列中出现的最左边的位置\(posl\)和最右边的位置\(posr\)，现在我们假设区间\([1,l]\)是合法的，也就是说该区间中的元素不存在逆序对，那么对于区间\([1,l+1]\)来说我们只要判断值为\(l+1\)的元素在序列中出现的最左边的位置会不会比区间\([1,l]\)中所有元素在序列中出现的位置中的最大位置来的小，如果小于说明区间\([1,l+1]\)中存在逆序对，反之说明\([1,l+1]\)同样合法，那么我们现在又需要多知道一个东西：元素值位于区间\([1,i]\)中的所有元素所处的最右边位置，那么对于这个我们只需要利用\(dp\)进行转移即可：\(R[i]=max(R[i-1],posr[i])\)

  4. 那么类似左端点，我们同样可以预处理所有合法的右端点区间\([qr,m]\),右指针\(j\)可以在这段区间中移动，不再赘述

  5. 那么对于\(i∈[1,ql],r∈[qr,m]\),我们如何去检查\(f(i,j)\)是合法的呢？显然我们只要判断区间\([1,i-1]\)的最右边位置是否和区间\([j+1,m]\)中最左边的位置形成逆序对即可

#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 = 1e6 + 10, M = 4e5 + 10;

int n, m;
int a[N];
int posl[N], posr[N], L[N], R[N];

void solve()
{
    cin >> n >> m;
    for (int i = 0; i <= m + 1; ++i)
    {
        posl[i] = INF;
        posr[i] = -INF;
        L[i] = INF;
        R[i] = -INF;
    }
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
    {
        posl[a[i]] = min(posl[a[i]], i);
        posr[a[i]] = max(posr[a[i]], i);
    }
    for (int i = 1; i <= m; ++i)
        R[i] = max(R[i - 1], posr[i]);	//dp预处理[1,i]中最右边元素位置
    for (int i = m; i >= 1; i--)
        L[i] = min(L[i + 1], posl[i]);	//dp预处理[i,m]中最左边元素位置
    int ql = 1, qr = m;
    while (posl[ql] >= R[ql - 1] && ql <= m)
        ql++;							//找到合法左端点区间[1,ql)
    while (posr[qr] <= L[qr + 1] && qr >= 1)
        qr--;							//找到合法右端点区间(qr,m],开区间的原因在双指针中体现
    int ans = 0;
    for (int i = 1, j = qr; i <= ql; ++i)
    {
        while (j <= m && (j < i || R[i - 1] > L[j + 1]))
            j++;
        ans += m - j + 1;
    }
    cout << ans << endl;
}
signed main(void)
{
    Zeoy;
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}