Educational Codeforces Round 152 (Rated for Div. 2)

C. Binary String Copying

题意

给出一个长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个相同的拷贝 $t_1,t_2,\cdots,t_m$ 。有 $m$ 个操作，第 $i$ 个操作 $[l_i,r_i]$ 表示将 $t_i$ 的第 $l_i$ 到第 $r_i$ 个字符排序。问最终得到多少个不同的 $t$ 串。

数据范围： $1\leq n,m\leq 2\times 10^5$ 。

题解

考虑一次操作 $[l,r]$ ，显然该区间前缀的 $0$ 和后缀的 $1$ 是没有影响的，所以它可以等价地缩成一个最短的区间 $[l',r']$ ，其中 $l'$ 为 $l$ 后面第一个 $1$ 的位置， $r'$ 为 $r$ 前面第一个 $0$ 的位置。如果 $l'>r'$ ，说明这个区间已经有序了。

容易发现对于缩完以后的区间，若 $[l_1,r_1]$ 和 $[l_2,r_2]$ 不完全一致，得到的串也是不同的。特别地，所有 $[l,r](l>r)$ 的区间都是一样的，它们得到的串都是 $s$ 本身。用set统计一下就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int pre[N],suf[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        int n,m;cin>>n>>m;
        string s0;cin>>s0;
        pre[0]=0,suf[n+1]=n+1;
        for(int i=1;i<=n;i++)
        {
            pre[i]=pre[i-1];
            if(s0[i-1]=='0') pre[i]=i;
        }
        for(int i=n;i;i--)
        {
            suf[i]=suf[i+1];
            if(s0[i-1]=='1') suf[i]=i;
        }
        set<pair<int,int>> s;
        for(int i=1;i<=m;i++)
        {
            int l,r;cin>>l>>r;
            if(suf[l]>pre[r]) s.insert({-1,-1});
            else s.insert({suf[l],pre[r]});
        }
        cout<<s.size()<<'\n';
    }
    return 0;
}

D. Array Painting

题意

有 $n$ 个数，每个数是 $0,1,2$ 。每个数初始都是蓝色，要把它们涂成红色。有两种操作：

花一块钱把一个数涂成红色；
选择一个非零的红色的数和一个和它相邻的蓝色的数，令红色数减一，将蓝色数涂成红色。

求最少需要多少钱。

数据范围： $1\leq n\leq 2\times10^5$ 。

题解

感觉这个题和牛客多校第二场的dp有些像。问题的关键在于有从后面往前给的操作，这种情况下，对于一个位置，我们不需要考虑后面往前给它的操作，只考虑它往前面给的操作，至于后面给它的情况，在枚举到后面位置的时候再考虑。

具体到这道题目，设 $f_{i,j}$ 为涂完前 $i$ 个数，最后一个数为 $j$ 的最小代价。那么最后一个数可以自己花钱涂，也可以由前一个数帮忙涂：

f_{i,a_i}=\min(f_{i-1,0}+1,\min(f_{i-1,1},f_{i-1,2}))

我们再考虑它往前涂的情况，这时我们会影响到它前面的一整段正数，它们都需要往前涂，直到遇到第一个 $0$ ：

f_{i,a_i-1}=\min(f_{pre_i-1,0},f_{pre_i-1,1},f_{pre_i-1,2})+1

其中 $pre_i$ 为 $i$ 前面第一个 $0$ 的位置。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],pre[N],f[N][3];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        pre[i]=pre[i-1];
        if(a[i]==0) pre[i]=i;
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=f[0][1]=f[0][2]=0;f[1][a[1]]=1;
    for(int i=2;i<=n;i++)
    {
        f[i][a[i]]=min(f[i-1][0]+1,min(f[i-1][1],f[i-1][2]));
        if(a[i]) f[i][a[i]-1]=min({f[pre[i]-1][0],f[pre[i]-1][1],f[pre[i]-1][2]})+1;
    }
    cout<<min({f[n][0],f[n][1],f[n][2]})<<'\n';
    return 0;
}

E. Max to the Right of Min

题意

给定一个长度为 $n$ 的排列 $p$ 。求区间 $[l,r]$ 的个数，满足区间内的最大值在区间内最小值的右侧。

数据范围： $1\leq n\leq 10^6$ 。

题解

我们对每个右端点枚举答案。考虑已经枚举了 $2\sim r-1$ ，当右端点移动到 $r$ 时，不难发现， $a_r$ 只会影响那些它作为最大或最小值的区间。

若 $a_r>a_{r-1}$ ，那么只需要考虑 $a_r$ 作为最大值的区间。记 $a_r$ 前第一个比它大的数的位置为 $b_r$ ，影响就是 $\forall x\in[b_r+1,r-1],ans_x\leftarrow 1$ 。
若 $a_r<a_{r-1}$ ，那么只需要考虑 $a_r$ 作为最小值的区间。记 $a_r$ 前第一个比它小的数的位置为 $c_r$ ，影响就是 $\forall x\in [c_r+1,r-1],ans_x\leftarrow 0$ 。

可以用线段树维护。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int a[N],b[N],c[N];
int tr[4*N],tag[4*N];
void pushdown(int l,int r,int p)
{
    int m=l+((r-l)>>1);
    tr[p*2]=tag[p]*(m-l+1),tr[p*2+1]=tag[p]*(r-m);
    tag[p*2]=tag[p*2+1]=tag[p];
    tag[p]=-1;
}
void update(int ul,int ur,int k,int l,int r,int p)
{
	if(ul<=l&&ur>=r)
    {
        tr[p]=(r-l+1)*k,tag[p]=k;
        return ;
    }
    int m=l+((r-l)>>1);
    if(tag[p]!=-1&&l!=r) pushdown(l,r,p);
    if(ul<=m) update(ul,ur,k,l,m,p*2);
    if(ur>m) update(ul,ur,k,m+1,r,p*2+1);
    tr[p]=tr[p*2]+tr[p*2+1];
}
int query(int ql,int qr,int l,int r,int p)
{
    if(ql<=l&&qr>=r) return tr[p];
    int m=l+((r-l)>>1);
    if(tag[p]!=-1&&l!=r) pushdown(l,r,p);
    int sum=0;
	if(ql<=m) sum+=query(ql,qr,l,m,p*2);
	if(qr>m) sum+=query(ql,qr,m+1,r,p*2+1);
	return sum;    
}
stack<int> stk;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(tag,-1,sizeof(tag));
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    a[0]=0x3f3f3f3f;
    stk.push(0);
    for(int i=1;i<=n;i++)
    {
        while(a[stk.top()]<a[i]) stk.pop();
        b[i]=stk.top();
        stk.push(i);
    }
    while(!stk.empty()) stk.pop();
    a[0]=0;
    stk.push(0);
    for(int i=1;i<=n;i++)
    {
        while(a[stk.top()]>a[i]) stk.pop();
        c[i]=stk.top();
        stk.push(i);
    }
    ll ans=0;
    for(int i=2;i<=n;i++)
    {
        if(a[i]>a[i-1]) update(b[i]+1,i-1,1,1,n,1);
        else update(c[i]+1,i-1,0,1,n,1);
        ans+=tr[1];
    }
    cout<<ans<<'\n';
    return 0;
}

F. XOR Partition

前置知识

最小异或生成树：给定 $n$ 个点，每个点有点权 $a_i$ ，点 $i$ 与点 $j$ 的边边权为 $a_i\oplus a_j$ 。求最小生成树。

我们将所有的 $a_i$ 插入一棵01trie中，仿照 Boruvka 算法的思路：每个叶子结点代表一个点，它们初始各自在一个连通块内。我们要做的就是：将左子树的叶子结点合并到一个连通块内，将右子树的叶子结点合并到一个连通块内，在两个连通块内各选出一个点来连边。

前两步可以递归实现，我们来考虑第三步。我们只需要枚举左子树或右子树内有哪些点，然后把在另一棵子树上查询与它异或出的最小值就可以了。为此，我们在插入前先把 $a$ 排序，每个点的子树内的点在 $a$ 中就一定是一段连续的区间，我们记录一下这个区间的左端点和右端点就可以了。

typedef long long ll;
const int N=2e5+5;
const int B=30;
const int M=N*B*2;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll a[N];
int cnt,son[M][2],l[M],r[M];
void insert(ll x,int id)
{
    int p=0;
    for(int i=B;i>=0;i--)
    {
        int bit=x>>i&1;
        if(!son[p][bit]) son[p][bit]=++cnt;
        p=son[p][bit];
        if(!l[p]) l[p]=id;
        r[p]=id;
    }
}
ll query(int p,int pos,ll x)
{
    ll res=0;
    for(int i=pos;i>=0;i--)
    {
        int bit=x>>i&1;
        if(son[p][bit]) p=son[p][bit];
        else
        {
            res+=1ll<<i;
            p=son[p][bit^1];
        }
    }
    return res;
}
ll divide(int p,int pos)
{
    if(son[p][0]&&son[p][1])
    {
        int x=son[p][0],y=son[p][1];
        ll mn=inf;
        if(r[x]-l[x]>r[y]-l[y]) swap(x,y);
            for(int i=l[x];i<=r[x];i++) mn=min(mn,query(y,pos-1,a[i]));
        mn+=1ll<<pos;
        return mn+divide(x,pos-1)+divide(y,pos-1);
    }
    else if(son[p][0]) return divide(son[p][0],pos-1);
    else if(son[p][1]) return divide(son[p][1],pos-1);
    else return 0;
}

sort(a+1,a+n+1);
for(int i=1;i<=n;i++) insert(a[i],i);
divide(0,B);

题意

定义一个集合 $S$ 的代价为 $\min_{x,y\in S} x\oplus y$ ，若集合内只有一个元素，它的代价为 $2^{30}$ 。给出一个长度为 $n$ 的数组 $a$ ，将它分为两个集合 $S_1,S_2$ 。要求最大化 $S_1,S_2$ 中的较小值。

数据范围： $2\leq |S|\leq 2\times 10^5$ 。

题解

考虑 $a$ 中最小的异或对 $(i,j)$ ，它们必然属于不同的集合。我们把它看作一条边，当整个图连通时所有关系就确定了。我们得到的是一棵最小异或生成树，将这棵树黑白染色就得到了最终方案。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const int N=2e5+5;
const int B=30;
const int M=N*B*2;
const ll inf=0x3f3f3f3f3f3f3f3f;
pli a[N];
int cnt,son[M][2],l[M],r[M];
int col[N],ans[N];
vector<int> g[N];
void insert(ll x,int id)
{
    int p=0;
    for(int i=B;i>=0;i--)
    {
        int bit=x>>i&1;
        if(!son[p][bit]) son[p][bit]=++cnt;
        p=son[p][bit];
        if(!l[p]) l[p]=id;
        r[p]=id;
    }
}
pli query(int p,int pos,ll x)
{
    ll res=0;
    for(int i=pos;i>=0;i--)
    {
        int bit=x>>i&1;
        if(son[p][bit]) p=son[p][bit];
        else
        {
            res+=1ll<<i;
            p=son[p][bit^1];
        }
    }
    return {res,l[p]};
}
ll divide(int p,int pos)
{
    if(son[p][0]&&son[p][1])
    {
        int x=son[p][0],y=son[p][1];
        int u,v;ll mn=inf;
        if(r[x]-l[x]>r[y]-l[y]) swap(x,y);
        for(int i=l[x];i<=r[x];i++) 
        {
            pli tmp=query(y,pos-1,a[i].first);
            if(tmp.first<mn)
            {
                mn=tmp.first;
                u=i,v=tmp.second;
            }
        }
        g[u].push_back(v),g[v].push_back(u);
        mn+=1ll<<pos;
        return mn+divide(x,pos-1)+divide(y,pos-1);
    }
    else if(son[p][0]) return divide(son[p][0],pos-1);
    else if(son[p][1]) return divide(son[p][1],pos-1);
    else return 0;
}
void dfs(int u,int fa)
{
    for(auto v:g[u])
    {
        if(v==fa) continue;
        col[v]=col[u]^1;
        dfs(v,u);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first,a[i].second=i;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) insert(a[i].first,i);
    divide(0,B);
    memset(col,-1,sizeof(col));
    col[1]=1;
    dfs(1,0);
    for(int i=1;i<=n;i++) ans[a[i].second]=col[i];
    for(int i=1;i<=n;i++) cout<<ans[i];
    return 0;
}

ACM

#dp #线段树 #最小异或生成树

Educational Codeforces Round 152 (Rated for Div. 2)

https://je3ter.github.io/2023/08/16/ACM/Educational Codeforces Round 152 (Rated for Div. 2)/

作者

Je3ter

发布于

2023年8月16日

许可协议

Educational Codeforces Round 153 (Rated for Div. 2) 上一篇

The 2023 Guangdong Provincial Collegiate Programming Contest 下一篇